地图插入(const_iterator提示，值)用法

Question

我正在查看cppreference映射插入操作并找到用法：

iterator insert( const_iterator hint, const value_type& value ); //(since C++11)

提示：迭代到新元素将位于的位置 插入(自C++11起(

我知道map和set都是内部排序的，那么"在提示后插入"的用法是如何工作的呢？

测试代码：

#include <set>
using namespace std;
int main()
{
set<int> foo = { 9,2,4,8,0 }; //0,2,4,8,9
//foo.insert(-1); //-1,0,2,4,8,9
const auto pos = foo.find(4);
foo.insert(pos, -1); //I expected to get 0,2,4,-1,8,9
//(unreasonable since map should be always sorted but that's how I understand the function usage)
// And I got -1,0,2,4,8,9  same result as insert(value)
}

insert(const_iterator hint, value)如何工作？

Answer 1

你传递的迭代器"只是"一个提示，这意味着如果提示错误，函数将回退到常规插入。

如果提示正确，则插入将在摊销常量时间内发生，但如果是错误的，则在映射或集合的大小中将对数。

要查看如何在llvm stdlib中完成它：https://github.com/llvm-mirror/libcxx/blob/master/include/map