Cpp Standard Library 简明教程

C++ Library - <map>

Introduction to map

Map 就像词典中的数据结构。它是（键值）对的序列，其中每个唯一键只关联单个值。它通常被称为关联数组。

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.

在 map 中，键值通常用于对元素进行排序。对于 map 数据类型，键和值可以不同，表示为

In map key values generally used to sort the elements. For map data type of key and value can differ and it is represented as

typedef pair<const Key, T> value_type;

Map 通常实现为二叉搜索树。

Maps are typically implemented as Binary Search Tree.

零大小的地图也是合法的。在这种情况下，map.begin() 和 map.end() 指向同一个位置。

Zero sized maps are also valid. In that case map.begin() and map.end() points to same location.

Definition

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

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

template < class Key,
           class T,
           class Compare = less<Key>,
           class Alloc = allocator<pair<const Key,T> >
           > class map;

Parameters

Key − Type of the key.
T − Type of the mapped values.
Compare − A binary predicate that takes two element keys as arguments and returns a bool.
Alloc − Type of the allocator object.

T 可以替换为任何其他数据类型，包括用户自定义类型。

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)

key_compare

Compare (Third parameter of the template)

allocator_type

Alloc (Fourth parameter of the template)

value_type

pair<const key_type,mapped_type>

value_compare

Nested function class to compare elements

reference

allocator_type::reference

const_reference

allocator_type::const_reference

pointer

allocator_type::pointer

const_pointer

allocator_type::const_pointer

iterator

bi-directional iterator to value_type

const_iterator

bi-directional iterator to const value_type

reverse_iterator

reverse iterator

const_reverse_iterator

constant reverse iterator

difference_type

ptrdiff_t

size_type

size_t

Functions from <map>

以下是 <map> header 中所有方法的列表。

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

Constructors

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

Destructor

Sr.No.

Method & Description

map::~mapDestroys map object by deallocating it’s memory.

Member functions

Sr.No.	Method & Description
1	map::atReturns a reference to the mapped value associated with key k.
2	map::beginReturns a iterator which refers to the first element of the map.
3	map::cbeginReturns a constant iterator which refers to the first element of the map.
4	map::cendReturns a constant iterator which points to past-the-end element of the map.
5	map::clearDestroys the map by removing all elements and sets size of map to zero.
6	map::countReturns number of mapped values associated with key k.
7	map::crbeginReturns a constant reverse iterator which points to the last element of the container i.
8	map::crendReturns a constant reverse iterator which points to the theoretical element preceding the first element in the container i.
9	map::emplaceExtends container by inserting new element.
10	map::emplace_hint hint versionInserts a new element in a map using hint as a position for element.
11	map::emptyTests whether map is empty or not.
12	map::endReturns an iterator which points to past-the-end element in the map.
13	map::equal_rangeReturns range of elements that matches specific key.
14	map::erase position versionRemoves single element of the map from position.
15	map::erase position versionRemoves single element of the map from position.
16	map::erase keyRemoves mapped value associated with key k.
17	map::erase range versionRemoves range of element from the the map.
18	map::erase range versionRemoves range of element from the the map.
19	map::findFinds an element associated with key k.
20	map::get_allocatorReturns an allocator associated with map.
21	map::insert single elementExtends container by inserting new element in map.
22	map::insert hint versionExtends container by inserting new element in map.
23	map::insert range versionExtends container by inserting new elements in the map.
24	map::insert move hint verstionExtends map by inserting new element.
25	map::insert initializer list versionExtends map by inserting new element from initializer list.
26	map::key_compReturns a function object that compares the keys, which is a copy of this container’s constructor argument comp.
27	map::lower_boundReturns an iterator pointing to the first element which is not less than key k.
28	map::max_sizeReturns the maximum number of elements can be held by map.
29	map::operator= copy versionAssign new contents to the map by replacing old ones and modifies size if necessary.
30	map::operator= move versionMove the contents of one map into another and modifies size if necessary.
31	map::operator= initializer list versionCopy elements from initializer list to map.
32	map::operator[] copy versionIf key k matches an element in the container, then method returns a reference to the element.
33	map::operator[] move versionIf key k matches an element in the container, then method returns a reference to the element.
34	map::rbeginReturns a reverse iterator which points to the last element of the map.
35	map::rendReturns a reverse iterator which points to the reverse end of the map i.
36	map::sizeReturns the number of elements present in the map.
37	map::swapExchanges the content of map with contents of map x.
38	map::upper_boundReturns an iterator pointing to the first element which is greater than key k.
39	map::value_compReturns a function object that compares objects of type std::map::value_type.

Non-member overloaded functions

Sr.No.	Method & Description
1	[role="bare"]../cpp_standard_library/cpp_map_operator_equal_to.htmlTests whether two maps are equal or not.
2	operator!=Tests whether two maps are equal or not.
3	operator<Tests whether first map is less than other or not.
4	map::operator⇐Tests whether first map is less than or equal to other or not.
5	operator>Tests whether first map is greater than other or not.
6	operator>=Tests whether first map is greater than or equal to other or not.
7	swap()Exchanges the content of map with contents of map x.

Introduction to multimap

