这是否会导致不平衡树(以及随后的搜索性能不佳)std::map/set:
std::set<int> s;
for(int i = 0; i< 1000; ++i)
s.insert(s.end(), i);
？
或者换句话说:"暗示插入"会根据需要重新平衡底层树吗？
Afaik,C++标准不保证这一点,但我想知道在这种情况下最流行的实现是如何表现的.
不管有序关联容器的底层实现如何（标准没有规定，尽管它通常是自平衡二叉搜索树），提示插入（）的要求iterator insert( const_iterator hint, const value_type& value );可以通过以下简单算法来满足：
将值与 *hint 和 *prev(hint) 进行比较
如果它适合它们之间，请将其插入那里。
否则，请忽略该提示。
只要prev(hint)是摊销常数时间，只要hint是正确的，该算法就是摊销常数时间。（“正确”是指它位于插入点之后的位置。）
如果提示不正确，忽略提示是完全可以接受的，因此提供不正确的提示不会对数据结构造成任何差异；它仍然与插入之前一样平衡（可对数访问）。但是提供不正确的提示会强制计算 O(1) 额外的比较，因此只有在提示通常正确的情况下才应使用插入的提示版本，对于某些“通常”值。
常见的用例是已经搜索了要插入的条目，因此可以明确知道插入位置。这避免了在插入之前需要执行某些操作时搜索两次的开销，并且在其他进程修改了和 之间的set情况下也不会牺牲安全性（当然，假设有适当的锁定）。find()insert()