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

193

Я впервые использую карты и понял, что есть много способов вставить элемент. Вы можете использовать emplace(), operator[]или insert(), плюс варианты, такие как использование value_typeили make_pair. Хотя есть много информации обо всех из них и вопросы о конкретных случаях, я до сих пор не могу понять общую картину. Итак, два моих вопроса:

  1. В чем преимущество каждого из них перед остальными?

  2. Была ли необходимость в добавлении emplace к стандарту? Есть ли что-то, что было бы невозможно без этого раньше?

Немецкий капуано
источник
1
Семантика размещения допускает явные преобразования и прямую инициализацию.
Kerrek SB
3
Сейчас operator[]основано на try_emplace. Стоит также упомянуть insert_or_assign.
FrankHB
@FrankHB, если вы (или кто-то еще) добавите актуальный ответ, я мог бы изменить принятый.
Немец Капуано

Ответы:

230

В частном случае карты старых вариантов было только два: operator[] и insert(разныеinsert ). Поэтому я начну объяснять это.

operator[]Является находкой или, добавить оператор. Он попытается найти элемент с заданным ключом внутри карты и, если он существует, вернет ссылку на сохраненное значение. Если этого не произойдет, он создаст новый элемент, вставленный на место с инициализацией по умолчанию, и вернет ссылку на него.

insertФункция (в единственном элементе аромата) занимает value_type( std::pair<const Key,Value>), он использует ключ ( firstэлемент) и пытается вставить ее. Потому std::mapчто не допускает дублирования, если есть существующий элемент, он ничего не вставит.

Первое различие между ними заключается в том, что operator[]необходимо иметь возможность создавать инициализированное значение по умолчанию , и поэтому оно непригодно для типов значений, которые не могут быть инициализированы по умолчанию. Второе различие между ними заключается в том, что происходит, когда уже есть элемент с данным ключом. insertФункция не будет изменять состояние карты, но вместо того, чтобы вернуть итератор к элементу (и falseо том , что она не была установлена).

// assume m is std::map<int,int> already has an element with key 5 and value 0
m[5] = 10;                      // postcondition: m[5] == 10
m.insert(std::make_pair(5,15)); // m[5] is still 10

В случае insertаргумента это объект value_type, который может быть создан по-разному. Вы можете напрямую сконструировать его с соответствующим типом или передать любой объект, из которого value_typeможет быть сконструирован объект , и именно здесь он std::make_pairвступает в игру, поскольку он позволяет легко создавать std::pairобъекты, хотя это, вероятно, не то, что вы хотите ...

Чистый эффект от следующих вызовов аналогичен :

K t; V u;
std::map<K,V> m;           // std::map<K,V>::value_type is std::pair<const K,V>

m.insert( std::pair<const K,V>(t,u) );      // 1
m.insert( std::map<K,V>::value_type(t,u) ); // 2
m.insert( std::make_pair(t,u) );            // 3

Но на самом деле это не одно и то же ... [1] и [2] на самом деле эквивалентны. В обоих случаях код создает временный объект того же типа ( std::pair<const K,V>) и передает его insertфункции. insertФункция создает соответствующий узел в бинарном дереве поиска , а затем скопировать value_typeчасть из аргумента в узел. Преимущество использования value_typeв том, что, ну, value_typeвсегда совпадает value_type , вы не можете неправильно набирать тип std::pairаргументов!

Разница в [3]. Функция std::make_pairпредставляет собой шаблонную функцию, которая создаст std::pair. Подпись:

template <typename T, typename U>
std::pair<T,U> make_pair(T const & t, U const & u );

Я намеренно не предоставил аргументы шаблона std::make_pair, так как это обычное использование. И подразумевается, что аргументы шаблона выводятся из вызова, в данном случае T==K,U==V, так что вызов std::make_pairвозвратит std::pair<K,V>(обратите внимание на отсутствие const). Для подписи требуется, value_typeчтобы она была близка, но не совпадала с возвращаемым значением из вызова std::make_pair. Поскольку он достаточно близко, он создаст временный объект правильного типа и скопирует его, инициализирует. Это, в свою очередь, будет скопировано в узел, создав в общей сложности две копии.

Это можно исправить, указав аргументы шаблона:

m.insert( std::make_pair<const K,V>(t,u) );  // 4

Но это все равно подвержено ошибкам так же, как и явная типизация в случае [1].

До этого момента у нас были разные способы вызова, insertкоторые требуют value_typeвнешнего создания и копирования этого объекта в контейнер. В качестве альтернативы вы можете использовать, operator[]если тип является конструируемым и назначаемым по умолчанию (преднамеренно фокусируясь только в m[k]=v), и это требует инициализации по умолчанию одного объекта и копии значения в этот объект.

