multiset и multimap - в чем смысл?

Некоторые варианты использования:

мульти-карта

• С почтовым индексом в качестве ключа все люди, у которых есть этот почтовый индекс
• С идентификатором учетной записи в качестве ключа все открытые ордера этого человека / учетной записи
• Словарь с различными объяснениями для каждого ключевого слова

мультимножество

по сути, это карта с ключом и целым числом.

• Инвентарь магазина, все продукты имеют свой ключ, а сумма, которая еще доступна, является стоимостью
• накопленные данные о продажах магазина, каждый раз, когда продукт продается, идентификатор продукта добавляется в мультимножество, тем самым увеличивая проданное количество

Наиболее важным преимуществом использования мультимножества над вектором / списком (или любым другим контейнером) является временная сложность операции поиска. средняя временная сложность для мультимножества составляет O (logn), а unordered_multiset - O (1). То же самое верно для multimap и orders_multimap.

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

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

Другим примером может быть любой неуникальный индекс (например, в базе данных).

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

Мультимножество или несколько карт просто для ситуаций, когда может быть более одного конкретного элемента. Например, предположим, вы хотите создать указатель для книги. Вы просматриваете текст, выкидываете все действительно общие бессмысленные слова («а», «ан», «тот» и т. Д.), А затем составляете список всех остальных и место в книге, где каждое произошел.

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

http://www.cplusplus.com/reference/stl/multimap/

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

Это своего рода реестр, в котором элементы могут иметь общий ключ. Вы можете думать о компаниях и сотрудниках. Почтовый адрес - это ключ, а сотрудники - ценности.

Вот что Википедия говорит об использовании:

• В системе набора студентов, где студенты могут быть записаны в несколько классов одновременно, может существовать ассоциация для каждого набора студента на курс, где ключ - это идентификатор студента, а значение - идентификатор курса. Если студент записан на три курса, будут три ассоциации, содержащие один и тот же ключ.
• Индекс книги может сообщать о любом количестве ссылок для данного термина индекса и, таким образом, может быть закодирован как мультикарта от терминов индекса до любого количества ссылок.

Используйте multimap везде, где вы хотите использовать древовидную структуру.