словарь — вставить против emplace против оператора [] в карту C ++

Emplace: использует ссылку rvalue для использования реальных объектов, которые вы уже создали. Это означает, что конструктор копирования или перемещения не вызывается, что хорошо для БОЛЬШИХ объектов! O (log (N)) время.

Вставка: Имеет перегрузки для стандартной ссылки lvalue и ссылки rvalue, а также итераторы для списков элементов для вставки и «подсказки» относительно позиции, к которой принадлежит элемент. Использование итератора «подсказки» может привести к тому, что время вставки сводится к постоянному времени, в противном случае это время O (log (N)).

Оператор []: проверяет, существует ли объект, и если он существует, изменяет ссылку на этот объект, в противном случае использует предоставленные ключ и значение для вызова make_pair для двух объектов, а затем выполняет ту же работу, что и функция вставки. Это время O (log (N)).

make_pair: делает немного больше, чем создает пару.

Не было никакой необходимости добавлять emplace к стандарту. В C ++ 11 я считаю, && тип ссылки был добавлен. Это устранило необходимость в семантике перемещения и позволило оптимизировать определенный тип управления памятью. В частности, ссылка на стоимость. Перегруженная вставка (value_type &&Оператор) не использует семантику in_place и поэтому гораздо менее эффективен. Хотя он предоставляет возможность работы с ссылками на rvalue, он игнорирует их основное назначение — создание объектов.

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

Вот пример для демонстрации:

#include <vector>

struct foo
{
explicit foo(int);
};

int main()
{
std::vector<foo> v;

v.emplace(v.end(), 10);      // Works
//v.insert(v.end(), 10);     // Error, not explicit
v.insert(v.end(), foo(10));  // Also works
}

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

Следующий код может помочь вам понять «общую идею» о том, как insert() отличается от emplace():

#include <iostream>
#include <unordered_map>
#include <utility>

struct Foo {
static int foo_counter; //Track how many Foo objects have been created.
int val; //This Foo object was the val-th Foo object to be created.

Foo() { val = foo_counter++;
std::cout << "Foo() with val:                " << val << '\n';
}
Foo(int value) : val(value) { foo_counter++;
std::cout << "Foo(int) with val:             " << val << '\n';
}
Foo(Foo& f2) { val = foo_counter++;
std::cout << "Foo(Foo &) with val:           " << val
<< " \tcreated from:      \t" << f2.val << '\n';
}
Foo(const Foo& f2) { val = foo_counter++;
std::cout << "Foo(const Foo &) with val:     " << val
<< " \tcreated from:      \t" << f2.val << '\n';
}
Foo(Foo&& f2) { val = foo_counter++;
std::cout << "Foo(Foo&&) moving:             " << f2.val
<< " \tand changing it to:\t" << val << '\n';
}
~Foo() { std::cout << "~Foo() destroying:             " << val << '\n'; }

Foo& operator=(const Foo& rhs) {
std::cout << "Foo& operator=(const Foo& rhs) with rhs.val: " << rhs.val
<< " \tcalled with lhs.val = \t" << val
<< " \tChanging lhs.val to: \t" << rhs.val << '\n';
val = rhs.val;
return *this;
}

bool operator==(const Foo &rhs) const { return val == rhs.val; }
bool operator<(const Foo &rhs)  const { return val < rhs.val;  }
};

int Foo::foo_counter = 0;

//Create a hash function for Foo in order to use Foo with unordered_map
namespace std {
template<> struct hash<Foo> {
std::size_t operator()(const Foo &f) const {
return std::hash<int>{}(f.val);
}
};
}

int main()
{
std::unordered_map<Foo, int> umap;
Foo foo0, foo1, foo2, foo3;
int d;

std::cout << "\numap.insert(std::pair<Foo, int>(foo0, d))\n";
umap.insert(std::pair<Foo, int>(foo0, d));
//equiv. to: umap.insert(std::make_pair(foo0, d));

std::cout << "\numap.insert(std::move(std::pair<Foo, int>(foo1, d)))\n";
umap.insert(std::move(std::pair<Foo, int>(foo1, d)));
//equiv. to: umap.insert(std::make_pair(foo1, d));

std::cout << "\nstd::pair<Foo, int> pair(foo2, d)\n";
std::pair<Foo, int> pair(foo2, d);

std::cout << "\numap.insert(pair)\n";
umap.insert(pair);

std::cout << "\numap.emplace(foo3, d)\n";
umap.emplace(foo3, d);

std::cout << "\numap.emplace(11, d)\n";
umap.emplace(11, d);

std::cout << "\numap.insert({12, d})\n";
umap.insert({12, d});

std::cout.flush();
}

