C ++: value_type по сравнению с make_pair, который быстрее для вставки карты?

Question

typedef map<KeyType, ValType> KVMap;
KVMap kvmap;

kvmap.insert( KVMap::value_type( key, val ) );
kvmap.insert( make_pair( key, val ) );

Какой из перечисленных выше вариантов для вставки в карту STL всегда быстрее? Почему?

Примечание. Мне хорошо известно, что insert() быстрее, чем использование []= для добавления (не обновления) пар ключ-значение на карту. Пожалуйста, предположите, что мой запрос о добавлении, а не обновлении. Поэтому я ограничил это insert().

Answer 1

Скорее всего, первое будет 'epsilon-fast' , из-за этого (из 23.3.1 в стандарте):

typedef pair<const Key, T> value_type;

[...]

pair<iterator, bool> insert(const value_type& x);

• В первой версии вы напрямую создаете соответствующий тип, ожидаемый как std::map<K,V>::insert

• Во второй версии выполняется преобразование с использованием std::pair конструктора шаблона. Действительно, std::make_pair, скорее всего, выведет свои аргументы шаблона в KeyType и ValType, возвращая, таким образом, std::pair<KeyType, ValType>.

  Это не соответствует типу параметра std::map<K,V>::insert, который равен std::pair<const KeyType, ValType> (разница заключается в том, что const квалифицируется первым). Конструктор преобразования std::pair будет использоваться для создания std::pair<const K, V> из std::pair<K, V>.

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

Answer 2

На самом деле есть аргумент для value_type более make_pair. Это связано с тем, что по разным непонятным причинам make_pair принимает свои аргументы по значению. С другой стороны, у value_type, псевдонима для std::pair<const Key, value>, будет вызываться его конструктор с аргументами, передаваемыми константной ссылкой. Потенциальная потеря эффективности из-за передачи по значению в make_pair по сравнению с передачей по ссылке, что теоретически может оказать заметное влияние на вашу программу.

Другая проблема, о которой следует беспокоиться с make_pair, заключается в том, что make_pair обычно создает пару типа std::pair<Key, Value> против std::pair<const Key, Value>, необходимого внутри map. Это означает, что может быть сделана еще одна ненужная копия, на этот раз pair для правильной работы преобразования.

Короче говоря, использование make_pair может привести к созданию двух совершенно ненужных копий ключа и значения, в то время как использование конструктора value_type не имеет ни одной.

Answer 3

Это всего лишь дополнение.

insert( make_pair(...) ) вызывает конструктор копирования 4 раза условно по причине, упомянутой другими ответчиками.

insert( value_type(...) ) вызывает конструктор копирования 2 раза.

operator[] вызывает конструктор по умолчанию один раз и копирует конструктор 2 раза в типичной реализации.конструктор по умолчанию вызывается внутри operator[] для insert( value_type( ..., mapped_type() ) ).Конструктор копирования вызывается один раз для копирования аргумента insert() (pair) и один раз для конструирования копии внутреннего узла карты.

Итак, если вы используете insert с make_pairНельзя сказать, что insert всегда быстрее, чем operator[] даже для добавления.Возможно, это зависит от ситуации.Как вы, возможно, знаете, с учетом вышесказанного для нового стандарта было предложено emplace.

Answer 4

Это принципиально одно и то же. KVMap::value_type - это typedef для std::pair<KeyType, ValType>, так что это просто вызов конструктора. std::make_pair - это функция шаблона, которая просто вызывает конструктор (она существует, потому что типы шаблонов могут быть выведены для свободных функций, но не для конструкторов). После того, как все невероятно стандартные оптимизации сделаны, нет никаких причин для различий.

Я не знаю, как вы тестируете, но есть много, много способов сделать это неправильно.

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