Cpp Standard Library 简明教程

C++ Library - <unordered_map>

Introduction to unordered_map

无序映射类似字典的数据结构。它是一个 (键值对) 对序列，其中每个唯一键仅关联有单个值。它通常被称为关联数组。它能够基于元素的键快速检索各个元素。它还实现了直接访问操作符 (下标操作符 [])，允许使用键值作为参数直接访问已映射值。

Unordered map is dictionary like data structure. It is a sequence of (key, value) pair, where only single value is associated with each unique key. It is often referred as associative array. It enables fast retrieval of individual elements based on their keys. It also implements the direct access operator(subscript operator[]) which allows for direct access of the mapped value using its key value as argument.

无序映射不会根据元素的键或已映射值按照任何特定顺序对元素进行排序，而是根据哈希值按桶组织，以直接通过键值快速访问各个元素。

Unordered map does not sort its element in any particular order with respect to either their key or mapped values, instead organizes into buckets depending on their hash values to allow for fast access to individual elements directly by their key values.

无序映射在通过键访问各个元素时性能优于映射。但对于范围迭代，其性能相当低下。

Unordered map performs better than map while accessing individual elements by their keys. But for range iteration their performance is considerably low.

Definition

以下是来自 <unordered_map> 头文件的 std::unordered_map 定义

Below is definition of std::unordered_map from <unordered_map> header file

template < class Key,
           class T,
           class Hash = hash<Key>,
           class Pred = equal_to<Key>,
           class Alloc = allocator< pair<const Key,T> >
           > class unordered_map;

Parameters

Key − Type of the key.
T − Type of the mapped values.
Hash − A unary function object type which takes an object of type key type as argument and returns a unique value of type size_t based on it.
Pred − A binary predicate that which two arguments of the key type and returns a bool.
Alloc − Type of the allocator object.

Member types

以下成员类型可作为参数或返回类型，由成员函数使用。

Following member types can be used as parameters or return type by member functions.

Sr.No.

Member types

Definition

key_type

Key (First parameter of the template)

mapped_type

T (Second parameter of the template)

value_type

pair<const key_type,mapped_type>

hasher

The third template parameter (defaults to: hash<key_type>)

key_equal

The fourth template parameter (defaults to: equal_to<key_type>)

allocator_type

Alloc (Fifth parameter of the template)

reference

value_type&

const_reference

const value_type&

pointer

allocator_traits<Alloc>::pointer

const_pointer

allocator_traits<Alloc>::const_pointer

iterator

A forward iterator to value_type value_type

const_iterator

A forward iterator to const value_type value_type

local_iterator

A forward iterator to value_type

const_local_iterator

A forward iterator to const value_type

difference_type

ptrdiff_t

size_type

size_t

Functions from <unordered_map>

以下是来自 <unordered_map> 头的所有方法列表。

Below is list of all methods from <unordered_map> header.

Constructors

Sr.No.	Method & Description
1	unordered_map::unordered_map default constructorConstructs an empty unordered_map with zero elements.
2	unordered_map::unordered_map copy constructorConstructs an unordered_map with copy of each elements present in existing unordered_map.
3	unordered_map::unordered_map move constructorConstructs an unordered_map with the contents of other using move semantics.
4	unordered_map::unordered_map range constructorConstructs an unordered_map with as many elements as in range of first to last.
5	unordered_map::unordered_map initializer_list constructor Constructs an unordered_map from initialize list.

Destructor

Sr.No.

Method & Description

unordered_map::~unordered_mapDestroys unordered_map object by deallocating it’s memory.

Member functions

