Блог

Главная - Вопросы по программированию - Переместить std :: map против перемещения всех элементов std ::map

Переместить std :: map против перемещения всех элементов std ::map

#c #c 11 #move #stdmap #c -standard-library

Вопрос:

 std::map<int, Obj> mp;
// insert elements into mp

// case 1
std::map<int, Obj> mp2;
mp2 = std::move(mp);

// case 2
std::map<int, Obj> mp3;
std::move(std::begin(mp), std::end(mp), std::inserter(mp3, std::end(mp3));

Меня смущают эти два случая. Они точно такие же?

Комментарии:

1. Первый имеет постоянную временную сложность, второй имеет n log n временную сложность.

2. нет, это не одно и то же. Обратите внимание, что карта назначения во втором случае может немного отличаться (например, иметь другой порядок). Случай 1 очень быстрый, случай 2 должен выделить некоторую внутреннюю структуру карты mp3 .

3. Обратите внимание, что первая копия просто перемещает все дерево с первой карты на вторую, первая (обычно) остается пустой, в то время как второй вариант из-за природы std::move оставляет узлы во втором дереве как есть, перемещается только их содержимое: Предположим std::map<std::vector<...>> , тогда содержимое вектора перемещается, в то время как векторыв первой карте сами остаются (обычно пустыми).

Ответ №1:

Они точно такие же?

Нет, это не так!

Первый вызывает конструктор перемещения std::map 4, и операция перемещения будет выполнена на уровне класса / структуры данных.

[…]

  1. Переместить конструктор. После того, как контейнер переместит конструкцию ( overload (4) ), ссылки, указатели и итераторы (кроме конечного итератора) в other остаются действительными, но ссылаются на элементы, которые сейчас находятся внутри *this . Действующий стандарт предоставляет эту гарантию с помощью общего заявления в container.requirements.general, а более прямая гарантия рассматривается с помощью LWG 2321

Сложность

4) Константа. Если задан alloc и alloc != other.get_allocator() , то линейный.

Второй std::move — из <algorithm> заголовка, который выполняет поэлементное перемещение (т.Е. Пары ключ-значение) на другую карту.

  1. Перемещает элементы в диапазоне [first, last) в другой диапазон, начиная с d_first , начиная с первого и заканчивая последним — 1. После этой операции элементы в перемещенном из диапазона по-прежнему будут содержать допустимые значения соответствующего типа, но не обязательно те же значения, что и до перемещения.

Сложность

Точно last - first перемещать назначения.

Ответ №2:

Нет, они не совпадают.

  • Случай 1 перемещает содержимое всего map сразу. map Внутренние указатели «перемещаются» на mp2 — ни один из pair указателей на карте не затрагивается.
  • Случай 2 перемещает индивидуумов pair на карте, одного за другим. Обратите внимание, что map ключи s const не могут быть перемещены, а вместо этого будут скопированы. mp будет по-прежнему содержать столько же элементов, сколько и раньше, но со значениями в неопределимом состоянии.
Метки: