Multimap

Last updated

In computer science, a multimap (sometimes also multihash, multidict or multidictionary) is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key. Both map and multimap are particular cases of containers (for example, see C++ Standard Template Library containers). Often the multimap is implemented as a map with lists or sets as the map values.

Contents

Examples

Language support

C++

C++'s Standard Template Library provides the multimap container for the sorted multimap using a self-balancing binary search tree, [1] and SGI's STL extension provides the hash_multimap container, which implements a multimap using a hash table. [2]

As of C++11, the Standard Template Library provides the unordered_multimap for the unordered multimap. [3]

Dart

Quiver provides a Multimap for Dart. [4]

Java

Apache Commons Collections provides a MultiMap interface for Java. [5] It also provides a MultiValueMap implementing class that makes a MultiMap out of a Map object and a type of Collection. [6]

Google Guava provides a Multimap interface and implementations of it. [7]

Python

Python provides a collections.defaultdict class that can be used to create a multimap. The user can instantiate the class as collections.defaultdict(list).

OCaml

OCaml's standard library module Hashtbl implements a hash table where it's possible to store multiple values for a key.

Scala

The Scala programming language's API also provides Multimap and implementations. [8]

See also

Related Research Articles

Java and C++ are two prominent object-oriented programming languages. By many language popularity metrics, the two languages have dominated object-oriented and high-performance software development for much of the 21st century, and are often directly compared and contrasted. Java's syntax was based on C/C++.

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of pairs, such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a function with finite domain. It supports 'lookup', 'remove', and 'insert' operations.

The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators.

In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterator are fixed, iterators are often implemented in terms of the structures underlying a container implementation and are often tightly coupled to the container to enable the operational semantics of the iterator. An iterator performs traversal and also gives access to data elements in a container, but does not itself perform iteration.

In computer science, a set is an abstract data type that can store unique values, without any particular order. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.

In the C++ programming language, the C++ Standard Library is a collection of classes and functions, which are written in the core language and part of the C++ ISO Standard itself.

C++ Technical Report 1 (TR1) is the common name for ISO/IEC TR 19768, C++ Library Extensions, which is a document that proposed additions to the C++ standard library for the C++03 language standard. The additions include regular expressions, smart pointers, hash tables, and random number generators. TR1 was not a standard itself, but rather a draft document. However, most of its proposals became part of the later official standard, C++11. Before C++11 was standardized, vendors used this document as a guide to create extensions. The report's goal was "to build more widespread existing practice for an expanded C++ standard library".

<span class="mw-page-title-main">Java collections framework</span> Collections in Java

The Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures.

In computing, a DBM is a library and file format providing fast, single-keyed access to data. A key-value database from the original Unix, dbm is an early example of a NoSQL system.

oneAPI Threading Building Blocks, is a C++ template library developed by Intel for parallel programming on multi-core processors. Using TBB, a computation is broken down into tasks that can run in parallel. The library manages and schedules threads to execute these tasks.

In computer programming, a collection is a grouping of some variable number of data items that have some shared significance to the problem being solved and need to be operated upon together in some controlled fashion. Generally, the data items will be of the same type or, in languages supporting inheritance, derived from some common ancestor type. A collection is a concept applicable to abstract data types, and does not prescribe a specific implementation as a concrete data structure, though often there is a conventional choice.

This Comparison of programming languages (associative arrays) compares the features of associative array data structures or array-lookup processing for over 40 computer programming languages.

A hash array mapped trie (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie. It is a refined version of the more general notion of a hash tree.

In the programming language C++, unordered associative containers are a group of class templates in the C++ Standard Library that implement hash table variants. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard: unordered_set, unordered_map, unordered_multiset, unordered_multimap. Each of these containers differ only on constraints placed on their elements.

Windows Runtime (WinRT) is a platform-agnostic component and application architecture first introduced in Windows 8 and Windows Server 2012 in 2012. It is implemented in C++ and officially supports development in C++, Rust/WinRT, Python/WinRT, JavaScript-TypeScript, and the managed code languages C# and Visual Basic (.NET) (VB.NET).

In C++, associative containers refer to a group of class templates in the standard library of the C++ programming language that implement ordered associative arrays. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard: set, map, multiset, multimap. Each of these containers differ only on constraints placed on their elements.

Google Guava is an open-source set of common libraries for Java, mainly developed by Google engineers.

The Java programming language's Java Collections Framework version 1.5 and later defines and implements the original regular single-threaded Maps, and also new thread-safe Maps implementing the java.util.concurrent.ConcurrentMap interface among other concurrent interfaces. In Java 1.6, the java.util.NavigableMap interface was added, extending java.util.SortedMap, and the java.util.concurrent.ConcurrentNavigableMap interface was added as a subinterface combination.

<span class="mw-page-title-main">Concurrent hash table</span>

A concurrent hash table or concurrent hash map is an implementation of hash tables allowing concurrent access by multiple threads using a hash function.

References

  1. ↑ "multimap<Key, Data, Compare, Alloc>". Standard Template Library Programmer's Guide. Silicon Graphics International.
  2. ↑ "hash_multimap<Key, HashFcn, EqualKey, Alloc>". Standard Template Library Programmer's Guide. Silicon Graphics International.
  3. ↑ "Working Draft, Standard for Programming Language C++" (PDF). p. 7807.
  4. ↑ "Multimap". Quiver API docs.
  5. ↑ "Interface MultiMap". Commons Collections 3.2.2 API, Apache Commons .
  6. ↑ "Class MultiValueMap". Commons Collections 3.2.2 API, Apache Commons .
  7. ↑ "Interface Multimap<K,V>". Guava Library 2.0. Archived from the original on 2013-01-15. Retrieved 2013-01-01.
  8. ↑ "Scala.collection.mutable.MultiMap". Scala stable API.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.