Why std::map::emplace_hint's time complexity is constant providing correct hint

user_70198 0
Viewed 65

From cppreference, it is said the complexity of std::map::emplace_hint is:

Complexity
Logarithmic in the size of the container in general, but amortized constant if the new element is inserted just before hint.

Why it is constant if we provide a good hint?

stl c++
1 Answers

std::map is a red-black tree, in order to insert/emplace an new element into a std::map, we need:

  1. Find the proper position to insert/emplace the new element - O(lgN)
  2. Recolor and rotate nodes to keep red-black tree properties. - O(1)

If a good hint is provided, the search part(#1) is already done, and for #2 there are 4 scenarios, with each of them O(1)

So with proper hint, std::map::emplace_hint is O(1)

user_701980
Related