Przejdź do głównej zawartości
uwaga

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

Overview

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

The std::map is a container that stores key-value pairs with unique keys. Unlike std::map the order of the elements stored is unspecified.

Technical details

Technical definition of an unordered map

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements 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. Keys with the same hash code appear in the same bucket. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into.

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

std::unordered_map

Defined inunordered_map

Template parameters

pubKeyThe type of the stored keys.
pubValueThe type of the stored values.
pubHashA function object that perfoms hashing on two objects of type Key.
pubKeyEqual

A function object taking two arguments of type Key and determining if the keys are equal. Must return bool.

pubAllocatorAn allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubmapped_typeValue
pubvalue_typestd::pair<const Key, Value>
pubsize_typeUnsigned integer type (usually
std::size_t
).
pubdifference_typeSigned integer type (usually
std::ptrdiff_t
).
pubhasherHash
pubkey_equalKeyEqual
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer(until C++11)
std::allocator_traits<Allocator>::pointer(since C++11)
pubconst_pointerAllocator::const_pointer(until C++11)
std::allocator_traits<Allocator>::const_pointer(since C++11)
pubiteratorLegacyBidirectionalIterator to value_type
pubconst_iteratorLegacyBidirectionalIterator to const value_type
publocal_iterator

Like iterator but only to iterate across a single bucket.

pubconst_local_iterator

Like const_iterator but only to iterate across a single bucket.

pubnode_type (since C++17) A specialization of node handle representing a container node.
pub insert_return_type (since C++17)

Type describing the result of inserting a node_type, a specialization of

template < class Iter, class NodeType >
struct /* unspecified */ {
Iter position;
bool inserted;
NodeType node;
};

instantiated with template arguments iterator and node_type.

Member functions

pub(constructor)

Constructs a new unordered_map.

pub(destructor)

Destructs a unordered_map.

puboperator=

Assigns one unordered_map to another.

pubget_allocator

Returns an associated allocator.

Iterators

pubbegin
cbegin

Returns an iterator to the beginning.

pubend
cend

Returns an iterator to the end.

Capacity

pubempty

Returns true if an unordered_map is empty, otherwise false.

pubsize

Returns the number of elements in an unordered_map.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of an unordered_map.

pubinsert

Inserts elements or nodes (extracted with .extract()) (since C++17).

pubinsert_or_assign (since C++17)

Inserts a new element or assigns to an already existing one if it already exists.

pubemplace

Constructs a new element in place.

pubemplace_hint

Constructs elements in-place using a hint (iterator).

pubtry_emplace (since C++17)

Inserts a new element in-place if the key does not exist, does nothing if the key exists.

puberase

Erases elements.

pubswap

Swaps two unordered_maps.

pubextract (since C++17)

