Векторная или многокарточная дилемма

Question

У меня есть дилемма: иметь ли multimap <int key, int value> или поддерживать вектор, содержащий вектор всех значений, соответствующих ключу int.

Меня интересует, что работает быстрее при поиске значений для определенной клавиши int.

Answer 1

Забудьте, что "быстрее".Вы можете профилировать это позже, но не зацикливайтесь на этом.Гораздо важнее то, что один подход дает вам скудное хранилище, а другой нет - сосредоточьтесь на этом и решите, какой из них наиболее подходит для вашей проблемы.

Answer 2

Если вы хотите multimap, а не просто map, альтернативой, вероятно, будет vector< list<int> > или что-то подобное (на самом деле multimap более или менее map с list тип элемента).

В общем, поиск vector быстрее: это O(1) для массива против O(log n) для карты (в обоих случаях я не считаю поиск в list / vector / set / все, что используется для "мульти" части). Но , чтобы использовать vector, вы должны сделать его таким же большим, как самый большой ключ int, который вы хотите использовать; если ваши ключи последовательные, это не проблема, но если ваш индекс редкий, multimap может быть лучшим выбором.

С другой стороны, если вам не нужен упорядоченный обход, unordered_multimap (который на самом деле является хеш-таблицей) может быть лучшим из обоих миров: вы получаете поиск в виде массива O(1) без необходимости сохранять огромный пустой массив.

Answer 3

Я бы сказал, если ваши ключи последовательно идут с вектором, но если в ваших ключах есть большие дыры, то карта будет лучше (так как вам не нужно будет хранить «пустые» записи, как в вашем векторе), Кроме того, вам будет проще сосчитать, сколько у вас записей и т. д. Векторы, основанные на производительности, основаны на массивах, поэтому поиск, как правило, выполняется быстрее (поскольку для поиска карты должны пройти через несколько фрагментов данных).

Answer 4

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

Answer 5

Я бы порекомендовал map<int, vector<int>>

Поскольку после выполнения поиска по карте у вас есть вектор со всеми значениями.

В противном случае вашему решению потребуется новый поиск каждого значения