Эффективность вставки карты STL: [] против вставки - PullRequest
Новая
       50

Эффективность вставки карты STL: [] против вставки

15 голосов
/ 17 апреля 2011

Существует два способа вставки карты: 

m[key] = val;

Или 

m.insert(make_pair(key, val));

У меня вопрос, какая операция быстрее? Люди обычно говорят, что первый медленнее, потому что стандарт STL сначала «вставляет» элемент по умолчанию, если «key» не существует на карте, а затем назначает «val» элементу по умолчанию.

Но я не вижу, что второй способ лучше из-за 'make_pair'. make_pair на самом деле является удобным способом создать пару по сравнению с pair<T1, T2>(key, val). В любом случае, они оба выполняют два назначения: одно присваивает «ключ» для «pair.first», а второе - «val» для «pair.second». После создания пары карта вставляет элемент, инициализированный как «pair.second».

Итак, первый способ - это 1. 'default construct of typeof(val)' 2. назначение второй способ - это 1. назначение 2. 'copy construct of typeof(val)'

Ответы [ 5 ]

18 голосов
/ 17 апреля 2011

Оба выполняют разные вещи.

m[key] = val;

Вставит новую пару ключ-значение, если key еще не существует, или перезапишет старое значение, сопоставленное с key, если оно уже существует.

m.insert(make_pair(key, val));

Вставит пару только в том случае, если key еще не существует, она никогда не перезапишет старое значение.Итак, выберите соответственно тому, что вы хотите достичь.
На вопрос, что более эффективно: профиль.: P Наверное, первый способ, который я бы сказал, хотя.Назначение (иначе копия) имеет место для обоих способов, поэтому единственная разница заключается в построении.Как все мы знаем и должны реализовать, конструкция по умолчанию должна быть в основном неактивной и, следовательно, очень эффективной.Копия это именно то - копия.Таким образом, одним способом мы получаем «без операции» и копию, а вторым способом мы получаем две копии.
Редактировать : В конце концов, доверяйте тому, что говорит вам ваше профилирование.Мой анализ был неудачным, как @Matthieu упоминает в своем комментарии, но это было мое предположение.:)

Тогда у нас будет C ++ 0x, и двойная копия на втором пути будет нулевой, так как пара теперь может быть просто перемещена.Так что, в конце концов, я думаю, что это возвращается к моему первому пункту: используйте правильный путь, чтобы выполнить то, что вы хотите сделать.

5 голосов
/ 17 апреля 2011

В слегка загруженной системе с большим объемом памяти этот код: 

#include <map>
#include <iostream>
#include <ctime>
#include <string>

using namespace std;

typedef map <unsigned int,string> MapType;
const unsigned int NINSERTS = 1000000;

int main() {
    MapType m1;
    string s = "foobar";
    clock_t t = clock();
    for ( unsigned int i = 0; i < NINSERTS; i++ ) {
        m1[i] = s;
    }
    cout << clock() - t << endl;
    MapType m2;
    t = clock();
    for ( unsigned int i = 0; i < NINSERTS; i++ ) {
        m2.insert( make_pair( i, s ) );
    }
    cout << clock() - t << endl;
}

производит: 

1547
1453

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

2 голосов
/ 22 апреля 2015

По производительности я думаю, что они в основном одинаковы. Могут быть некоторые исключения для карты с большими объектами, в этом случае вы должны использовать [] или возможно использовать emplace, который создает меньше временных объектов, чем «insert». Подробнее см. Обсуждение здесь .

Однако в особых случаях вы можете получить повышение производительности, если используете оператор «подсказка» в операторе вставки. Итак, глядя на вариант 2 из здесь : 

iterator insert (const_iterator position, const value_type& val);

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

0 голосов
/ 15 марта 2017

Мой взгляд на это: Напомним, что карты - это сбалансированное двоичное дерево, большинство модификаций и проверок требуют O (logN).

Действительно зависит от проблемы, которую вы пытаетесь решить.

1) если вы просто хотите вставить значение, зная, что его еще нет, тогда [] сделал бы две вещи: а) проверить, есть ли товар там или нет б) если его там нет, создадим пару и сделаем то, что делает вставка ( двойная работа O (logN)), поэтому я бы использовал insert.

2) если вы не уверены, есть ли он там или нет, то а) если вы действительно проверили, есть ли предмет, выполнив что-то вроде if (map.find (item) == mp.end ()) из строк выше где-то, затем используйте вставку, потому что двойная работа [] будет выполнять б), если вы не проверяли, то это зависит, потому что вставка не будет изменять значение, если оно есть, [] будет, в противном случае они равно

0 голосов
/ 21 ноября 2014

Мы должны уточнить анализ, упомянув, что относительная производительность зависит также от типа (размера) копируемых объектов.

Я провел аналогичный эксперимент (с nbt) с картой (int -> set). Я знаю, что это ужасно, но показательно для этого сценария. «Значение», в данном случае набор целых, содержит 20 элементов.

Я выполняю миллион итераций [] = Vs. вставьте операции и выполните RDTSC / iter-count.

[] = установить | 10731 циклов

insert (make_pair <>) | 26100 циклов

Показывает величину штрафа, добавленного за копирование. Конечно, CPP11 (переместить ctor's) изменит картинку.

...