Самый эффективный способ присвоения значений картам
Какой способ присвоения значений карте наиболее эффективен? Или они все оптимизированы под один и тот же код (на большинстве современных компиляторов)?
// 1) Assignment using array index notation
Foo["Bar"] = 12345;
// 2) Assignment using member function insert() and STL pair
Foo.insert(std::pair<string,int>("Bar", 12345));
// 3) Assignment using member function insert() and "value_type()"Foo.insert(map<string,int>::value_type("Bar", 12345));
// 4) Assignment using member function insert() and "make_pair()"Foo.insert(std::make_pair("Bar", 12345));
(Я знаю, что мог бы сравнить и проверить вывод компилятора, но этот вопрос возник сейчас, и единственное, что у меня есть под рукой, это мой мобильный телефон … хе-хе)
Решение
Во-первых, между семантическими различиями [] а также insert:
[]будут замещать старое значение (если есть)insertбудут игнорировать новое значение (если старое значение уже присутствует)
поэтому сравнивать их в общем бесполезно.
Относительно версий вкладышей:
std::map<std::string, int>::value_typeявляетсяstd::pair<std::string const, int>так что нет (важная) разница между 3 и 4std::make_pair("Bar", 12345)дешевле чемstd::pair<std::string, int>("Bar", 12345)посколькуstd::stringтип является полноценным классом с операциями, которые нужно делать при копировании и"Bar"это просто строковый литерал (таким образом, просто копия указателя); Однако, так как в конце вам нужно создатьstd::string… это будет зависеть от качества вашего компилятора
В общем, я бы порекомендовал:
[]для обновленияinsert(std::make_pair())за игнорирование дубликатов
std::make_pair он не только короче, но и соответствует принципу СУХОЙ: не повторяйте себя.
Для полноты, самый быстрый (и самый простой) будет emplace (C ++ 11 включен):
map.emplace("Bar", 12345);
Его поведение таково insert, но он создает новый элемент на месте.
Другие решения
1) может быть немного медленнее, чем другие методы, потому что std::map::operator[] сначала по умолчанию — создает объект, если он еще не существует, затем возвращает ссылку, которую вы можете использовать operator= чтобы установить желаемое значение, то есть две операции.
2-4) должен быть эквивалентен, так как map::value_type является typedef для std::pair для одних и тех же типов, и, следовательно, make_pair также эквивалентно. Компилятор должен относиться к ним одинаково.
Также обратите внимание, что производительность может быть увеличена еще больше, если вам нужно как проверить наличие (например, выполнить специальную логику в зависимости от того, существует она или нет), а затем также вставить ее, используя map::lower_bound сначала получить подсказку, где должен быть элемент, так map::insert не нужно искать весь map снова:
// get the iterator to where the key *should* be if it existed:
std::map::iterator hint = mymap.lower_bound(key);
if (hint == mymap.end() || mymap.key_comp()(key, hint->first)) {
// key didn't exist in map
// special logic A here...
// insert at the correct location
mymap.insert(hint, make_pair(key, new_value));
} else {
// key exists in map already
// special logic B here...
// just update value
hint->second = new_value;
}
Ваша первая возможность: Foo["Bar"] = 12345; имеет несколько другую семантику, чем другие — он вставит новый объект, если ни один не существует (как другие), но затирать текущее содержимое, если оно не существует (где другие используют insert потерпит неудачу, если этот ключ уже присутствует).
Что касается скорости, она может быть медленнее других. Когда вы вставляете новый объект, он создает пару с указанным ключом и сконструированным по умолчанию значением value_type, а затем назначает правильный value_type впоследствии. Все остальные создают для пары правильный ключ и значение и вставляют этот объект. Однако, по справедливости, мой опыт заключается в том, что разница редко бывает существенной (с более старыми компиляторами она была более значимой, но с более новыми довольно минимальными).
Следующие два эквивалентны друг другу. Вы просто используете два разных способа назвать один и тот же тип. По времени выполнения между ними нет никакой разницы.
Четвертый использует шаблонную функцию (make_pair), которая теоретически мог привлекать дополнительный уровень вызова функции. Я был бы очень удивлен, увидев реальное отличие от этого, за исключением (возможно), если бы вы были осторожны, чтобы компилятор сделал абсолютно нет оптимизация (особенно встраивание) вообще.
Итог: первый часто будет немного медленнее остальных (но не всегда и не намного). Остальные три почти всегда будут равны (как в: обычно ожидают, что любой разумный компилятор выдаст идентичный код для всех трех), даже если есть четкое теоретическое обоснование того, что четвертый медленнее.
Если в этом ключевом месте нет объекта, то:
std::map::emplace является наиболее эффективным. insert является вторым (но будет очень близко). [] наименее эффективен.
[], если там нет объекта, тривиальные конструируют его. Затем звонит operator=,
insert вызывает ли конструктор копирования std::pair аргумент.
Тем не менее, в случае карт, map.insert( make_pair( std::move(key), std::move(value) ) ) будет близко к map.emplace( std::move(key), std::move(value) ),
Если в ключевом месте есть объект, то [] позвоню operator=, в то время как insert/emplace уничтожит старый объект и создаст новый. [] может легко быть дешевле в этом случае.
В конце концов, это зависит от того, что ваш operator= против копирования-конструирования против тривиального-конструктора против деструктора — затраты на ваш ключ и ценность.
Фактическая работа ищет вещи в древовидной структуре std::map будет так близко к идентичности, это не смешно.
Третий — лучший выбор (ИМХО), но 2, 3 и 4 равны.
// 3) Assignment using member function insert() and "value_type()"Foo.insert(map<string,int>::value_type("Bar", 12345));
Почему я думаю, что третий — лучший выбор: вы выступаете только один операция для вставки значения: просто вставка (ну, есть и поиск), и вы можете узнать, было ли введено значение, проверяя second Член возвращаемого значения и реализация дает право не перезаписывать значение.
Использование value_type также имеет свои преимущества: вам не нужно знать сопоставленный тип или тип ключа, что полезно при программировании на основе шаблонов.
Худшее (ИМХО) первое
// 1) Assignment using array index notation
Foo["Bar"] = 12345;
Вы звоните std::map::operator[] который создает объект и возвращает ссылку на него, затем сопоставленный объект operator = называется. Вы делаете две операции для вставки: сначала вставка, затем присвоение.
И у него есть еще одна проблема: вы не знаете, было ли значение вставлено или перезаписано.
Даже при том, что уже было несколько хороших ответов, я подумал, что я мог бы также сделать быстрый тест. Пробежал каждый 5 миллионов раз и использовал хронологию c ++ 11 для измерения времени, которое потребовалось.
Вот код:
#include <string>
#include <map>
#include <chrono>
#include <cstdio>
// 5 million
#define times 5000000
int main()
{
std::map<std::string, int> foo1, foo2, foo3, foo4, foo5;
std::chrono::steady_clock::time_point timeStart, timeEnd;
int x = 0;
// 1) Assignment using array index notation
timeStart = std::chrono::steady_clock::now();
for (x = 0; x <= times; x++)
{
foo1[std::to_string(x)] = 12345;
}
timeEnd = std::chrono::steady_clock::now();
printf("1) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());
// 2) Assignment using member function insert() and STL pair
timeStart = std::chrono::steady_clock::now();
for (x = 0; x <= times; x++)
{
foo2.insert(std::pair<std::string, int>(std::to_string(x), 12345));
}
timeEnd = std::chrono::steady_clock::now();
printf("2) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());
// 3) Assignment using member function insert() and "value_type()"timeStart = std::chrono::steady_clock::now();
for (x = 0; x <= times; x++)
{
foo3.insert(std::map<std::string, int>::value_type(std::to_string(x), 12345));
}
timeEnd = std::chrono::steady_clock::now();
printf("3) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());
// 4) Assignment using member function insert() and "make_pair()"timeStart = std::chrono::steady_clock::now();
for (x = 0; x <= times; x++)
{
foo4.insert(std::make_pair(std::to_string(x), 12345));
}
timeEnd = std::chrono::steady_clock::now();
printf("4) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());
// 5) Matthieu M.'s suggestion of C++11's emplace
timeStart = std::chrono::steady_clock::now();
for (x = 0; x <= times; x++)
{
foo5.emplace(std::to_string(x), 12345);
}
timeEnd = std::chrono::steady_clock::now();
printf("5) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());
return 0;
}
Выход за 5 миллионов итераций:
1) took 23448 milliseconds
2) took 22854 milliseconds
3) took 22372 milliseconds
4) took 22988 milliseconds
5) took 21356 milliseconds
Версия GCC:
g++ (Built by MinGW-builds project) 4.8.0 20121225 (experimental)
Моя машина:
Intel i5-3570k overclocked at 4.6 GHz
EDIT1: исправил код и переделал тест.
РЕДАКТИРОВАТЬ 2: Добавлено предложение Мэтью М. для emplace C ++ 11, и он прав, emplace самый быстрый
detector