c++ - map insert(const_iterator hint, value) 用法

Question

我正在浏览 cppreference map insert operation 并找到一个用法:

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

hint: iterator to the position before which the new element will be inserted (since 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

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

如果提示正确，插入将在分摊的常数时间内发生，但如果错误，它将在 map 或 set 的大小上呈对数。

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