станд.:: карта и поведение уже вставленных данных
Делает std::map уже переместить вставленные значения при вставке новых данных?
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 , должен быть повторно вычислен после вставки или удаления, и его лучше не кэшировать.
Стандарт C ++ не диктует реализацию std :: map только его поведение и эффективность. Реализациям разрешено перемещать элементы; однако это может быть неэффективным.
Большинство контейнеров std :: map реализованы с использованием древовидной структуры данных со ссылками. При вставке или изменении порядка элементов ссылки изменяются, но данные не перемещаются. Перемещение элементов замедлит время выполнения std :: map .
Стандарт не предписывает конкретные реализации STL, только поведение и характеристики времени выполнения. Учитывая это, пропущенный список или дерево - это, скорее всего, реализация std::map, поэтому ссылки будут обновляться, и относительное упорядочивание будет меняться, но фактические данные не будут перемещаться.