Какой способ присвоения значений карте наиболее эффективен? Или они все оптимизированы под один и тот же код (на большинстве современных компиляторов)?
// 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 самый быстрый