Extracts nodes from an unordered_map (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two unordered_maps together.

Lookup

pubat

Accesses a specified element with bounds checking.

puboperator[]

Accesses or inserts a specified element.

pubcount

Returns the number of elements matching a specific key (for an unordered_map always 0/1).

pubfind

Searches for an element and returns an iterator to it, or end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside an unordered_map, otherwise false.

pubequal_range

Returns a range of elements matching a specific key. (for an unorderd_map the range will always contain one element).

Bucket interface

pubbegin
cbegin

Returns an iterator to the beginning of a specified bucket.

pubend
cend

Returns an iterator to the end of a specified bucket.

pubbucket_count

Returns a number of buckets.

pubmax_bucket_count

Returns a maximum number of buckets.

pubbucket_size

Returns a number of elements in a specific bucket.

pubbucket

Returns a bucket for a specific key.

Hash policy

pubload_factor

Returns an average number of elements per bucket.

pubmax_load_factor

Manages a maximum average number of elements per bucket.

pubrehash

Reserves at least the specified number of buckets and regenerates the hash table.

pubreserve

Reserves space for at least a specified number of elements and regenerates the hash table.

Observers

pubhash_function

Returns an internal function object that hashes keys.

pubkey_eq

Returns an internal function object that compares keys.

Non-member functions

puboperator==
operator!= (removed in C++20)
Compares values in an unordered_map.
pubstd::swap (std::unordered_map)An overload for a std::swap algorithm.
pubstd::erase_if (std::unordered_map) (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
>
zanotuj

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:

zanotuj

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:

More examples

Basic manipulation

Creating unordered_map, inserting pair and printing it out

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
player2 is in Capital City
player3 is in The Harbor
player1 is in Mine
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.
uwaga

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

Overview

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

The std::map is a container that stores key-value pairs with unique keys. Unlike std::map the order of the elements stored is unspecified.

Technical details

Technical definition of an unordered map

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements 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. Keys with the same hash code appear in the same bucket. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into.

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

std::unordered_map

Defined inunordered_map

Template parameters

pubKeyThe type of the stored keys.
pubValueThe type of the stored values.
pubHashA function object that perfoms hashing on two objects of type Key.
pubKeyEqual

A function object taking two arguments of type Key and determining if the keys are equal. Must return bool.

pubAllocatorAn allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubmapped_typeValue
pubvalue_typestd::pair<const Key, Value>
pubsize_typeUnsigned integer type (usually
std::size_t
).
pubdifference_typeSigned integer type (usually
std::ptrdiff_t
).
pubhasherHash
pubkey_equalKeyEqual
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerAllocator::pointer(until C++11)
std::allocator_traits<Allocator>::pointer(since C++11)
pubconst_pointerAllocator::const_pointer(until C++11)
std::allocator_traits<Allocator>::const_pointer(since C++11)
pubiteratorLegacyBidirectionalIterator to value_type
pubconst_iteratorLegacyBidirectionalIterator to const value_type
publocal_iterator

Like iterator but only to iterate across a single bucket.

pubconst_local_iterator

Like const_iterator but only to iterate across a single bucket.

pubnode_type (since C++17) A specialization of node handle representing a container node.
pub insert_return_type (since C++17)

Type describing the result of inserting a node_type, a specialization of

template < class Iter, class NodeType >
struct /* unspecified */ {
Iter position;
bool inserted;
NodeType node;
};

instantiated with template arguments iterator and node_type.

Member functions

pub(constructor)

Constructs a new unordered_map.

pub(destructor)

Destructs a unordered_map.

puboperator=

Assigns one unordered_map to another.

pubget_allocator

Returns an associated allocator.

Iterators

pubbegin
cbegin

Returns an iterator to the beginning.

pubend
cend

Returns an iterator to the end.

Capacity

pubempty

Returns true if an unordered_map is empty, otherwise false.

pubsize

Returns the number of elements in an unordered_map.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of an unordered_map.

pubinsert

Inserts elements or nodes (extracted with .extract()) (since C++17).

pubinsert_or_assign (since C++17)

Inserts a new element or assigns to an already existing one if it already exists.

pubemplace

Constructs a new element in place.

pubemplace_hint

Constructs elements in-place using a hint (iterator).

pubtry_emplace (since C++17)

Inserts a new element in-place if the key does not exist, does nothing if the key exists.

puberase

Erases elements.

pubswap

Swaps two unordered_maps.

pubextract (since C++17)

Extracts nodes from an unordered_map (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two unordered_maps together.

Lookup

pubat

Accesses a specified element with bounds checking.

puboperator[]

Accesses or inserts a specified element.

pubcount

Returns the number of elements matching a specific key (for an unordered_map always 0/1).

pubfind

Searches for an element and returns an iterator to it, or end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside an unordered_map, otherwise false.

pubequal_range

Returns a range of elements matching a specific key. (for an unorderd_map the range will always contain one element).

Bucket interface

pubbegin
cbegin

Returns an iterator to the beginning of a specified bucket.

pubend
cend

Returns an iterator to the end of a specified bucket.

pubbucket_count

Returns a number of buckets.

pubmax_bucket_count

Returns a maximum number of buckets.

pubbucket_size

Returns a number of elements in a specific bucket.

pubbucket

Returns a bucket for a specific key.

Hash policy

pubload_factor

Returns an average number of elements per bucket.

pubmax_load_factor

Manages a maximum average number of elements per bucket.

pubrehash

Reserves at least the specified number of buckets and regenerates the hash table.

pubreserve

Reserves space for at least a specified number of elements and regenerates the hash table.

Observers

pubhash_function

Returns an internal function object that hashes keys.

pubkey_eq

Returns an internal function object that compares keys.

Non-member functions

puboperator==
operator!= (removed in C++20)
Compares values in an unordered_map.
pubstd::swap (std::unordered_map)An overload for a std::swap algorithm.
pubstd::erase_if (std::unordered_map) (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
>
zanotuj

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:

zanotuj

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:

More examples

Basic manipulation

Creating unordered_map, inserting pair and printing it out

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
player2 is in Capital City
player3 is in The Harbor
player1 is in Mine
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.