我是靠谱客的博主 发嗲流沙,这篇文章主要介绍跟我学C++中级篇——STL的容器Map三、源码分析,现在分享给大家,希望可以做个参考。

一、关联容器map和multimap

C++STL库中,有一组关联容器,其中就包含map,map顾名思意,就是一个映射,学过基础数学的都明白,STL中的map底层是通过红黑树来实现的,这个可以参看一下《STL源码剖析》中,对红黑树的详细说明,包括单旋,双旋转等。在一些算法书籍上也总结很多的优秀的学习方法,这里就不再详细说明红黑树的算法实现了。
看一下c++ STL中的定义:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//Map template< class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<const Key, T> > > class map; //since c++17 namespace pmr { template <class Key, class T, class Compare = std::less<Key>> using map = std::map<Key, T, Compare, std::pmr::polymorphic_allocator<std::pair<const Key,T>>> } //multimap template< class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<const Key, T> > > class multimap; //since C++ 17 namespace pmr { template <class Key, class T, class Compare = std::less<Key>> using multimap = std::multimap<Key, T, Compare, std::pmr::polymorphic_allocator<std::pair<const Key,T>>>; }

二、二者的不同

STL中有Map和Multimap两种,都是将KEY/VALUE pair做为元素基本单位,即使没有学过这个的,但是搞过NOSQL的可能也一下子也能明白。区别在于,Map是一一映射,而Multimap是一对多映射。它们两个都是根据Key值进行自动排序的,这才是重点。Key和Value都必须是可拷贝或者可移动的(Move语义),假如指定了排序规则,Key还必须是可比较的。
在底层的实现中,由于后者存在有相同的Key,所以在插入时,会使用equal而不是unique来进行操作RB_tree.

三、源码分析

