Note, this article is not finished! You can help by editing this doc page.
Overview
- Simplified (since C++11)
- Detailed
template< class Key, class Value, /* ... */ >
class unordered_map;
- Regular (since C++11)
- Polymorphic (since C++17)
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;
namespace pmr {
template<
class Key,
class Value,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
>
using unordered_map = std::unordered_map<Key, Value, Hash, KeyEqual,
std::pmr::polymorphic_allocator<std::pair<const Key, Value>>>;
}
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 in | unordered_map |
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 |
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 | 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 |
pub | const_local_iterator | Like |
pub | node_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
instantiated with template arguments |
Member functions
pub | (constructor) | Constructs a new unordered_map. |
pub | (destructor) | Destructs a unordered_map. |
pub | operator= | Assigns one unordered_map 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 |
pub | size | Returns the number of elements in an unordered_map. |
pub | max_size | Returns the maximum possible number of elements. |
Modifiers
pub | clear | Clears the contents of an unordered_map. |
pub | insert | Inserts elements or nodes (extracted with |
pub | insert_or_assign (since C++17) | Inserts a new element or assigns to an already existing one if it already exists. |
pub | emplace | Constructs a new element in place. |
pub | emplace_hint | Constructs elements in-place using a hint (iterator). |
pub | try_emplace (since C++17) | Inserts a new element in-place if the key does not exist, does nothing if the key exists. |
pub | erase | Erases elements. |
pub | swap | Swaps two unordered_maps. |
pub | extract (since C++17) | Extracts nodes from an unordered_map (can be later inserted somewhere else). |
pub | merge (since C++17) | Merges two unordered_maps together. |
Lookup
pub | at | Accesses a specified element with bounds checking. |
pub | operator[] | Accesses or inserts a specified element. |
pub | count | Returns the number of elements matching a specific key (for an unordered_map always |
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. (for an unorderd_map the range will always contain one element). |
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_map. |
pub | std::swap (std::unordered_map) | An overload for a std::swap algorithm. |
pub | std::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 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: A deduction guide for an unordered associative container shall not participate in overload resolution if any of the following are true:
InputIt
satisfiesLegacyInputIterator
Alloc
satisfiesAllocator
Hash
doesn't deduce to an integral type or doesn't satisfyAllocator
Pred
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
Creating unordered_map, inserting pair and printing it out
#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;
}
player2 is in Capital City
player3 is in The Harbor
player1 is in Mine
Hover to see the original license.