c++ - 为什么 std::map::emplace_hint 的时间复杂度是恒定的，提供正确的提示

Question

从cppreference中可以看出std::map::emplace_hint的复杂度是:

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

如果我们提供一个好的提示，为什么它是不变的？

Answer 1

std::map 是一棵红黑树，为了将新元素插入/放置到 std::map 中，我们需要:

1. 找到插入/放置新元素的正确位置 - O(lgN)
2. 重新着色和旋转节点以保持红黑树属性。 - O(1)

如果提供了一个好的提示，搜索部分(#1)已经完成，对于#2 有4 scenarios , 其中每个 O(1)

所以在适当的提示下，std::map::emplace_hint 是 O(1)