c++ - std::map 如何通过字符串查找元素？

Question

在 C++ 中，您可以使用 std::map 创建 map “容器” .

在我的例子中，键是字符串，元素是整数。 ( std::map<string, int> )

我想知道的是 map 如何通过使用 [] 检索它们的元素运算符(operator)用一个字符串。

map 是否只是将输入的字符串与其现有字符串键集的 ALL 与我声明的元素进行比较？如果是这种情况，那么如果我需要一种从一长串字符串中检索我需要的元素的最佳方法，那肯定会显得很慢。

按字符串索引的更快方法是对字符串中的每个字符使用 256 个相同类型链表的链表。这意味着为了让我检索我的元素，我所要做的就是说 [char 1]->[char 2]->...[char n]->element.

速度将由字符串的长度决定，或者无论您指向下一个字符多少次。

编辑:我刚才描述的这个过程被称为 Trie ，这不是 std::map 使用的。

如果std::map<string, element_type>不使用这种方法，那么它是如何工作的呢？如果我碰巧添加了大量 key ，它是否值得使用？

如果我的问题似乎不清楚，请告诉我，以便我进行更改。我只需要知道 map 中键的数量是否会减慢访问过程，以及 map 如何匹配它们的元素。

Answer 1

std::map使用 binary search tree .所以查找时间与 log(n) 成正比, 其中n是 map 中元素的数量。所以不，它并不慢。

另一种将字符串映射到值的方法通常(但并非总是)比二叉搜索树更快，它是 hash map .标准库也有 std::unordered_map 形式的其中之一。 .

您在提案中描述的内容类似于 Trie .标准库没有 Trie 类。请注意，虽然 Trie 适用于作为字符串的键的特定情况，但二叉搜索树更为通用，并且只需要可以对键进行排序。 std::map使用 operator< 进行此排序吗？默认情况下。