Вывод, который я получил, был:

Foo() with val:                0
Foo() with val:                1
Foo() with val:                2
Foo() with val:                3

umap.insert(std::pair<Foo, int>(foo0, d))
Foo(Foo &) with val:           4    created from:       0
Foo(Foo&&) moving:             4    and changing it to: 5
~Foo() destroying:             4

umap.insert(std::move(std::pair<Foo, int>(foo1, d)))
Foo(Foo &) with val:           6    created from:       1
Foo(Foo&&) moving:             6    and changing it to: 7
~Foo() destroying:             6

std::pair<Foo, int> pair(foo2, d)
Foo(Foo &) with val:           8    created from:       2

umap.insert(pair)
Foo(const Foo &) with val:     9    created from:       8

umap.emplace(foo3, d)
Foo(Foo &) with val:           10   created from:       3

umap.emplace(11, d)
Foo(int) with val:             11

umap.insert({12, d})
Foo(int) with val:             12
Foo(const Foo &) with val:     13   created from:       12
~Foo() destroying:             12

~Foo() destroying:             8
~Foo() destroying:             3
~Foo() destroying:             2
~Foo() destroying:             1
~Foo() destroying:             0
~Foo() destroying:             13
~Foo() destroying:             11
~Foo() destroying:             5
~Foo() destroying:             10
~Foo() destroying:             7
~Foo() destroying:             9

Заметить, что:

1. unordered_map всегда внутри магазинов Foo объекты (а не, скажем, Foo *s) в качестве ключей, которые все уничтожаются, когда unordered_map уничтожен Здесь unordered_mapВнутренние ключи были foos 13, 11, 5, 10, 7 и 9.

   • Так что технически наш unordered_map на самом деле магазины std::pair<const Foo, int> объекты, которые в свою очередь хранят Foo объекты. Но, чтобы понять «идею общей картины» о том, как emplace() отличается от insert() (см. выделенное поле ниже), это нормально временно представь это std::pair объект как полностью пассивный. Как только вы поймете эту «общую идею», важно сделать резервную копию и понять, как используется этот посредник. std::pair возражать unordered_map вводит тонкие, но важные, технические детали.

2. Вставка каждого из foo0, foo1, а также foo2 требуется 2 звонка на один из FooКопирование / перемещение конструкторов и 2 вызова FooДеструктор (как я сейчас опишу):

   а. Вставка каждого из foo0 а также foo1 создал временный объект (foo4 а также foo6соответственно), чей деструктор был вызван сразу после завершения вставки. Кроме того, внутренняя часть unordered_map Foos (которые являются foos 5 и 7) также вызывали свои деструкторы, когда unordered_map был уничтожен.

   б. Вставить foo2вместо этого мы сначала явно создали не временный объект пары (называемый pair), который называется FooКопируй конструктор на foo2 (создание foo8 как внутренний член pair). Мы тогда insert()редактировать эту пару, что привело к unordered_map снова вызывать конструктор копирования foo8) создать свою собственную внутреннюю копию (foo9). Как с foos 0 и 1, конечный результат — два вызова деструктора для этой вставки, с той лишь разницей, что foo8деструктор назывался только когда мы достигли конца main() вместо того, чтобы быть вызванным сразу после insert() законченный.

3. Emplacing foo3 в результате только 1 вызов конструктора копирования / перемещения (создание foo10 внутренне в unordered_map ) и только 1 звонок Fooдеструктор. (Я вернусь к этому позже).

4. За foo11мы напрямую передали целое число 11 в emplace(11, d) чтобы unordered_map позвонил бы Foo(int) Конструктор в то время как выполнение находится в пределах его emplace() метод. В отличие от (2) и (3), нам даже не нужно было предварительно выходить foo объект, чтобы сделать это. Важно отметить, что только 1 звонок на Foo конструктор произошел.

5. Затем мы напрямую передали целое число 12 в insert({12, d}), В отличие от emplace(11, d)этот призыв к insert({12, d}) привело к двум вызовам конструктора Foo.

Это показывает, в чем основная «большая картина» разницы между insert() а также emplace() является:

