What is the time complexity of std::map

Question

What is the time complexity of std::map? And will it degenerate in the worst case? Or it is decide by the implementation, we can't know it?

Answer 1

Lookups are proportional to log(N). In a typical case (implementation as a red-black tree) the number of comparisons can be up to twice Log₂N.

Insertions are normally proportional to Log₂N as well--but there's a special provision made for when you're inserting a number of items that are already in order¹. In this case, you can specify a "hint" for where an insertion is going to take place. When that hint is correct, each insertion is (amortized) O(1) instead of O(Log N), so inserting a range of items in sorted order is linear instead of N log(N). The hint you specify is an iterator to the position just after the item to be inserted.

For example, if you have a number of items in a file in sorted order, and you want to insert them into the map, you can specify your_map.end() as the "hint", and building the map will have O(N) complexity instead of O(N Log N) complexity.

---

_{1. Technically, this applies anytime you insert items, not just when you're inserting them in order--but by far the most common case where you have a reasonable "hint" available is when you're inserting items in order.}

Answer 2

This depends on the implementation, you can't associate a complexity of any kind to std::map just by looking at the language specs.

Usually an std::map is implemented as a Red-Black Tree and you can find all info about the Big-O properties of this kind of containers here.

Notably there are less popular alternatives to the standard libraries shipped with popular compilers such as msvc or gcc, that implements this kind of containers with B-trees, this leads to lower memory usage due to the fact that a B-tree usually occupy less memory that an RB-tree.

For example click here.

Answer 3

Usually the time complexity is specified for operations. In your case the lookup and insert seems relevant.

See http://www.sgi.com/tech/stl/complexity.html for the guaranteed complexties of the STL containers. And this http://www.sgi.com/tech/stl/AssociativeContainer.html on the Associative Containers.

Another source is found here:

• http://www.cplusplus.com/reference/map/map/find/ --> Logarithmic in size.
• http://www.cplusplus.com/reference/map/map/insert/ --> If a single element is inserted, logarithmic in size in general, but amortized constant if a hint is given and the position given is the optimal.

the lookup of std::map is log(number of elements in the map).