std::map的时间复杂度是什么？

Question

std::map的时间复杂度是什么？它会在最坏情况下退化吗？或者它由实现决定，我们不能知道它？

- user3288177

---

时间复杂度针对什么？不管怎样，看一下这里：http://en.cppreference.com/w/cpp/container/map。 - juanchopanza

@juanchopanza 这可能是除了数据检索之外的任何事情吗？ - ApproachingDarknessFish

@ValekHalfHeart 是的。例如数据插入或元素删除。 - juanchopanza

Answer 1

查找操作的时间复杂度与 log(N) 成正比。在典型情况下（用红黑树实现），比较次数最多可以达到两倍的 Log₂N。

插入操作通常也与 Log₂N 成正比，但是当你要插入一些已经有序的项目时，会有一个特殊的方法。在这种情况下，你可以指定一个“提示”，它表示插入的位置。当这个提示正确时，每个插入操作的平均时间复杂度为O(1)，而不是O(Log N)，因此以已排序顺序插入一系列项目的时间复杂度是线性的，而不是N log(N)。你指定的提示是一个迭代器，指向要插入的项的后一个位置。

例如，如果你有几个按顺序排列的文件，并想将它们插入到映射中，你可以将 your_map.end() 作为“提示”，构建映射的复杂度将从O(N log(N)) 变成 O(N)。

---

_{1. 技术上讲，这适用于任何时候插入项目，而不仅仅是当你按顺序插入时--但是当你插入项目时，大多数情况下可以提供一个合理的“提示”。}

- Jerry Coffin

---

你能详细说明一下我们如何使用一个非常长的已排序数字列表来更新地图吗？谢谢。 - lllllllllllll

Answer 2

这取决于具体实现，你无法仅通过查看语言规范来将任何复杂度类型与std::map相关联。

通常，std::map被实现为红黑树，你可以在这里找到有关这种容器的大O特性的所有信息。

值得注意的是，与流行编译器（如msvc或gcc）附带的标准库不同，还存在不太流行的替代方案，它们使用B-tree来实现这种容器，这会导致内存使用较低，因为B-tree通常占用的内存比RB-tree少。

例如点击这里。

- user2485710

---

是的，您可以将复杂度与std::map操作相关联，因为它们被写入规范中。特别是，“排序数组”实现std::map由于这个原因（以及指针/迭代器失效要求）是不符合标准的。 - Pseudonym

@Pseudonym，实际定义是什么？ - user2485710

我正在查看2012年1月的草案（除了一些小的副本编辑之外，与ISO 2011相同），第[map.access]节：“复杂度：对数级别。” - Pseudonym

Answer 3

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

请参见http://www.sgi.com/tech/stl/complexity.html，了解STL容器的保证复杂性。以及这个http://www.sgi.com/tech/stl/AssociativeContainer.html关于关联容器的内容。

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

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

std::map的查找时间复杂度为对数级别，与其中元素的数量成对数关系。

- Jörg Beyer

---

前两个链接已经失效。 - Zoe stands with Ukraine

这就是为什么你不应该在回答中添加链接，而是要总结它们的内容。 - Matej Novosad

Answer 4

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

更多信息请参见： http://www.cplusplus.com/reference/map/map/ 这里还有常用的std::unordered_map，它将是您的哈希映射（无序），具有O(1)的查找速度，但是根据数据结构的设计使用更多的内存。

- ak_2050