В то время как использование insert() почти всегда требует строительства или существования некоторых Foo объект в main()область действия (с последующим копированием или перемещением), если используется emplace() тогда любой вызов Foo Конструктор делается полностью внутри unordered_map (то есть в рамках emplace() определение метода). Аргумент (ы) для ключа, который вы передаете emplace() непосредственно направляются Foo вызов конструктора внутри unordered_map (необязательные дополнительные детали: где этот недавно построенный объект немедленно включается в один из unordered_mapпеременные-члены, так что при выходе из программы не вызывается деструктор emplace() и никакие конструкторы перемещения или копирования не называются).

Примечание: причина почти в почти всегда объясняется в I) ниже.

3. продолжение: причина звонка umap.emplace(foo3, d) называется Fooнеконстантный конструктор копирования следующий: так как мы используем emplace(), компилятор знает, что foo3 (неконстантный Foo объект) должен быть аргументом для некоторых Foo конструктор. В этом случае наиболее подходящим Foo Конструктор является неконстантной копией Foo(Foo& f2), Вот почему umap.emplace(foo3, d) называется конструктор копирования в то время как umap.emplace(11, d) не.

Эпилог:

I. Обратите внимание, что одна перегрузка insert() на самом деле эквивалентно emplace(), Как описано на этой странице cppreference.com, перегрузка template<class P> std::pair<iterator, bool> insert(P&& value) (который является перегрузкой (2) из insert() на этой странице cppreference.com) эквивалентно emplace(std::forward<P>(value)),

II. Куда пойти отсюда?

а. Поиграйте с приведенным выше исходным кодом и изучите документацию для insert() (например. Вот) а также emplace() (например. Вот) это найдено в Интернете. Если вы используете IDE, такую ​​как eclipse или NetBeans, вы можете легко заставить свою IDE сообщить вам, какая перегрузка insert() или же emplace() вызывается (в eclipse, просто удерживайте курсор мыши над вызовом функции на секунду). Вот еще немного кода, чтобы попробовать:

std::cout << "\numap.insert({{" << Foo::foo_counter << ", d}})\n";
umap.insert({{Foo::foo_counter, d}});
//but umap.emplace({{Foo::foo_counter, d}}); results in a compile error!

std::cout << "\numap.insert(std::pair<const Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<const Foo, int>({Foo::foo_counter, d}));
//The above uses Foo(int) and then Foo(const Foo &), as expected. but the
// below call uses Foo(int) and the move constructor Foo(Foo&&).
//Do you see why?
std::cout << "\numap.insert(std::pair<Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<Foo, int>({Foo::foo_counter, d}));
//Not only that, but even more interesting is how the call below uses all
// three of Foo(int) and the Foo(Foo&&) move and Foo(const Foo &) copy
// constructors, despite the below call's only difference from the call above
// being the additional { }.
std::cout << "\numap.insert({std::pair<Foo, int>({" << Foo::foo_counter << ", d})})\n";
umap.insert({std::pair<Foo, int>({Foo::foo_counter, d})});//Pay close attention to the subtle difference in the effects of the next
// two calls.
int cur_foo_counter = Foo::foo_counter;
std::cout << "\numap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}}) where "<< "cur_foo_counter = " << cur_foo_counter << "\n";
umap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}});

std::cout << "\numap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}}) where "<< "Foo::foo_counter = " << Foo::foo_counter << "\n";
umap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}});//umap.insert(std::initializer_list<std::pair<Foo, int>>({{Foo::foo_counter, d}}));
//The call below works fine, but the commented out line above gives a
// compiler error. It's instructive to find out why. The two calls
// differ by a "const".
std::cout << "\numap.insert(std::initializer_list<std::pair<const Foo, int>>({{" << Foo::foo_counter << ", d}}))\n";
umap.insert(std::initializer_list<std::pair<const Foo, int>>({{Foo::foo_counter, d}}));

Вы скоро увидите, что перегрузка std::pair конструктор (см. ссылка) в конечном итоге используется unordered_map может иметь важное влияние на количество копируемых, перемещаемых, создаваемых и / или уничтожаемых объектов и когда это происходит.

б. Посмотрите, что происходит, когда вы используете другой класс контейнера (например, std::set или же std::unordered_multiset) вместо std::unordered_map,

с. Теперь используйте Goo объект (просто переименованная копия Foo) вместо int как тип диапазона в unordered_map (т.е. использовать unordered_map<Foo, Goo> вместо unordered_map<Foo, int>) и посмотри сколько и какие Goo конструкторы называются. (Спойлер: эффект есть, но он не очень драматичен.)