地图的插入在 c++ 中到底如何工作？

Question

我试图自己用 C++ 重新实现地图容器，但我陷入了 insert 方法。

注意：我知道地图使用自平衡树（红黑树），因此当您插入新元素时，您需要遵守二叉搜索树规则。

现在我的问题是：

(C++98) 中的映射有 3 个插入成员函数，

single element (1)  pair<iterator,bool> insert (const value_type& val);

with hint (2)       iterator insert (iterator position, const value_type& val);

range (3)           template <class InputIterator>
                    void insert (InputIterator first, InputIterator last);

单个元素 (1) 很清楚。

但第二个不是。

我想知道如何使用提示，如何检查给我的位置是否尊重树的规则，以及如何修复它。

注 2：这是基于 c++98 我知道这在 C++11 中发生了变化。

Answer 1

当提示正确时，提示重载具有更严格的复杂性要求。如果提示不正确，则会被忽略。

复杂性

如果插入发生在提示之后的位置，则为摊销常量，以容器大小的对数表示
否则。

如果您已经知道（或者甚至有一个很好的猜测）要插入的值应该放在哪里，例如您要插入一系列已排序的值，则可以使用提示重载作为优化。