std::multimap::equal_range的时间复杂度

Question

下午好，我想知道std::multimap::equal_range的时间复杂度是多少？是Big-O(n)还是BIG-0(log )。我记得我读到过std::multimap::erase的时间复杂度是“被删除的序列的长度的对数加上线性时间。”[http://frank.mtsu.edu/~csjudy/STL/Multimap.html](http://frank.mtsu.edu/~csjudy/STL/Multimap.html)

Answer 1

C++03标准，23.1.2中的表69 (“关联容器要求”)表明equal_range具有对数复杂度。

Answer 2

equal_range是一个O(log )操作，返回lower_bound和upper_bound对。

这意味着它将返回一个迭代器范围，从大于或等于搜索关键字的第一个关键字开始，到大于搜索关键字的第一个关键字结束。

Answer 3

我从未真正找到过比SGI STL Programmer's Guide更好的此类信息来源。在本例中，您感兴趣的页面是排序的关联容器concept page，它在复杂性保证部分下声明：

的下界、上界和相等范围是对数的。1

..。

1这是一个比关联容器提供的更强大的保证。关联容器中的保证只适用于平均复杂度；允许最坏情况下的复杂度更高。然而，排序关联容器提供了最坏情况下的复杂度上限。