caution

Note, this article is not finished! You can help by editing this doc page.

Overview

Simplified (since C++11)

template< class Key, class Value, /* ... */ >
class unordered_map;

Detailed

Regular (since C++11)

template<
    class Key,
    class Value,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, Value>>
>
class unordered_map;

Polymorphic (since C++17)

namespace pmr {
    template<
        class Key,
        class Value,
        class Hash = std::hash<Key>,
        class KeyEqual = std::equal_to<Key>,
    >
    using unordered_multimap = std::unordered_multimap<Key, Value, Hash, KeyEqual,
                                std::pmr::polymorphic_allocator<std::pair<const Key, Value>>>;
}

The std::unordered_multimap is a container that stores key-value pairs. It works almost as std::unordered_map, the only difference is that the keys can repeat themselves. If the keys of both elements are the same, their values are compared to determine if they should be added to the multimap.

The order of the elements stored is not specified, unlike in std::multimap.

Technical details

Technical definition of an unordered multimap

Unordered multimap is an unordered associative container that supports equivalent keys (an unordered_multimap may contain multiple copies of each key value) and that associates values of another type with the keys.

The unordered_multimap class supports forward iterators. Search, insertion, and removal have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into.

The iteration order of this container is not required to be stable (so, for example, std::equal cannot be used to compare two std::unordered_multimaps), except that every group of elements whose keys compare equivalent (compare equal with key_eq() as the comparator) forms a contiguous subrange in the iteration order, also accessible with equal_range().

std::unordered_multimap meets the requirements of Container, AllocatorAwareContainer, UnorderedAssociativeContainer.

std::unordered_multimap

Defined in

unordered_multimap

Template parameters

pub	Key	The type of the stored keys.
pub	Value	The type of the stored values.
pub	Hash	A function object that perfoms hashing on two objects of type Key.
pub	KeyEqual	A function object taking two arguments of type Key and determining if the keys are equal. Must return bool.
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 std::size_t ).
pub	difference_type	Signed integer type (usually std::ptrdiff_t ).
pub	hasher	Hash
pub	key_equal	KeyEqual
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	local_iterator	Like iterator but only to iterate across a single bucket.
pub	const_local_iterator	Like const_iterator but only to iterate across a single bucket.
pub	node_type (since C++17)	A specialization of node handle representing a container node.

Member functions

pub	(constructors)	Constructs a new unordered_multimap.
pub	(destructor)	Destructs an unordered_multimap.
pub	operator=	Assigns one unordered_multimap to another.
pub	get_allocator	Returns an associated allocator.

Iterators

pub	begin cbegin	Returns an iterator to the beginning.
pub	end cend	Returns an iterator to the end.

Capacity

pub	empty	Returns true if an unordered_multimap is empty, otherwise false.
pub	size	Returns the number of elements in an unordered_multimap.
pub	max_size	Returns the maximum possible number of elements.

Modifiers

pub	clear	Clears the contents of an unordered_multimap.
pub	insert	Inserts elements or nodes (extracted with .extract()) (since C++17).
pub	emplace	Constructs a new element in place.
pub	emplace_hint	Constructs elements in-place using a hint (iterator).
pub	erase	Erases elements.
pub	swap	Swaps two unordered_multimaps.
pub	extract (since C++17)	Extracts nodes from an unordered_multimap (can be later inserted somewhere else).
pub	merge (since C++17)	Merges two unordered_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 true if an element is inside an unordered_multimap, otherwise false.
pub	equal_range	Returns a range of elements matching a specific key.

Bucket interface

pub	begin cbegin	Returns an iterator to the beginning of a specified bucket.
pub	end cend	Returns an iterator to the end of a specified bucket.
pub	bucket_count	Returns a number of buckets.
pub	max_bucket_count	Returns a maximum number of buckets.
pub	bucket_size	Returns a number of elements in a specific bucket.
pub	bucket	Returns a bucket for a specific key.

