Multimap против карты с множеством

Question

Мне интересно, что более эффективно.

std::map< String, std::set<int> >

или

std::multimap< String, int >

EDIT: Я не планирую делать что-то необычное с этими картами. Стандартная вставка, удаление, изменение, поиск. Размер каждого набора или строки с несколькими ключами не должен превышать 100.

Answer 1

Я считаю, что это зависит от реализации, но (не) образованное предположение:

На практике это зависит от количества целых чисел, которые вы будете хранить в multimap или std::set. multimap, скорее всего, будет использовать линейный поиск значений после логарифмического (n) поиска ключа. Если у вас есть большое количество целочисленных значений, то поиск в журнале (n) ключей с последующим поиском в журнале (n) значений может быть немного быстрее.

Однако с точки зрения эффективности хранение чего-либо в map или multimap с помощью клавиши string почти наверняка перевесит различия в любом случае.

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

Answer 2

Опция "set" устранит дублирование пар ключ + значение, независимо от того, не будет ли мультикарта.

Answer 3

Если вы до сих пор не удовлетворены этими ответами (не говоря о том, что это не так), и я абсолютно вынужден ответить, я тоже дам свое образованное «предположение»:

Для вставки мультикарта выглядит более «эффективной». При использовании картографического подхода сначала необходимо извлечь, а затем выполнить операцию на съемочной площадке. Для удаления / извлечения карта кажется более «эффективной».

Answer 4

std :: multimap , скорее всего, более эффективно использует память.

Answer 5

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

Answer 6

Они на самом деле не эквивалентны в любом случае. 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.

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