看一下源码:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
template <class _Kty, class _Ty, class _Pr = less<_Kty>, class _Alloc = allocator<pair<const _Kty, _Ty>>> class map : public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false>> { // ordered red-black tree of {key, mapped} values, unique keys public: static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<pair<const _Kty, _Ty>, typename _Alloc::value_type>, _MISMATCHED_ALLOCATOR_MESSAGE("map<Key, Value, Compare, Allocator>", "pair<const Key, Value>")); using _Mybase = _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false>>; using _Nodeptr = typename _Mybase::_Nodeptr; using key_type = _Kty; using mapped_type = _Ty; using key_compare = _Pr; using value_compare = typename _Mybase::value_compare; using value_type = pair<const _Kty, _Ty>; ...... using const_reference = const value_type&; using iterator = typename _Mybase::iterator; using const_iterator = typename _Mybase::const_iterator; using reverse_iterator = typename _Mybase::reverse_iterator; using const_reverse_iterator = typename _Mybase::const_reverse_iterator; using _Alnode = typename _Mybase::_Alnode; using _Alnode_traits = typename _Mybase::_Alnode_traits; #if _HAS_CXX17 using insert_return_type = _Insert_return_type<iterator, typename _Mybase::node_type>; #endif // _HAS_CXX17 map() : _Mybase(key_compare()) {} explicit map(const allocator_type& _Al) : _Mybase(key_compare(), _Al) {} map(const map& _Right) : _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(_Right._Getal())) {} map(const map& _Right, const allocator_type& _Al) : _Mybase(_Right, _Al) {} explicit map(const key_compare& _Pred) : _Mybase(_Pred) {} map(const key_compare& _Pred, const allocator_type& _Al) : _Mybase(_Pred, _Al) {} template <class _Iter> map(_Iter _First, _Iter _Last) : _Mybase(key_compare()) { insert(_First, _Last); } template <class _Iter> map(_Iter _First, _Iter _Last, const key_compare& _Pred) : _Mybase(_Pred) { insert(_First, _Last); } template <class _Iter> map(_Iter _First, _Iter _Last, const allocator_type& _Al) : _Mybase(key_compare(), _Al) { insert(_First, _Last); } template <class _Iter> map(_Iter _First, _Iter _Last, const key_compare& _Pred, const allocator_type& _Al) : _Mybase(_Pred, _Al) { insert(_First, _Last); } map& operator=(const map& _Right) { _Mybase::operator=(_Right); return *this; } map(map&& _Right) : _Mybase(_STD move(_Right)) {} map(map&& _Right, const allocator_type& _Al) : _Mybase(_STD move(_Right), _Al) {} map& operator=(map&& _Right) noexcept(_Alnode_traits::is_always_equal::value&& is_nothrow_move_assignable_v<_Pr>) { _Mybase::operator=(_STD move(_Right)); return *this; } mapped_type& operator[](key_type&& _Keyval) { // find element matching _Keyval or insert value-initialized value return _Try_emplace(_STD move(_Keyval)).first->_Myval.second; } void swap(map& _Right) noexcept(noexcept(_Mybase::swap(_Right))) { _Mybase::swap(_Right); } using _Mybase::insert; template <class _Valty, enable_if_t<is_constructible_v<value_type, _Valty>, int> = 0> pair<iterator, bool> insert(_Valty&& _Val) { return this->emplace(_STD forward<_Valty>(_Val)); } template <class _Valty, enable_if_t<is_constructible_v<value_type, _Valty>, int> = 0> iterator insert(const_iterator _Where, _Valty&& _Val) { return this->emplace_hint(_Where, _STD forward<_Valty>(_Val)); } private: template <class _Keyty, class... _Mappedty> pair<_Nodeptr, bool> _Try_emplace(_Keyty&& _Keyval, _Mappedty&&... _Mapval) { const auto _Loc = _Mybase::_Find_lower_bound(_Keyval); if (_Mybase::_Lower_bound_duplicate(_Loc._Bound, _Keyval)) { return {_Loc._Bound, false}; } _Mybase::_Check_grow_by_1(); const auto _Scary = _Mybase::_Get_scary(); const auto _Inserted = _Tree_temp_node<_Alnode>(_Mybase::_Getal(), _Scary->_Myhead, piecewise_construct, _STD forward_as_tuple(_STD forward<_Keyty>(_Keyval)), _STD forward_as_tuple(_STD forward<_Mappedty>(_Mapval)...)) ._Release(); // nothrow hereafter return {_Scary->_Insert_node(_Loc._Location, _Inserted), true}; } ...... public: template <class... _Mappedty> pair<iterator, bool> try_emplace(const key_type& _Keyval, _Mappedty&&... _Mapval) { const auto _Result = _Try_emplace(_Keyval, _STD forward<_Mappedty>(_Mapval)...); return {iterator(_Result.first, _Mybase::_Get_scary()), _Result.second}; } ...... }; template <class _Traits> class _Tree { // ordered red-black tree for map/multimap/set/multiset public: using value_type = typename _Traits::value_type; using allocator_type = typename _Traits::allocator_type; protected: using _Alty = _Rebind_alloc_t<allocator_type, value_type>; using _Alty_traits = allocator_traits<_Alty>; using _Node = _Tree_node<value_type, typename _Alty_traits::void_pointer>; using _Alnode = _Rebind_alloc_t<allocator_type, _Node>; using _Alnode_traits = allocator_traits<_Alnode>; using _Nodeptr = typename _Alnode_traits::pointer; using _Scary_val = _Tree_val<conditional_t<_Is_simple_alloc_v<_Alnode>, _Tree_simple_types<value_type>, _Tree_iter_types<value_type, typename _Alty_traits::size_type, typename _Alty_traits::difference_type, typename _Alty_traits::pointer, typename _Alty_traits::const_pointer, value_type&, const value_type&, _Nodeptr>>>; static constexpr bool _Multi = _Traits::_Multi; enum _Redbl { // colors for link to parent _Red, _Black }; ...... };

从上面可以看到它的基本数据结构是以Tree为定义的,注释中“ordered red-black tree for map/multimap/set/multiset”说明了所有。

四、应用例程

看一下具体的应用例程(https://en.cppreference.com/):

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream> #include <map> #include <string> #include <string_view> struct FatKey { int x; int data[1000]; }; struct LightKey { int x; }; // Note: as detailed above, the container must use std::less<> (or other // transparent Comparator) to access these overloads. // This includes standard overloads, such as between std::string and std::string_view. bool operator<(const FatKey& fk, const LightKey& lk) { return fk.x < lk.x; } bool operator<(const LightKey& lk, const FatKey& fk) { return lk.x < fk.x; } bool operator<(const FatKey& fk1, const FatKey& fk2) { return fk1.x < fk2.x; } void print_map(std::string_view comment, const std::map<std::string, int>& m) { std::cout << comment; for (const auto& [key, value] : m) { std::cout << key << " = " << value << "; "; } std::cout << "n"; } int main() { // Create a map of three strings (that map to integers) std::map<std::string, int> m { {"CPU", 10}, {"GPU", 15}, {"RAM", 20}, }; print_map("Initial map: ", m); m["CPU"] = 25; // update an existing value m["SSD"] = 30; // insert a new value print_map("Updated map: ", m); //multimap demo std::multimap<int,char> example = {{1,'a'},{2,'b'}}; auto search = example.find(2); if (search != example.end()) { std::cout << "Found " << search->first << " " << search->second << 'n'; } else { std::cout << "Not foundn"; } // transparent comparison demo std::multimap<FatKey, char, std::less<>> example2 = { { {1, {} },'a'}, { {2, {} },'b'} }; LightKey lk = {2}; auto search2 = example2.find(lk); if (search2 != example2.end()) { std::cout << "Found " << search2->first.x << " " << search2->second << 'n'; } else { std::cout << "Not foundn"; } // Obtaining const iterators. // Compiler decides whether to return iterator of (non) const type by way of accessing // map; to prevent modification on purpose, one of easiest choices is to access map by // const reference. const auto& example2ref = example2; auto search3 = example2ref.find(lk); if (search3 != example2.end()) { std::cout << "Found " << search3->first.x << ' ' << search3->second << 'n'; // search3->second = 'c'; // error: assignment of member // 'std::pair<const FatKey, char>::second' // in read-only object } }

运行结果是:

复制代码
1
2
3
4
5
6
7
Initial map: CPU = 10; GPU = 15; RAM = 20; Updated map: CPU = 25; GPU = 15; RAM = 20; SSD = 30; Found 2 b Found 2 b Found 2 b

五、注意点

使用Map赋值时,尽量不要使用类似数组方式的形式进行赋值,如 map_test[3] = “test”,这种方式会导致如果没有KEY(3)对应的元素,就自动插入这个值,而产生不必要的麻烦。同样,查找一定要使用find函数而不是挨个自己比较。
Map和Multimap在新的标准环境下,一般不推荐使用了,主要是这东西线程不安全操作起来还有各种小细节需要考虑,搞不好就进了坑了。基本上现在推荐使用的都是无序容器unordered_map,在后面的章节会对其进行详细分析。

六、总结

明白这两个Map在意义在于掌握STL中的映射使用,更重要的是明白RB_Tree的应用,明白使用库其实是屏蔽了复杂的数据结构在背后的,而不是用不到数据结构。
在这里插入图片描述

最后

以上就是发嗲流沙最近收集整理的关于跟我学C++中级篇——STL的容器Map三、源码分析的全部内容,更多相关跟我学C++中级篇——STL内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(59)

评论列表共有 0 条评论

立即
投稿
返回
顶部