Примеры использования 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> вместо прямого к `K.

Answer 3

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

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