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

Question

std :: map的时间复杂度是多少？它会在最糟糕的情况下堕落吗？或者由实施决定,我们无法知道吗？

Answer 1

查找与log(N)成比例.在典型情况下(作为红黑树实现),比较的数量可以是Log ₂ N的两倍.

插入通常也与Log ₂ N 成比例- 但是当您插入已经按顺序¹的多个项目时,会有一个特殊的规定.在这种情况下,您可以指定插入位置的"提示".当该提示正确时,每个插入都是(摊销)O(1)而不是O(Log N),因此按排序顺序插入一系列项目是线性的而不是N log(N).您指定的提示是要插入项目之后的位置的迭代器.

例如,如果文件中有多个项目按排序顺序排列,并且您希望将它们插入到地图中,则可以指定your_map.end()为"提示",构建映射将具有O(N)复杂度而不是O (N Log N)复杂性.

_{1.从技术上讲,这适用于您插入物品的任何时候,而不仅仅是当您按顺序插入物品时 - 但到目前为止,您有合理的"提示"可用的最常见情况是您按顺序插入物品时.}

Answer 2

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

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

值得注意的是，流行编译器附带的标准库有不太流行的替代品，例如msvc或gcc，它使用 s 实现这种容器B-tree，这会导致内存使用量降低，因为 B 树通常比 RB 占用更少的内存。树。

例如点击这里。