std :: map и поведение уже вставленных данных

Question

Перемещается ли std::map уже вставленные значения при вставке новых данных?

Answer 1

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

Это не делает недействительными любые итераторы или ссылки на элементы в дереве. Такая балансировка осуществляется с помощью указателей, поэтому вам не о чем беспокоиться; сами узлы остаются на месте.

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

Answer 2

Стандарт не требует конкретных реализаций STL, только характеристики поведения и времени выполнения. Тем не менее, список пропусков или дерево является очень вероятной реализацией std :: map, поэтому ссылки будут обновляться, и относительный порядок будет меняться, но фактические данные не будут перемещаться.

Answer 3

Стандарт C ++ не диктует реализацию std::map только его поведение и эффективность. Реализации разрешено перемещать элементы; однако это может быть неэффективно.

Большинство std::map контейнеров реализованы с использованием древовидной структуры данных со ссылками. При вставке или переупорядочении элементов ссылки изменяются, но данные не перемещаются. Перемещение предметов замедлит время выполнения std::map.

Answer 4

Рассмотрим типичный узел в двусвязном списке:

template <class T>
struct Node
{
  Node* mPrevious;
  Node* mNext;
  T mValue;
};

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

void insert(Node* target, Node* newNode)
{
  target->mPrevious->mNext = newNode;
  target->mPrevious = newNode;

  newNode->mPrevious = target->mPrevious;
  newNode->mNext = target;
}

Поведение схоже с std::map (или std::set, std::multimap или std::multiset, поскольку они все реализованы с использованием одной и той же базовой структуры в целом).

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