C++ std::map 的时间复杂度是多少

What is the time complexity of std::map

提问by user3288177

What is the time complexity of std::map? And will it degenerate in the worst case? Or it is decide by the implementation, we can't know it?

std::map 的时间复杂度是多少？在最坏的情况下它会退化吗？还是由执行决定，我们不知道？

回答by Jerry Coffin

Lookups are proportional to log(N). In a typical case (implementation as a red-black tree) the number of comparisons can be up to twice Log₂N.

查找与 log(N) 成正比。在典型情况下（作为红黑树实现），比较次数最多可达 Log ₂N 的两倍。

Insertions are normallyproportional to Log₂N as well--but there's a special provision made for when you're inserting a number of items that are already in order¹. In this case, you can specify a "hint" for where an insertion is going to take place. When that hint is correct, each insertion is (amortized) O(1) instead of O(Log N), so inserting a range of items in sorted order is linear instead of N log(N). The hint you specify is an iterator to the position just after the item to be inserted.

插入通常也与 Log ₂N成正比——但是当你插入一些已经在 order ^{1 中}的项目时，有一个特殊的规定。在这种情况下，您可以为将要进行插入的位置指定一个“提示”。当该提示正确时，每次插入（摊销）为 O(1) 而不是 O(Log N)，因此按排序顺序插入一系列项目是线性的，而不是 N log(N)。您指定的提示是指向要插入的项目之后的位置的迭代器。

For example, if you have a number of items in a file in sorted order, and you want to insert them into the map, you can specify your_map.end()as the "hint", and building the map will have O(N) complexity instead of O(N Log N) complexity.

例如，如果您在一个文件中按排序顺序有多个项目，并且您想将它们插入到地图中，您可以指定your_map.end()为“提示”，并且构建地图将具有 O(N) 复杂度而不是 O (N Log N) 复杂性。

---

---

_{1. Technically, this applies anytime you insert items, not just when you're inserting them in order--but by far the most common case where you have a reasonable "hint" available is when you're inserting items in order.}

_{1. 从技术上讲，这适用于您插入项目的任何时候，而不仅仅是在您按顺序插入项目时——但到目前为止，您有合理“提示”可用的最常见情况是按顺序插入项目。}

回答by J?rg Beyer

Usually the time complexity is specified for operations. In your case the lookupand insertseems relevant.

通常时间复杂度是为操作指定的。在您的情况下，查找和插入似乎相关。

See http://www.sgi.com/tech/stl/complexity.htmlfor the guaranteed complexties of the STL containers. And this http://www.sgi.com/tech/stl/AssociativeContainer.htmlon the Associative Containers.

请参阅http://www.sgi.com/tech/stl/complexity.html以了解 STL 容器的复杂性。还有这个关于关联容器的http://www.sgi.com/tech/stl/AssociativeContainer.html。

Another source is found here:

另一个来源可以在这里找到：

• http://www.cplusplus.com/reference/map/map/find/--> Logarithmicin size.
• http://www.cplusplus.com/reference/map/map/insert/--> If a single element is inserted, logarithmicin size in general, but amortized constant if a hint is given and the position given is the optimal.

• http://www.cplusplus.com/reference/map/map/find/-->大小为对数。
• http://www.cplusplus.com/reference/map/map/insert/--> 如果插入单个元素，一般大小为对数，但如果给出提示并且给出的位置是最佳的，则摊销常量。

the lookup of std::map is log(number of elements in the map).

std::map 的查找是 log(map 中的元素数)。

回答by user2485710

This depends on the implementation, you can't associate a complexity of any kind to std::mapjust by looking at the language specs.

这取决于实现，您不能std::map仅通过查看语言规范就将任何类型的复杂性关联到。

Usually an std::mapis implemented as a Red-Black Treeand you can find all info about the Big-O properties of this kind of containers here.

通常 anstd::map实现为红黑树，您可以在此处找到有关此类容器的 Big-O 属性的所有信息。

Notably there are less popular alternatives to the standard libraries shipped with popular compilers such as msvcor gcc, that implements this kind of containers with B-trees, this leads to lower memory usage due to the fact that a B-tree usually occupy less memory that an RB-tree.

值得注意的是，有一些不太流行的替代标准库可以替代流行的编译器（例如msvcor ）gcc，它们使用B-trees实现这种容器，这会导致内存使用量较低，因为 B 树通常占用的内存少于 RB-树。

For example click here.

例如点击这里。

回答by ak_2050

if you're asking about the lookup time compexity for std::map then that would be O(log(n)) since the stl implemented the std::map library as a Tree (binary tree) datastructure.

如果您询问 std::map 的查找时间复杂性，那么这将是 O(log(n)) ，因为 stl 将 std::map 库实现为树（二叉树）数据结构。

More information here: http://www.cplusplus.com/reference/map/map/

更多信息在这里：http: //www.cplusplus.com/reference/map/map/

Here is also the commonly used std::unordered_map, which would be your hashmap (no ordering hence) with a O(1) look up speed, however, using more memory than the Tree per the design of the data structure.

这里也是常用的 std::unordered_map，它将是您的哈希图（因此没有排序），具有 O(1) 查找速度，但是，根据数据结构的设计，使用比树更多的内存。