Time Complexity of std::multimap::equal_range

Good afternoon, I am wondering what the time complexity of std::multimap::equal_range is? Is it Big-O(n) or BIG-0(log n). I remember reading that the time 开发者_如何学运维complexity of std::multimap::erase "is logarithmic plus linear time for the length of the sequence being removed." <http://frank.mtsu.edu/~csjudy/STL/Multimap.html>

---

C++03 standard, Table 69 ("Associative container requirements") in 23.1.2 says that equal_range has logarithmic complexity.

---

equal_range is an O(log n) operation returning the pair of lower_bound and upper_bound.

This means it will return an iterator range starting with the first key that is greater-than or equal-to the search key and ending with the first key that is greater than the search key.

---

I've never really found a better source for this sort of information than the SGI STL Programmer's Guide. In this case the page you're interested in is the Sorted Associative Container concept page which states under the Complexity Guarantees section:

Lower bound, upper bound, and equal range are logarithmic. [1]

...

[1] This is a much stronger guarantee than the one provided by Associative Container. The guarantees in Associative Container only apply to average complexity; worst case complexity is allowed to be greater. Sorted Associative Container, however, provides an upper limit on worst case complexity.