Эффективность использования вставки с картой в C ++

Question

На * cplusplus.com есть пример , который я не понимаю.

В следующем примере, когда вставляется 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 является итератором подсказок):

Элемент вставляется как можно ближе к позиции непосредственно перед p.

Позиция до begin() не существует.Во всяком случае, вероятно, было бы более эффективно не давать подсказку для первого insert.

Во время второго insert, 'b' находится на begin(), и мы не хотим insert 'c' "как раз перед" 'b', поэтому стандарт "как можно ближе" сработает, и можно ожидать, что insert будет искать правильное место, несмотря на подсказку.

В более общем смысле подсказки становятся полезными, когда в дереве много элементов, поэтому реализация insert может просто проверить пару элементов рядом с подсказкой, чтобы обеспечить порядок, не спускаясь вниз от корня двоичного дерева.