c++ - 在 C++ 中使用带有映射的插入的效率

Question

有 an example on cplusplus.com reference我不明白。

在下面的例子中，当插入 C 时，为什么它比插入 B 效率低？它们有什么不同？

  // second insert function version (with hint position):
  std::map<char,int>::iterator it = mymap.begin();
  mymap.insert (it, std::pair<char,int>('b',300));  // max efficiency inserting
  mymap.insert (it, std::pair<char,int>('c',400));  // no max efficiency inserting

Answer 1

该示例使用 insert 的重载，它接受一个“提示”迭代来说明新元素应该插入后备二叉树的哪个部分。该示例暗示 it - 已初始化为 begin() - 在插入空表时是一个尽可能好的提示，但用处不大(可能根本没有用) ) 插入第二个元素时。

我不确定为什么该网站(历史上不是很好 - 我更信任 cppreference.com)对插入 'b' 做出效率断言。标准的要求是(p 是提示迭代器):

The element is inserted as close as possible to the position just prior to p.

begin() 之前的位置不存在。如果有的话，不为第一个 insert 提供提示可能会更有效。

在第二次 insert 期间，'b' 位于 begin() 并且我们不想insert 'c' “就在”'b' 之前，因此标准的“尽可能接近”开始并且 insert 可以尽管有提示，但仍要四处摸索寻找正确的位置。

更一般地说，当树有更多元素时，提示会变得有用，因此 insert 实现可以只检查提示附近的几个元素以确保顺序，而无需从树的根部向下工作二叉树。