Note, this article is not finished! You can help by editing this doc page.
Overview
- Simplified (since C++98)
- Detailed
template< class Key, class Value, /* ... */ >
class multimap;
- Regular (since C++98)
- Polymorphic (since C++17)
template<
class Key,
class Value,
class Compare = std::less<Key>,
class Allocator = std::allocator<std::pair<const Key, Value>>
>
class multimap;
namespace pmr {
template< class Key, class Value, class Compare = std::less<Key> >
using multimap = std::multimap<Key, Value, Compare,
std::pmr::polymorphic_allocator<std::pair<const Key, Value>>>;
}
The std::multimap
is a container that stores key-value pairs in a specified order. It works almost as
std::map
, the only difference is that the keys can repeat themselves. If the keys of both elements are the
same, they are ordered by their values.
Technical details
Technical definition of a multimap
Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key.
Sorting is done according to the comparison function Compare
, applied to the keys. Search, insertion, and removal operations have logarithmic complexity.
The order of the key-value pairs whose keys compare equivalent is the order of insertion and does not change. (since C++11)
Everywhere the standard library uses the Compare
requirements, equivalence is determined by using the equivalence relation as described on Compare.
In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a)
.
std::multimap
Defined in | map |
Template parameters
pub | Key | The type of the stored keys. |
pub | Value | The type of the stored values. |
pub | Compare | A comparator type satisfying Compare. |
pub | Allocator | An allocator type responsible for allocating and deallocating memory. Must satisfy Allocator. |
Type names
pub | key_type | Key |
pub | mapped_type | Value |
pub | value_type | std::pair<const Key, Value> |
pub | size_type | Unsigned integer type (usually ). |
pub | difference_type | Signed integer type (usually ). |
pub | key_compare | Compare |
pub | allocator_type | Allocator |
pub | reference | value_type& |
pub | const_reference | const value_type& |
pub | pointer | Allocator::pointer (until C++11)std::allocator_traits<Allocator>::pointer (since C++11) |
pub | const_pointer | Allocator::const_pointer (until C++11)std::allocator_traits<Allocator>::const_pointer (since C++11) |
pub | iterator | LegacyBidirectionalIterator to value_type |
pub | const_iterator | LegacyBidirectionalIterator to const value_type |
pub | reverse_iterator |
|
pub | const_reverse_iterator |
|
pub | node_type (since C++17) | A specialization of node handle representing a container node. |
Member classes
pub | value_compare | Function object that compares two objects of type |
Member functions
pub | (constructors) | Constructs a new multimap. |
pub | (destructor) | Destructs a multimap. |
pub | operator= | Assigns one multimap to another. |
pub | get_allocator | Returns an associated allocator. |
Iterators
pub | begin cbegin (since C++11) | Returns an iterator to the beginning. |
pub | end cend (since C++11) | Returns an iterator to the end. |
pub | rbegin crbegin (since C++11) | Returns a reverse iterator to the beginning. |
pub | rend crend (since C++11) | Returns a reverse iterator to the end. |
Capacity
pub | empty | Returns |
pub | size | Returns the number of elements in a multimap. |
pub | max_size | Returns the maximum possible number of elements. |
Modifiers
pub | clear | Clears the contents of a multimap. |
pub | insert | Inserts elements or nodes (extracted with |
pub | emplace (since C++11) | Constructs a new element in place. |
pub | emplace_hint (since C++11) | Constructs elements in-place using a hint (iterator). |
pub | erase | Erases elements. |
pub | swap | Swaps two multimaps. |
pub | extract (since C++17) | Extracts nodes from a multimap (can be later inserted somewhere else). |
pub | merge (since C++17) | Merges two multimaps together. |
Lookup
pub | count | Returns the number of elements matching a specific key. |
pub | find | Searches for an element and returns an iterator to it, or end iterator if not found. |
pub | contains (since C++20) | Returns |
pub | equal_range | Returns a range of elements matching a specific key. |
pub | lower_bound | Returns an iterator to the first element not less than the given key. |
pub | upper_bound | Returns an iterator to the first element greater than the given key. |
Observers
pub | key_comp | Returns an internal function object that compares keys. |
pub | value_comp | Returns an internal function object that compares keys in objects of type |
Non-member functions
pub | operator== operator!= (removed in C++20) operator< (removed in C++20) operator> (removed in C++20) operator<= (removed in C++20) operator>= (removed in C++20) operator<=> (since C++20) | Lexicographically compares the values in a multimap. |
pub | std::swap (std::multimap) | An overload for a std::swap algorithm. |
pub | std::erase_if (std::multimap) (since C++20) | Overload for a std::erase_if algorithm. |
Deduction guides (since C++17)
Click to expand
Deduction guides
// (1)
template< class InputIt, class Alloc >
multimap( InputIt, InputIt, Alloc )
-> multimap<iter_key_t<InputIt>, iter_val_t<InputIt>,
std::less<iter_key_t<InputIt>>, Alloc>;
// (2)
template< class InputIt,
class Comp = std::less<iter_key_t<InputIt>>,
class Alloc = std::allocator<iter_to_alloc_t<InputIt>> >
multimap( InputIt, InputIt, Comp = Comp(), Alloc = Alloc() )
-> multimap<iter_key_t<InputIt>, iter_val_t<InputIt>, Comp, Alloc>;
(1)
and(2)
allow for deduction from an iterator range
// (3)
template< class Key, class T, class Allocator >
multimap( std::initializer_list<std::pair<Key, T>>, Allocator )
-> multimap<Key, T, std::less<Key>, Allocator>;
// (4)
template< class Key,
class T,
class Comp = std::less<Key>,
class Alloc = std::allocator<std::pair<const Key, T>> >
multimap( std::initializer_list<std::pair<Key, T>>, Comp = Comp(), Alloc = Alloc() )
-> multimap<Key, T, Comp, Alloc>;
(3)
and(4)
allow for deduction from astd::initializer_list
Aliases iter_key_t
, iter_val_t
and iter_to_alloc_t
are defined as if follows:
template< class InputIt >
using iter_key_t = std::remove_const_t<
typename std::iterator_traits<InputIt>::value_type::first_type>;
template< class InputIt >
using iter_val_t = typename std::iterator_traits<InputIt>::value_type::second_type;
template< class InputIt >
using iter_to_alloc_t = std::pair<
std::add_const_t<typename std::iterator_traits<InputIt>::value_type::first_type>,
typename std::iterator_traits<InputIt>::value_type::second_type
>
Note that these aliases aren't guaranteed to be found anywhere in the standard library. They are defined solely for presentation purposes of these deduction guides and weren't present in the standard library at the point of writing of this document.
Overload resolution
In order for any of the deduction guides to participate in overload resolution, the folllowing requirements must be met:
InputIt
satisfiesLegacyInputIterator
Alloc
satisfiesAllocator
Comp
doesn't satisfyAllocator
The extent to which the library determines that a type does not satisfy LegacyInputIterator
is unspecified,
except that as a minimum:
- Integral types do not qualify as input iterators.
Likewise, the extent to which it determines that a type does not satisfy Allocator
is unspecified,
except that as a minimum:
- The member type
Alloc::value_type
must exist. - The expression
std::declval<Alloc&>().allocate(std::size_t{})
must be well-formed when treated as an unevaluated operand.
More examples
Basic manipulation
#include <iostream>
#include <utility>
#include <string>
#include <map>
int main(){
std::multimap<std::string, int> potions { {"health", 30}, {"mana", 25}, {"mana", 50} };
potions.emplace("health", 200);
potions.insert(std::make_pair("speed", 10));
for (const auto& [key, value] : potions)
std::cout << key << " " << value << std::endl;
return 0;
}
health 30
health 200
mana 25
mana 50
speed 10
Hover to see the original license.