Sr.No.	Method & Description
1	unordered_map::atReturns a reference to the mapped value associated with key k.
2	unordered_map::begin container iteratorReturns an iterator which refers to the first element of the map.
3	unordered_map::begin bucket iteratorReturns an iterator pointing to the first element in one of its buckets.
4	unordered_map::bucketReturns the bucket number where element with key k is located.
5	unordered_map::bucket_countReturns the number of buckets in unordered_map container.
6	unordered_map::bucket_sizeReturns the number of elements presents in the nth bucket.
7	unordered_map::cbegin container iteratorReturns a constant iterator which refers to the first element of the unordered_map.
8	unordered_map::cbegin bucket iteratorReturns a constant iterator pointing to the first element in one of its buckets.
9	unordered_map::cend container iteratorReturns a constant iterator which points to past-the-end element of the unordered_map.
10	unordered_map::cend bucket iteratorReturns a constant iterator which points to past-the-end element in one of its buckets.
11	unordered_map::clearDestroys the unordered_map by removing all elements and sets the size of unordered_map to zero.
12	unordered_map::countReturns the number of mapped values associated with key k.
13	unordered_map::emplaceExtends container by inserting new element.
14	unordered_map::emplace_hintInserts a new element in unordered_map using hint as a position for element.
15	unordered_map::emptyTests whether unordered_map is empty or not.
16	unordered_map::end container iteratorReturns an iterator which points to past-the-end element in the unordered_map.
17	unordered_map::end bucket iteratorReturns an iterator which points to past-the-end element in one of its buckets.
18	unordered_map::equalReturns range of elements that matches specific key.
19	unordered_map::erase position versionRemoves single element of the unordered_map from position.
20	unordered_map::erase key versionRemoves mapped value associated with key k.
21	unordered_map::erase range versionRemoves range of element from the the unordered_map.
22	unordered_map::findFinds an element associated with key k.
23	unordered_map::get_allocatorReturns an allocator associated with unordered_map.
24	unordered_map::hash_functionCalculates the hash function object used by the unordered_map container.
25	unordered_map::insertExtends container by inserting new element in unordered_map.
26	unordered_map::insert move versionExtends container by inserting new element in unordered_map.
27	unordered_map::insert hint versionExtends conta iner by inserting new element in unordered_map.
28	unordered_map::insert move and hint versionExtends unordered_map by inserting new element.
29	unordered_map::insert range versionExtends container by inserting new elements in the unordered_map.
30	unordered_map::insert initializer_list versionExtends map by inserting new element from initializer list.
31	unordered_map::key_eqReturns the function that compares keys for equality.
32	unordered_map::load_factorReturns the current load factor of the unordered_map container.
33	unordered_map::max_bucket_countReturns the maximum number of buckets that the unordered_map container can have.
34	unordered_map::max_load_factor get versionReturns the current maximum load factor for the unordered_map container.
35	unordered_map::max_load_factor set versionAssigns new load factor for the unordered_map container.
36	unordered_map::max_sizeReturns the maximum number of elements can be held by unordered_map.
37	unordered_map::operator= copy versionAssigns new contents to the unordered_map by replacing old ones and modifies size if necessary.
38	unordered_map::operator= move versionMove the contents of one unordered_map into another and modifies size if necessary.
39	unordered_map::operator= initializer_list versionCopy elements from initializer list to unordered_map.
40	unordered_map::operator[]If key k matches an element in the container, then method returns a reference to the element.
41	unordered_map::operator[] move versionIf key k matches an element in the container, then method returns a reference to the element.
42	unordered_map::rehashSets the number of buckets in the container to n or more.
43	unordered_map::reserveSets the number of buckets in the container to the most appropriate to contain at least n elements.
44	unordered_map::sizeReturns the number of elements present in the unordered_map.
45	unordered_map::swapExchanges the content of first unordered_map with another.

Non-member overloaded functions

Sr.No.

Method & Description

unordered_map::operator==Tests whether two unordered_maps are equal or not.

unordered_map::operator!=Tests whether two unordered_maps are equal or not.

unordered_map::swapExchanges the content of first unordered_map with another.

Introduction to unordered_multimap

Unordered_multimap是一个类字典的数据结构。这是一个（键值）对序列，其中不同的元素可能具有相同的键。具有相同键的元素分组在同一个桶中，分割方式使得一个equal_range迭代器可以对所有元素进行迭代。

Unordered_multimap is dictionary like data structure. It is a sequence of (key, value) pair, where different elements can have equivalent keys. Elements with equivalent keys are grouped together in the same bucket and in such a way that an equal_range iterator can iterate through all of them.

Unordered_multimap不按键或映射值对元素进行特殊的顺序排列，而是根据哈希值按桶组织，以通过键值直接快速访问各个元素。

Unordered_multimap does not sort its element in any particular order with respect to either their key or mapped values, instead organizes into buckets depending on their hash values to allow for fast access to individual elements directly by their key values.

Definition

以下是<unordered_map>头文件中std::unordered_multimap的定义

Below is definition of std::unordered_multimap from <unordered_map> header file

template < class Key,
           class T,
           class Hash = hash<Key>,
           class Pred = equal_to<Key>,
           class Alloc = allocator< pair<const Key,T> >
           > class unordered_multimap;

Parameters

Key − Type of the key.
T − Type of the mapped values.
Hash − A unary function object type which takes an object of type key type as argument and returns a unique value of type size_t based on it.
Pred − A binary predicate that which two arguments of the key type and returns a bool.
Alloc − Type of the allocator object. T may be substituted by any other data type including user-defined type.

Member types

以下成员类型可作为参数或返回类型，由成员函数使用。

Following member types can be used as parameters or return type by member functions.

Sr.No.

Member types

Definition

key_type

Key (First parameter of the template)

mapped_type

T (Second parameter of the template)

value_type

pair<const key_type,mapped_type>

hasher

The third template parameter (defaults to: hash<key_type>)

key_equal

The fourth template parameter (defaults to: equal_to<key_type>)

allocator_type

Alloc (Fifth parameter of the template)

reference

value_type&

const_reference

const value_type&

pointer

allocator_traits<Alloc>::pointer

const_pointer

allocator_traits<Alloc>::const_pointer

iterator

A forward iterator to value_type value_type

const_iterator

A forward iterator to const value_type value_type

local_iterator

A forward iterator to value_type

const_local_iterator

A forward iterator to const value_type

difference_type

ptrdiff_t

size_type

size_t

Functions from <unordered_multimap>

以下是来自 <unordered_map> 头的所有方法列表。

Below is list of all methods from <unordered_map> header.

Constructors

