c++ - 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.}