В информатике , MultiMap (иногда также multihash или multidict ) является обобщением карты или ассоциативный массив абстрактного типа данных , в которых более чем одно значение может быть связано с и возвращаемой для данного ключа. Как map, так и multimap являются частными случаями контейнеров (например, см. Контейнеры стандартной библиотеки шаблонов C ++ ). Часто мульти-карта реализуется как карта со списками или наборами в качестве значений карты.
Примеры
- В системе набора студентов, где студенты могут быть записаны в несколько классов одновременно, может существовать связь для каждого набора студента на курс, где ключ - это идентификатор студента, а значение - идентификатор курса. Если студент записан на три курса, будут три ассоциации, содержащие один и тот же ключ.
- Индекс книги может сообщать о любом количестве ссылок для данного индексного термина и, таким образом, может быть закодирован как мультикарта от индексных терминов до любого количества ссылок или страниц.
- Строки запроса могут иметь несколько значений, связанных с одним полем. Это обычно создается, когда веб-форма позволяет выбрать несколько флажков или вариантов выбора в ответ на один элемент формы.
Языковая поддержка
C ++
C ++ «s Standard Template Library предоставляет multimap
контейнер для отсортированного Multimap с использованием самобалансирующейся бинарного дерева поиска , [1] и SGI » расширение STL s обеспечивает hash_multimap
контейнер, который реализует Multimap с использованием хэш - таблицы . [2]
Начиная с C ++ 11, Стандартная библиотека шаблонов предоставляет unordered_multimap
для неупорядоченных мульти-карт. [3]
Дротик
Колчан предоставляет Multimap для Dart . [4]
Ява
Коллекции Apache Commons предоставляют интерфейс MultiMap для Java . [5] Он также предоставляет класс реализации MultiValueMap, который делает MultiMap из объекта Map и типа Collection. [6]
Google Guava предоставляет интерфейс Multimap и его реализации. [7]
Python
Python предоставляет collections.defaultdict
класс, который можно использовать для создания мульти-карты. Пользователь может создать экземпляр класса как collections.defaultdict(list)
.
OCaml
Модуль стандартной библиотеки OCamlHashtbl
реализует хеш-таблицу, в которой можно хранить несколько значений для ключа.
Scala
В Scala API языка программирования также предоставляет Multimap и реализации. [8]
Смотрите также
- Абстрактный тип данных для концепции типа в целом
- Ассоциативный массив для более фундаментального абстрактного типа данных
- Мультимножество для случая, когда один и тот же элемент может появляться несколько раз
Рекомендации
- ^ "multimap <Ключ, данные, сравнение, выделение>" . Руководство программиста стандартной библиотеки шаблонов . Silicon Graphics International .
- ^ "hash_multimap <Ключ, HashFcn, EqualKey, Alloc>" . Руководство программиста стандартной библиотеки шаблонов . Silicon Graphics International .
- ^ «Рабочий проект стандарта языка программирования C ++» (PDF) . п. 7807.
- ^ «Мультимап» . Документы Quiver API .
- ^ «Интерфейс MultiMap» . Commons Collections 3.2.2 API, Apache Commons .
- ^ «Класс MultiValueMap» . Commons Collections 3.2.2 API, Apache Commons .
- ^ «Интерфейс Multimap »,> . Библиотека Guava 2.0 . Архивировано из оригинала на 2013-01-15 . Проверено 1 января 2013 .
- ^ "Scala.collection.mutable.MultiMap" . Стабильный API Scala .