Примеры использования std::multimap

Question

Я не совсем понимаю цель этой структуры данных. В чем разница между std::multimap<K, V> а также std::map<K, std::vector<V>>, То же самое касается std::multiset- это может быть просто std::map<K, int> где int подсчитывает количество вхождений K. Я что-то упустил при использовании этих структур?

Answer 1

Контр-пример вроде бы в порядке.

Рассмотрим PhoneEntry в AdressList, сгруппированном по имени.

int AdressListCompare(const PhoneEntry& p1, const PhoneEntry& p2){
    return p1.name<p2.name;
}

multiset<PhoneEntry, AdressListCompare> adressList;

adressList.insert( PhoneEntry("Cpt.G", "123-456", "Cellular") );    
adressList.insert( PhoneEntry("Cpt.G", "234-567", "Work") );
// Getting the entries
addressList.equal_range( PhoneENtry("Cpt.G") ); // All numbers

Это не было бы возможно с набором + количество. Ваш подход Object+count кажется более быстрым, если такое поведение не требуется. Например, государства-члены multiset::count()

"Сложность: логарифмическая по размеру + линейная по количеству."

Answer 2

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

Например, std::map<K, std::vector<V>> будет иметь итераторы, которые обращаются к std::pair<K, std::vector<V>> вместо std::pair<K, V>, std::map<K, std::vector<V>>::Count() не вернет правильный результат, если не учитывать дубликаты в векторе. Конечно, вы можете изменить свой код, чтобы выполнить дополнительные шаги, необходимые для исправления этого, но теперь вы взаимодействуете с контейнером совсем другим способом. Вы не можете позже заглянуть unordered_map или какая-то другая реализация карты, чтобы увидеть, как она работает лучше.

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

Вполне возможно, что реализация вашего компилятора std::multimap на самом деле просто обертка вокруг std::map<K, std::vector<V>>, Или это может быть не так. Это может быть более эффективным и дружественным к распределению пула объектов (какие векторы не являются).

С помощью std::map<K, int> вместо std::multiset это тот же случай. Count() не вернет ожидаемое значение, итераторы не будут перебирать дубликаты, итераторы будут обращаться к std::pair<k, int> вместо того, чтобы напрямую `К.

Answer 3

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

т. е. множество является неупорядоченной группой элементов, которые все уникальны в этом {A,B,C} == {B,C,A}