多重映射是类似于字典的数据结构。它是 (键, 值) 对的序列，其中多个值可以与等效的键相关联。它通常被称为关联数组。

Multimap is dictionary like data structure. It is a sequence of (key, value) pair, where multiple values can be associate with equivalent keys. It is often referred as associative array.

在多重映射中，键值通常用于对元素进行排序。对于多重映射，键和值的数据类型可以不同，表示如下：

In multimap key values generally used to sort the elements. For multimap data type of key and value can differ and it is represented as

typedef pair<const Key, T> value_type;

多重映射通常作为二叉查找树来实现。

Multimaps are typically implemented as Binary Search Tree.

零大小的多重映射也是有效的。在这种情况下，multimap.begin() 和 multimap.end() 指向同一位置。

Zero sized multimaps are also valid. In that case multimap.begin() and multimap.end() points to same location.

Definition

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

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

template < class Key,
           class T,
           class Compare = less<Key>,
           class Alloc = allocator<pair<const Key,T> >
           > class multimap;

Parameters

Key − Type of the key.
T − Type of the mapped values.
Compare − A binary predicate that takes two element keys as arguments 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)

key_compare

Compare (Third parameter of the template)

allocator_type

Alloc (Fourth parameter of the template)

value_type

pair<const key_type,mapped_type>

value_compare

Nested function class to compare elements

reference

allocator_type::reference

const_reference

allocator_type::const_reference

pointer

allocator_type::pointer

const_pointer

allocator_type::const_pointer

iterator

bi-directional iterator to value_type

const_iterator

bi-directional iterator to const value_type

reverse_iterator

reverse iterator

const_reverse_iterator

constant reverse iterator

difference_type

ptrdiff_t

size_type

size_t

Functions from <multimap>

以下是 <multimap> 头文件中的所有方法列表。

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

Constructors

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

Destructor

Sr.No.

Method & Description

multimap::~multimapDestroys multimap object by deallocating it’s memory.

Member functions

Sr.No.	Method & Description
1	multimap::beginReturns a iterator which refers to the first element of the multimap.
2	multimap::cbeginReturns a constant iterator which refers to the first element of the multimap.
3	multimap::cendReturns a constant iterator which points to past-the-end element of the multimap.
4	multimap::clearDestroys the multimap by removing all elements and sets size of multimap to zero.
5	multimap::countReturns number of multimapped values associated with key k.
6	multimap::crbeginReturns a constant reverse iterator which points to the last element of the container.
7	multimap::crendReturns a constant reverse iterator which points to the theoretical element preceding the first element in the container.
8	multimap::emplaceExtends container by inserting new element.
9	multimap::emplace_hint hint versionInserts a new element in a multimap using hint as a position for element.
10	multimap::emptyTests whether multimap is empty or not.
11	multimap::endReturns an iterator which points to past-the-end element in the multimap.
12	multimap::equal_rangeReturns range of elements that matches specific key.
13	multimap::erase position versionRemoves single element of the multimap from position.
14	multimap::erase position versionRemoves single element of the multimap from position.
15	multimap::erase keyRemoves mapped value associated with key k.
16	multimap::erase range versionRemoves range of element from the the multimap.
17	multimap::erase range versionRemoves range of element from the the multimap.
18	multimap::findFinds an element associated with key k.
19	multimap::get_allocatorReturns an allocator associated with multimap.
20	multimap::insert single elementExtends container by inserting new element in multimap.
21	multimap::insert hint versionExtends container by inserting new element in multimap.
22	multimap::insert range versionExtends container by inserting new elements in the multimap.
23	multimap::insert move hint verstionExtends multimap by inserting new element.
24	multimap::insert initializer list versionExtends multimap by inserting new element from initializer list.
25	multimap::key_compReturns a function object that compares the keys, which is a copy of this container’s constructor argument comp.
26	multimap::lower_boundReturns an iterator pointing to the first element which is not less than key k.
27	multimap::max_sizeReturns the maximum number of elements can be held by multimap.
28	multimap::operator= copy versionAssign new contents to the multimap by replacing old ones and modifies size if necessary.
29	multimap::operator= move versionMove the contents of one multimap into another and modifies size if necessary.
30	multimap::operator= initializer list versionCopy elements from initializer list to multimap.
31	multimap::rbeginReturns a reverse iterator which points to the last element of the multimap.
32	multimap::rendReturns a reverse iterator which points to the reverse end of the multimap.
33	multimap::sizeReturns the number of elements present in the multimap.
34	multimap::swapExchanges the content of multimap with contents of multimap x.
35	multimap::upper_boundReturns an iterator pointing to the first element which is greater than key k.
36	multimap::value_compReturns a function object that compares objects of type std::multimap::value_type.

Non-member overloaded functions

Sr.No.	Method & Description
1	[role="bare"]../cpp_standard_library/cpp_multimap_operator_equal_to.htmlTests whether two multimaps are equal or not.
2	operator!=Tests whether two multimaps are equal or not.
3	operator<Tests whether first multimap is less than other or not.
4	multimap::operator⇐Tests whether first multimap is less than or equal to other or not.
5	operator>Tests whether first multimap is greater than other or not.
6	operator>=Tests whether first multimap is greater than or equal to other or not.
7	swap()Exchanges the content of multimap with contents of multimap x.