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

Оба достигают разных целей.

m[key] = val;

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

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

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

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

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

#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

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

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

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

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

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

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

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

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

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

вставить (make_pair ‹>) | 26100 циклов

Он показывает величину штрафа, добавленного из-за копирования. Конечно, CPP11 изменит картину.

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

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

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

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

Мой ответ не об эффективности, а о безопасности, которая имеет отношение к выбору алгоритма вставки:

Вызовы [] и insert() вызовут деструкторы элементов. Это может иметь опасные побочные эффекты, если, скажем, у ваших деструкторов есть критическое поведение внутри.

После такой опасности я перестал полагаться на неявные функции отложенной вставки STL и всегда использую явные проверки, имеют ли мои объекты поведение в своих ctors / dtors.

См. Этот вопрос: Деструктор вызвал объект при добавлении это в std :: list