Multimap vs map с множеством
Мне интересно, что более эффективно.
std::map< String, std::set<int> >
или
std::multimap< String, int >
EDIT:
Я не планирую делать что-то необычное с этими картами. Стандартная вставка, удаление, изменение, поиск. Размер каждого набора или многострочной строки не должен превышать 100.
Ответы
Ответ 1
Это, я считаю, зависит от реализации, но (un) образованное предположение:
На практике это зависит от количества целых чисел, которые вы будете хранить в multimap или std::set. A multimap, скорее всего, будет использовать линейный поиск значений после log (n) поиска ключа. Если у вас есть большое количество целочисленных значений, тогда поиск в журнале (n) ключей, за которым следует поиск (n) значений журнала, может быть немного быстрее.
Однако с точки зрения эффективности хранение чего-либо в map или multimap с помощью клавиши string почти наверняка перевешивает различия в обоих случаях.
Как сказано ниже, multimap, вероятно, будет более простым в использовании и более понятным для поддержания его явного преимущества.
Ответ 2
Опция "set" исключает дублирование пар символов + значение, не будет ли мультимап.
Ответ 3
Я не могу сказать точно, но, учитывая, что multimap был разработан для того, чтобы сделать то, что другое является выражением, должно быть лучше быть конкретным и использовать мультимап, он имеет гораздо больше смысла, он также имеет функции-члены для работы с мультимапом в качестве концепции эти функции были бы немного фанки, используя другой подход.
Ответ 4
станд:: MultiMap < String, int > , скорее всего, более эффективен с точки зрения памяти.
Ответ 5
Если вы до сих пор не довольны этими ответами (не говорите, что это не так), и я абсолютно вынужден ответить, я также дам свое образованное "предположение":
Чтобы вставить, мультимап выглядит более "эффективным". С помощью подхода карты вы сначала должны получить, а затем выполнить операцию на множестве.
Чтобы удалить/извлечь, карта выглядит более "эффективной".
Ответ 6
Они на самом деле не эквивалентны. A multimap<X,Y> позволяет хранить повторяющиеся пары ключ-значение, тогда как map<T, set<X>> не работает.
multimap<int, int> m;
m.insert(make_pair(2, 3));
m.insert(make_pair(2, 3)); // This changes the size of m!
В то время как
map<int, set<int>> m;
m[2].insert(3);
m[2].insert(3); // This does nothing.
Таким образом, я бы использовал установленный подход, если вам не нужны двойные пары ключ-значение. Синтаксис также приятнее. Я ожидаю, что разница в производительности и использовании памяти не так уж велика.