Sr.No.	Method & Description
1	unordered_multimap::unordered_multimap() default constructorConstructs an empty unordered_multimap with zero elements.
2	unordered_multimap::unordered_multimap() copy constructorConstructs an unordered_multimap with copy of each elements present in existing unordered_multimap.
3	unordered_multimap::unordered_multimap() move constructorConstructs an unordered_multimap with the contents of other using move semantics.
4	unordered_multimap::unordered_multimap() range constructorConstructs an unordered_multimap with as many elements as in range of first to last.
5	unordered_multimap::unordered_multimap() initializer_list constructorConstructs an unordered_multimap from initialize list.

Destructor

Sr.No.

Method & Description

unordered_multimap::~unordered_multimap()Destroys unordered_multimap object by deallocating it’s memory.

Member functions

Sr.No.	Method & Description
1	unordered_multimap::begin() container iteratorReturns an iterator which refers to the first element of the unordered_mulitmap.
2	unordered_multimap::begin() bucket iteratorReturns an iterator pointing to the first element in one of its buckets.
3	unordered_multimap::bucket()Returns the bucket number where element with key k is located.
4	unordered_multimap::bucket_count()Returns the number of buckets present in unordered_multimap container.
5	unordered_multimap::bucket_size()Returns the number of elements presents in the nth bucket.
6	unordered_multimap::cbegin() container iteratorReturns a constant iterator which refers to the first element of the unordered_multimap.
7	unordered_multimap::cbegin() bucket iteratorReturns a constant iterator pointing to the first element in one of its buckets.
8	unordered_multimap::cend() container iteratorReturns a constant iterator which points to past-the-end element of the unordered_multimap.
9	unordered_multimap::cend() bucket iteratorReturns a constant iterator which points to past-the-end element in one of its buckets.
10	unordered_multimap::clear()Destroys the unordered_multimap by removing all elements and sets the size of unordered_multimap to zero.
11	unordered_multimap::count()Returns the number of mapped values associated with key k.
12	unordered_multimap::emplace()Extends container by inserting new element.
13	unordered_multimap::emplace_hint()Inserts a new element in a unordered_multimap using hint as a position for element.
14	unordered_multimap::empty()Tests whether unordered_multimap is empty or not.
15	unordered_multimap::end() container iteratorReturns an iterator which points to past-the-end element in the unordered_multimap.
16	unordered_multimap::end() bucket iteratorReturns an iterator which points to past-the-end element in one of its buckets.
17	unordered_multimap::equal_range()Returns range of elements that matches specific key.
18	unordered_multimap::erase() position versionRemoves single element of the unordered_multimap from position.
19	unordered_multimap::erase() key versionRemoves mapped value associated with key k.
20	unordered_multimap::erase() range versionRemoves range of element from the the unordered_multimap.
21	unordered_multimap::find()Finds an element associated with key k.
22	unordered_multimap::get_allocator()Returns an allocator associated with unordered_multimap.
23	unordered_multimap::hash_function()Calculates the hash function object used by the unordered_multimap container.
24	unordered_multimap::insert() value versionExtends container by inserting new element in unordered_multimap.
25	unordered_multimap::insert() move versionExtends unordered_multimap by inserting new element.
26	unordered_multimap::insert() hint versionExtends container by inserting new element in unordered_multimap.
27	unordered_multimap::insert() hint move versionExtends container by inserting new element in unordered_multimap by using move semantics.
28	unordered_multimap::insert() range versionExtends container by inserting new elements in the unordered_multimap.
29	unordered_multimap::insert() initializer_list versionExtends unordered_multimap by inserting new element from initializer list.
30	unordered_multimap::key_eq()Returns the function that compares keys for equality.
31	unordered_multimap::load_factor()Returns the current load factor of the unordered_multimap container.
32	unordered_multimap::max_bucket_count()Returns the maximum number of buckets that the unordered_multimap container can have.
33	unordered_multimap::max_load_factor() get versionReturns the current maximum load factor for the unordered_multimap container.
34	unordered_multimap::max_load_factor() set versionAssigns new load factor for the unordered_multimap container.
35	unordered_multimap::max_size()Returns the maximum number of elements can be held by unordered_multimap.
36	unordered_multimap::operator=() copy versionAssigns new contents to the unordered_multimap by replacing old ones and modifies size if necessary.
37	unordered_multimap::operator=() move versionMove the contents of one unordered_multimap into another and modifies size if necessary.
38	unordered_multimap::operator=() initializer_list versionCopy elements from initializer list to unordered_multimap.
39	unordered_multimap::rehash()Sets the number of buckets in the container to n or more.
40	unordered_multimap::reserve()Sets the number of buckets in the container to the most appropriate to contain at least n elements.
41	unordered_multimap::size()Returns the number of elements present in the unordered_multimap.
42	unordered_multimap::swap()Exchanges the content of first unordered_multimap with another.

Non-member overloaded functions

Sr.No.

Method & Description

unordered_multimap::operator==()Tests whether two unordered_multimaps are equal or not.

unordered_multimap::operator!=()Tests whether two unordered_multimaps are equal or not.

unordered_multimap::swap()Exchanges the content of first unordered_multimap with another.