Поведение std::map при обращении к ключу

Я пишу программу для численного моделирования, используя std::map для хранения некоторых пар ключ-значение. Карта используется для хранения состояний, возникших в ходе моделирования. Тип ключа — целое число, а значение соответствует ключу, который говорит, сколько копий существует для одних и тех же ключей, т. е. std::map. Для каждого шага моделирования мне нужно вычислить, сколько значений существует для одного и того же ключа, поэтому я проверю это с помощью следующего кода.

if (map[key]>0) {do something here with the number of copies}

Однако вскоре я обнаружил, что этот код не работает, потому что даже такого ключа на карте нет, всякий раз, когда вы вызываете map[key], он генерирует заполнитель для этого ключа и устанавливает значение равным нулю; поэтому я всегда пересчитываю общее количество ключей с помощью std::map.size(). Позже я изменил код следующим образом, чтобы вместо этого искать ключ

if (map.find(key)!=map.end()) {...}

Так это единственный и самый быстрый способ проверить, существует ли ключ для карты? Я собираюсь запускать симуляцию сотни миллионов раз, и она будет очень часто вызывать приведенный выше код для проверки ключа. Будет ли слишком медленно использовать вместо этого map.find()? Спасибо.


person user1285419    schedule 19.04.2012    source источник


Ответы (4)


Функция-член find, вероятно, является самым быстрым способом узнать, находится ли ключ уже на карте. Тем не менее, если вам не нужно перебирать элементы на карте по порядку, вы можете повысить производительность с помощью std::unordered_map.

person Jerry Coffin    schedule 19.04.2012
comment
… для int ключей и значений следует также рассмотреть простой массив со случайными отсутствующими (неиспользуемыми) элементами. - person Potatoswatter; 19.04.2012
comment
Благодарю. Да, я тоже думал использовать массив. Но в моем алгоритме для некоторых условий мне нужно довольно часто удалять/вставлять ключи, поэтому общая длина варьируется. - person user1285419; 19.04.2012

В std::map или хеш-таблице (std::unordered_map) функция find работает очень быстро, так же быстро, как и оператор подписки []. На самом деле, это быстрее, когда элемент не найден, потому что его не нужно вставлять.

person Ben Voigt    schedule 19.04.2012
comment
спасибо, кажется, что unordered_map - это одно из решений. Таким образом, единственная разница между map и unordered_map заключается в том, что ключ не отсортирован динамически, верно? - person user1285419; 19.04.2012
comment
@ user1285419: Это единственная разница в использовании. Внизу они хранятся совершенно по-разному (std::map — сбалансированное дерево, а std::unordered_map — хэш-таблица). - person Ben Voigt; 19.04.2012

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

Кстати: меня заинтересовала скорость простого массива, вектора, карты и неупорядоченной карты. Я написал простую программу, которая делает 100000000 container[n]++, где n — случайное число в диапазоне от 0 до 10000. Результаты:

  • массив: 1,27 с
  • вектор: 1,36 с
  • неупорядоченная карта: 2,6 с
  • map: 11,6 с Накладные расходы цикла + расчет индекса в этом простом случае составляют ~ 0,8 с.

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

person dbrank0    schedule 19.04.2012
comment
Я ценю, что вы потратили время, чтобы показать мне данные. Я думаю, что это дает мне некоторое направление, какую структуру я полагаю использовать в моем случае. - person user1285419; 19.04.2012

вы можете использовать hash_map, это самые быстрые структуры данных для вашего типа ключ-значение;

также вы можете использовать карту, но она медленнее, чем hash_map

person argue2000    schedule 19.04.2012