c++ - 提示插入到 std::map 会导致树不平衡吗？

Question

这是否会导致 std::map/set 中的树不平衡(以及随后的搜索性能不佳):

std::set<int> s;
for(int i = 0; i< 1000; ++i)
    s.insert(s.end(), i);

?

或者换句话说:“提示插入”会根据需要重新平衡底层树吗？

Afaik，C++ 标准并不能保证这一点，但我想知道大多数流行的实现在这种情况下的表现如何。

Answer 1

不管有序关联容器的底层实现是什么(标准没有规定，虽然通常是自平衡二叉查找树)，hinted insert (iterator insert( const_iterator hint, const value_type& value );) 可以用下面的简单算法来满足:

1. 比较值与*hint 和*prev(hint)

2. 如果它适合它们，将它插入那里。

3. 否则，忽略提示。

只要 prev(hint) 是摊销常数时间，只要 hint 是正确的，该算法就是摊销常数时间。 (“正确”的意思是它是插入点之后的位置。)

如果提示不正确，忽略提示是完全可以接受的，因此提供不正确的提示不会对数据结构造成任何影响；它仍然与插入之前一样平衡(可对数访问)。但是提供不正确的提示会强制计算 O(1) 次额外比较，因此仅当提示通常正确时才应使用插入的提示版本，对于“通常”的某些值。

一个常见的用例是当已经对要插入的条目进行了搜索，因此插入位置是明确已知的。这避免了在插入之前需要做某事时搜索两次的开销，而不会在其他进程修改 find() 之间的 set 的情况下牺牲安全性并提示 insert()(当然，假设适当的锁定)。