Hash policy

pub	load_factor	Returns an average number of elements per bucket.
pub	max_load_factor	Manages a maximum average number of elements per bucket.
pub	rehash	Reserves at least the specified number of buckets and regenerates the hash table.
pub	reserve	Reserves space for at least a specified number of elements and regenerates the hash table.

Observers

pub	hash_function	Returns an internal function object that hashes keys.
pub	key_eq	Returns an internal function object that compares keys.

Non-member functions

pub	operator== operator!= (removed in C++20)	Compares values in an unordered_multimap.
pub	std::swap (std::unordered_multimap)	An overload for a std::swap algorithm.
pub	std::erase_if (std::unordered_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 >
unordered_map( InputIt, InputIt, Alloc )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>,
            std::hash<iter_key_t<InputIt>>,
            std::equal_to<iter_key_t<InputIt>>, Alloc>;

// (2)
template< class InputIt, class Hash, class Alloc >
unordered_map( InputIt, InputIt, typename /*see below*/::size_type, Hash, Alloc )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>, Hash,
              std::equal_to<iter_key_t<InputIt>>, Alloc>;

// (3)
template< class InputIt, class Alloc >
unordered_map( InputIt, InputIt, typename /*see below*/::size_type, Alloc )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>,
           std::hash<iter_key_t<InputIt>>,
           std::equal_to<iter_key_t<InputIt>>, Alloc>;

// (4)
template< class InputIt,
          class Hash = std::hash<iter_key_t<InputIt>>,
          class Pred = std::equal_to<iter_key_t<InputIt>>,
          class Alloc = std::allocator<iter_to_alloc_t<InputIt>> >
unordered_map( InputIt, InputIt,
         typename /*see below*/::size_type = /*see below*/,
         Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
  -> unordered_map<iter_key_t<InputIt>, iter_val_t<InputIt>, Hash, Pred, Alloc>;

(1 - 4) allow deduction from an iterator range

// (5)
template< class Key, class T, typename Alloc >
unordered_map( std::initializer_list<std::pair<Key, T>>, Alloc )
  -> unordered_map<Key, T, std::hash<Key>, std::equal_to<Key>, Alloc>;

// (6)
template< class Key, class T, class Hash, class Alloc >
unordered_map( std::initializer_list<std::pair<Key, T>>,
       typename /*see below*/::size_type, Hash, Alloc )
  -> unordered_map<Key, T, Hash, std::equal_to<Key>, Alloc>;

// (7)
template< class Key, class T, typename Alloc >
unordered_map( std::initializer_list<std::pair<Key, T>>,
     typename /*see below*/::size_type, Alloc )
  -> unordered_map<Key, T, std::hash<Key>, std::equal_to<Key>, Alloc>;

// (8)
template< class Key, class T, class Hash = std::hash<Key>,
          class Pred = std::equal_to<Key>,
          class Alloc = std::allocator<std::pair<const Key, T>> >
unordered_map( std::initializer_list<std::pair<Key, T>>,
         typename /*see below*/::size_type = /*see below*/,
         Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
-> unordered_map<Key, T, Hash, Pred, Alloc>;

(5 - 8) allow deduction from a std::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

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: A deduction guide for an unordered associative container shall not participate in overload resolution if any of the following are true:

• InputIt satisfies LegacyInputIterator
• Alloc satisfies Allocator
• Hash doesn't deduce to an integral type or doesn't satisfy Allocator
• Pred doesn't satisfy Allocator

note

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

Create, insert and print

#include <unordered_map>
#include <iostream>
#include <string>

int main() {
  std::unordered_map<std::string, std::string> player_locations {
    {"player2", "Capital City"},
    {"player3", "The Harbor"}
  };

  player_locations["player1"] = "Mine";

  for (const auto& [key, value] : player_locations)
    std::cout << key << " is in " << value << '\n';

  return 0;
}

Result

player3 has got Shield
player2 has got Health potion
player2 has got Sword