В C ++ 11 с использованием шаблонов с переменным числом строк и совершенной пересылки существует новый способ добавления элементов в контейнер посредством размещения (создания на месте). Эти emplaceфункции в различных контейнерах делают в основном то же самое: вместо того , чтобы получить источник , из которого скопировать в контейнер, функция принимает параметры , которые будут переданы в конструктор объекта , хранящегося в контейнере.

m.emplace(t,u);               // 5

В работе [5], std::pair<const K, V>не создаются и передаются emplace, а скорее ссылки на tи uобъект передаются , emplaceкоторый пересылает их в конструктор value_typeподобъекта внутри структуры данных. В этом случае нет Копии std::pair<const K,V>не выполняются вообще, что является преимуществом emplaceнад C ++ 03 альтернатив. Как и в случае с insertним не будет переопределять значение на карте.


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

Дэвид Родригес - дрибеи
источник
5
Это указывается в ответе, но map [] = val перезапишет предыдущее значение, если оно существует.
dk123
более интересный вопрос в моем смысле, это то, что это служит небольшой цели. Потому что вы сохраняете парную копию, что хорошо, потому что ни одна парная копия не означает никакой mapped_typeкопии. То, что мы хотим, это наложить конструкцию mapped_typeпары в и наложение пары на карту. Следовательно, std::pair::emplaceфункция и ее поддержка пересылки map::emplaceотсутствуют. В его текущей форме вам все равно придется передать созданный mapped_type в конструктор пары, который скопирует его один раз. это лучше, чем в два раза, но все равно ничего хорошего.
v.oddou
на самом деле я исправляю этот комментарий, в C ++ 11 есть конструктор пар шаблонов, который служит точно такой же цели, как emplace в случае конструирования с 1 аргументом. и какая-то странная кусочная конструкция, как они ее называют, использующая кортежи для пересылки аргументов, так что, похоже, у нас все еще может быть идеальная пересылка.
v.oddou
Похоже, есть ошибка производительности вставки в unordered_map и map: ссылка
Deqing
1
Возможно, было бы неплохо обновить эту информацию информацией insert_or_assignи try_emplace(оба из C ++ 17), которые помогают заполнить некоторые пробелы в функциональности существующих методов.
ShadowRanger
15

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, он игнорирует их основное назначение - создание объектов.

ChrisCM
источник
4
« Не было необходимости в добавлении emplace к стандарту». Это явно ложно. emplace()это просто единственный способ вставить элемент, который нельзя скопировать или переместить. (& да, возможно, наиболее эффективно вставить тот, чьи конструкторы копирования и перемещения стоят намного дороже, чем конструирование, если такая вещь существует) Также кажется, что вы ошиблись: это не о том, чтобы " воспользоваться преимуществом ссылки на rvalue" использовать реальные объекты, которые вы уже создали "; ни один объект не создан, и вы перенаправлять mapаргументы он должен создать его внутри себя. Вы не делаете объект.
underscore_d
10

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

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

#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
}

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

Керрек С.Б.
источник
Представьте, что foo требуется два целых числа в ctor, а не один. Сможете ли вы использовать этот звонок? v.emplace(v.end(), 10, 10); ... или вам теперь нужно использовать v.emplace(v.end(), foo(10, 10) ); :?
Kaitain
У меня нет доступа к компилятору прямо сейчас, но я предполагаю, что это означает, что обе версии будут работать. Почти все примеры, которые вы видите, emplaceиспользуют класс, который принимает один параметр. ИМО, это на самом деле сделало бы природу вариабельного синтаксиса emplace более понятным, если бы в параметрах использовались несколько параметров.
Kaitain
9

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

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

//Foo simply outputs what constructor is called with what value.
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;

    //Print the statement to be executed and then execute it.

    std::cout << "\numap.insert(std::pair<Foo, int>(foo0, d))\n";
    umap.insert(std::pair<Foo, int>(foo0, d));
    //Side note: 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)));
    //Side note: 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. An unordered_mapвсегда внутренне хранит Fooобъекты (а не, скажем, Foo *с) как ключи, которые все уничтожены , когда 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, соответственно), чей деструктор был вызван сразу после завершения вставки. Кроме того, внутренним Foos в unordered_map (которые являются Foo5 и 7) также были вызваны их деструкторы, когда unordered_map был уничтожен.

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

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

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

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

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

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

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

  1. продолжение: причина, по которой вызывается 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конструкторы вызваны. (Спойлер: эффект есть, но он не очень драматичен.)

Мэтью К.
источник
0

С точки зрения функциональности или выхода, они оба одинаковы.

Для больших объемов памяти объект emplace оптимизирован для памяти, в котором не используются конструкторы копирования

Для простого подробного объяснения https://medium.com/@sandywits/all-about-emplace-in-c-71fd15e06e44

frostcs
источник