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

Question

Мои данные концептуально выглядят так:

"BLUE" :  (3 , 10,  15, 1220,  44040)
"RED"  :  (44, 523,  122143,  323233)
"BANANA" : (....)

Время сборки не важно. Для поиска, где у меня есть несколько ключей, где я хочу объединить все списки значений и отсортировать их; я должен представить это как карту или мультикарту в C ++ для быстрого результата?

Другими словами, поскольку векторы значений, прикрепленные к ключам, имеют переменную длину, я должен иметь карту с ключом: вектор или мультикарту с ключом1: int1, ключ1: int2 и т. Д.?

Цель состоит в том, чтобы написать функцию, в которой input = (key1, ...., keyN), а вывод представляет собой отсортированный список всех значений.

Answer 1

Если вы собираетесь заполнять только один раз перед поиском, лучший способ - это вектор, который вы сортируете после заполнения: vector<pair<string, int> >.

Answer 2

Решение map<string, vector<int>> проще для понимания и кодирования, и, возможно, более эффективное с точки зрения пространства, поскольку вы размещаете группы значений в непрерывном хранилище, а не создаете узел для каждого значения.По той же причине это, вероятно, также более эффективно алгоритмически.