multimap Class

Article
07/29/2015

The Standard Template Library multimap class is used for the storage and retrieval of data from a collection in which the each element is a pair that has both a data value and a sort key. The value of the key does not need to be unique and is used to order the data automatically. The value of an element in a multimap, but not its associated key value, may be changed directly. Instead, key values associated with old elements must be deleted and new key values associated with new elements inserted.

template <
   class Key, 
   class Type, 
   class Traits=less<Key>, 
   class Allocator=allocator<pair <const Key, Type> > 
> class multimap;

Parameters

Key
The key data type to be stored in the multimap.
Type
The element data type to be stored in the multimap.
Traits
The type that provides a function object that can compare two element values as sort keys to determine their relative order in the multimap. The binary predicate less<Key> is the default value.
Allocator
The type that represents the stored allocator object that encapsulates details about the map's allocation and deallocation of memory. This argument is optional and the default value is allocator<pair <const Key, Type> >.

Remarks

The STL multimap class is

An associative container, which a variable size container that supports the efficient retrieval of element values based on an associated key value.
Reversible, because it provides bidirectional iterators to access its elements.
Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.
Multiple, because its elements do not need to have a unique keys, so that one key value may have many element data values associated with it.
A pair associative container, because its element data values are distinct from its key values.
A template class, because the functionality it provides is generic and so independent of the specific type of data contained as elements or keys. The data types to be used for elements and keys are, instead, specified as parameters in the class template along with the comparison function and allocator.

The iterator provided by the map class is a bidirectional iterator, but the class member functions insert and multimap have versions that take as template parameters a weaker input iterator, whose functionality requirements are more minimal than those guaranteed by the class of bidirectional iterators. The different iterator concepts form a family related by refinements in their functionality. Each iterator concept has its own set of requirements and the algorithms that work with them must limit their assumptions to the requirements provided by that type of iterator. It may be assumed that an input iterator may be dereferenced to refer to some object and that it may be incremented to the next iterator in the sequence. This is a minimal set of functionality, but it is enough to be able to talk meaningfully about a range of iterators [First, Last) in the context of the class's member functions.

The choice of container type should be based in general on the type of searching and inserting required by the application. Associative containers are optimized for the operations of lookup, insertion and removal. The member functions that explicitly support these operations are efficient, performing them in a time that is on average proportional to the logarithm of the number of elements in the container. Inserting elements invalidates no iterators, and removing elements invalidates only those iterators that had specifically pointed at the removed elements.

The multimap should be the associative container of choice when the conditions associating the values with their keys are satisfied by the application. A model for this type of structure is an ordered list of key words with associated string values providing, say, definitions, where the words were not always uniquely defined. If, instead, the key words were uniquely defined so that keys were unique, then a map would be the container of choice. If, on the other hand, just the list of words were being stored, then a set would be the correct container. If multiple occurrences of the words were allowed, then a multiset would be the appropriate container structure.

The multimap orders the sequence it controls by calling a stored function object of type key_compare. This stored object is a comparison function that may be accessed by calling the member function key_comp. In general, the elements need be merely less than comparable to establish this order: so that, given any two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements. On a more technical note, the comparison function is a binary predicate that induces a strict weak ordering in the standard mathematical sense. A binary predicate f(x,y) is a function object that has two argument objects x and y and a return value of true or false. An ordering imposed on a set is a strict weak ordering if the binary predicate is irreflexive, antisymmetric, and transitive and if equivalence is transitive, where two objects x and y are defined to be equivalent when both f(x,y) and f(y,x) are false. If the stronger condition of equality between keys replaces that of equivalence, then the ordering becomes total (in the sense that all the elements are ordered with respect to each other) and the keys matched will be indiscernible from each other.

Members

Constructors

multimap

Constructs a multimap that is empty or that is a copy of all or part of some other multimap.

Typedefs

allocator_type	A type that represents the allocator class for the multimap object.
const_iterator	A type that provides a bidirectional iterator that can read a const element in the multimap.
const_pointer	A type that provides a pointer to a const element in a multimap.
const_reference	A type that provides a reference to a const element stored in a multimap for reading and performing const operations.
const_reverse_iterator	A type that provides a bidirectional iterator that can read any const element in the multimap.
difference_type	A signed integer type that can be used to represent the number of elements of a multimap in a range between elements pointed to by iterators.
iterator	A type that provides the difference between two iterators that refer to elements within the same multimap.
key_compare	A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the multimap.
key_type	A type that describes the sort key object that constitutes each element of the multimap.
mapped_type	A type that represents the data type stored in a multimap.
pointer	A type that provides a pointer to a const element in a multimap.
reference	A type that provides a reference to an element stored in a multimap.
reverse_iterator	A type that provides a bidirectional iterator that can read or modify an element in a reversed multimap.
size_type	An unsigned integer type that provides a pointer to a const element in a multimap.
value_type	A type that provides a function object that can compare two elements as sort keys to determine their relative order in the multimap.

Member Functions

begin	Returns an iterator addressing the first element in the multimap.
cbegin	Returns a const iterator addressing the first element in the multimap.
cend	Returns a const iterator that addresses the location succeeding the last element in a multimap.
clear	Erases all the elements of a multimap.
count	Returns the number of elements in a multimap whose key matches a parameter-specified key.
crbegin	Returns a const iterator addressing the first element in a reversed multimap.
crend	Returns a const iterator that addresses the location succeeding the last element in a reversed multimap.
emplace	Inserts an element constructed in place into a multimap.
emplace_hint	Inserts an element constructed in place into a multimap, with a placement hint
empty	Tests if a multimap is empty.
end	Returns an iterator that addresses the location succeeding the last element in a multimap.
equal_range	Finds the range of elements where the key of the element matches a specified value.
erase	Removes an element or a range of elements in a multimap from specified positions or removes elements that match a specified key.
find	Returns an iterator addressing the first location of an element in a multimap that has a key equivalent to a specified key.
get_allocator	Returns a copy of the allocator object used to construct the multimap.
insert	Inserts an element or a range of elements into a multimap.
key_comp	Retrieves a copy of the comparison object used to order keys in a multimap.
lower_bound	Returns an iterator to the first element in a multimap that with a key that is equal to or greater than a specified key.
max_size	Returns the maximum length of the multimap.
rbegin	Returns an iterator addressing the first element in a reversed multimap.
rend	Returns an iterator that addresses the location succeeding the last element in a reversed multimap.
size	Returns the number of elements in the multimap.
swap	Exchanges the elements of two multimaps.
upper_bound	Returns an iterator to the first element in a multimap that with a key that is greater than a specified key.
value_comp	The member function returns a function object that determines the order of elements in a multimap by comparing their key values.

Operators

operator=

Replaces the elements of a multimap with a copy of another multimap.

Requirements

Header: <map>

Namespace: std

The (key, value) pairs are stored in a multimap as objects of type pair. The pair class requires the header <utility>, which is automatically included by <map>.

multimap Class

Parameters

Remarks

Members

Constructors

Typedefs

Member Functions

Operators

Requirements

See Also

Reference

Concepts

Other Resources

Additional resources