медленный std :: карта для больших записей

Question

В этом формате у нас есть 48,16,703 записей.

1 abc
2 def
...
...
4816702 blah
4816703 blah_blah

Поскольку количество записей достаточно велико, я беспокоюсь, что std :: map займет много времени во время вставки, так как это нужно сделатьбалансировка также для каждой вставки.

Только вставка этих записей в карту занимает много времени.Я делаю

map[first] = second;

Два вопроса: 1. Правильно ли я использую std :: map для подобных случаев?2. Правильно ли я вставил, как указано выше.ИЛИ Должен ли я использовать map.insert ()

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

Кроме того, они не всегда являются последовательными ключами ..

PS Конечно, позже нам потребуется также получить доступ к этой карте, чтобы получить значения, соответствующие ключам.

Answer 1

Если после этого вам не нужно вставлять карту, вы можете создать несортированный вектор ваших данных, отсортировать его по ключу, а затем выполнить поиск с помощью таких функций, как std::equal_range.
Это такая же сложностькак std::map, но гораздо меньше ассигнований.

Answer 2

Используйте std::unordered_map, который имеет намного лучшую сложность времени вставки, чем std::map, в качестве ссылки упоминается:

Complexity

Single element insertions:
    Average case: constant.
    Worst case: linear in container size.

Multiple elements insertion:
    Average case: linear in the number of elements inserted.
    Worst case: N*(size+1): number of elements inserted times the container size plus one.

May trigger a rehash (not included in the complexity above).

Это лучше, чемсложность логарифмического времени при вставке std::map.

Примечание: при вставке std::map может использоваться " амортизированная константа, если дана подсказка и заданная позиция является оптимальной.».Если это так, то используйте карту (если вектор не применим).

@ nm предоставляет репрезентативную живую демонстрацию