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

std :: map的时间复杂度是多少？它会在最坏的情况下退化吗？或者由实施决定，我们无法知道吗？std :: map的时间复杂度是多少:: map

2014-02-12 user3288177

* what *的时间复杂度？无论如何，看看[这里]（http://en.cppreference.com/w/cpp/container/map）。 – juanchopanza

@juanchopanza它可以是除数据检索以外的任何东西吗？ – ApproachingDarknessFish

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

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

请参见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/ - >如果插入单个元素，一般大小为对数，但如果给出提示并且给出的位置是最优的，则摊销常数。

的标准::地图查找是log（在地图数目的元件）。

来源

2014-02-12 22:15:22

如果您询问std :: map的查询时间强弱，那么stl :: map库将作为Tree（二叉树）数据结构实现，因此这将是O（log（n））。

点击此处了解详情： http://www.cplusplus.com/reference/map/map/

这里也是常用的std :: unordered_map，这将是你的HashMap（没有顺序，因此）与O（1）查找速度，但是，使用更多的内存每个数据结构的设计都要比Tree要好。

来源

2014-02-12 22:22:25

查找与log（N）成正比。在典型的情况下（实施作为红黑树）的比较的数量可高达两倍登录 N.

的插入是通常正比于登录 N作为阱 - 但有当您插入许多已经按顺序排列的物品时，特殊条款会提供。在这种情况下，您可以为插入的位置指定一个“提示”。当提示正确时，每个插入都是（分期付款）O（1）而不是O（日志N），因此按排序顺序插入一系列项目是线性的，而不是N log（N）。您指定的提示是要插入项目后面的位置的迭代器。例如，如果按排序顺序在文件中有多个项目，并且要将它们插入到地图中，则可以指定your_map.end()作为“提示”，并且构建地图将具有O（N ）复杂性而不是O（N日志N）的复杂性。

_{1。从技术上讲，这适用于任何时候你插入项目，而不只是当你为了将他们 - 但迄今为止最常见的情况，你有一个合理的“暗示”可当您按顺序插入项目。}

来源

2014-02-12 22:57:07

这依赖于实现，你不能在任何种类的复杂性std::map只是看着语言规范关联。

通常std::map实现为Red-Black Tree，您可以找到有关这种容器here的Big-O属性的所有信息。

值得注意的是有不太受欢迎的替代品随流行的编译器，如msvc或gcc标准库，实现这种与B-tree小号的容器，这导致较低的内存使用情况，由于这样的事实，一个B-tree通常占用一个RB树的内存较少。

例如click here。

来源

2014-02-12 23:09:14 user2485710

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

@假名和实际定义是什么？ – user2485710

我在看2012年1月草案（与ISO 2011相同，除了次要版本），[map.access]部分：“复杂性：对数。” – Pseudonym

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

回答

相关问题