Вставка элементов в нужные позиции на карте STL

Question

map <int, string> rollCallRegister;
map <int, string> :: iterator rollCallRegisterIter;
map <int, string> :: iterator temporaryRollCallRegisterIter;

rollCallRegisterIter     = rollCallRegister.begin ();
tempRollCallRegisterIter = rollCallRegister.insert (rollCallRegisterIter, pair <int, string> (55, "swati"));

rollCallRegisterIter++;
tempRollCallRegisterIter = rollCallRegister.insert (rollCallRegisterIter, pair <int, string> (44, "shweta"));

rollCallRegisterIter++;
tempRollCallRegisterIter = rollCallRegister.insert (rollCallRegisterIter, pair <int, string> (33, "sindhu"));

// Displaying contents of this map.
cout << "\n\nrollCallRegister contains:\n";
for (rollCallRegisterIter = rollCallRegister.begin(); rollCallRegisterIter != rollCallRegister.end(); ++rollCallRegisterIter)
{
    cout << (*rollCallRegisterIter).first << " => " << (*rollCallRegisterIter).second << endl;
}

Выход:

rollCallRegister contains:
33 => sindhu
44 => shweta
55 => swati

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

Answer 1

Интерфейс действительно немного сбивает с толку, потому что он очень похож на std::vector<int>::insert (например) и все же не дает того же эффекта ...

Для ассоциативных контейнеров, таких как set,map и новые unordered_set и co, вы полностью отказываетесь от контроля над порядком элементов (как видно из итерации по контейнеру).В обмен на эту потерю контроля вы получаете эффективный поиск.

Не имеет смысла внезапно предоставлять вам контроль над вставкой, поскольку это позволит вам сломать инварианты контейнера, и вы потеряетеэффективный поиск, который является причиной использования таких контейнеров в первую очередь.

И, таким образом, insert(It position, value_type&& value) не вставляется в указанное положение ...

Однако это дает нам некоторое пространстводля оптимизации: при вставке элемента в ассоциативный контейнер необходимо выполнить поиск, чтобы определить, куда вставить этот элемент.Позволяя вам указать подсказку , вы получаете возможность help контейнера ускорить процесс.

Это можно проиллюстрировать на простом примере: предположим, чтоВы получаете элементы, уже отсортированные по какому-либо интерфейсу, поэтому не стоит использовать эту информацию!

template <typename Key, typename Value, typename InputStream>
void insert(std::map<Key, Value>& m, InputStream& s) {
  typename std::map<Key, Value>::iterator it = m.begin();

  for (; s; ++s) {
    it = m.insert(it, *s).first;
  }
}

Некоторые элементы могут быть плохо отсортированы, но это не имеет значения, если два последовательных элементав правильном порядке, тогда мы получим, в противном случае ... мы просто будем работать как обычно.

Answer 2

Поскольку std::map является отсортированным ассоциативным контейнером.

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

Согласно здесь параметр позиции равен

позиция первого элемента, который будет сравниваться для вставки операция. Обратите внимание, что это не заставляет новый элемент находиться в эта позиция в контейнере карты (элементы в наборе всегда следовать определенному порядку), но это на самом деле указывает на возможное положение вставки в контейнер, если, если установлено элемент, который предшествует фактическому местоположению, где элемент вставлено, делает для очень эффективной операции вставки. итератор тип члена, определенный как двунаправленный тип итератора.

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

Вы можете использовать std::vector<std::pair<int,std::string>>, если важен порядок вставки.

Answer 3

Карта всегда сортируется, но вы даете «подсказку» относительно того, куда элемент может пойти как оптимизация.

Вставка - O (log N), но если вы можете успешно сообщить контейнеру, куда он идет, это постоянное время.

Таким образом, если вы создаете большой контейнер уже отсортированных значений, то каждое значение будет вставлено в конце, хотя дерево потребуется перебалансировать довольно много раз.

Answer 4

Как говорит sad_man, это ассоциативно. Если вы устанавливаете значение с помощью существующего ключа, то вы перезаписываете предыдущее значение.

Теперь итераторы необходимы, потому что вы обычно не знаете, что это за ключи.