映射
Map的特性是：所有的元素都会根据键值自动排列。Map的所有元素都是pair，同时拥有实值(Value) 和 键值(Key)。Pair的第一元素被视为键值，第二元素被视为实值。Map不允许两个元素拥有相同的键值。
下面是Pair的定义：
|
1 2 3 4 5 6 7 8 9 10 11 12 |
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() : first(T1()), second(T2()) {} pair(const T1& a, const T2& b) : first(a), second(b) {} } |
我们可以通过map的迭代器改变map的元素内容吗？
如果是想要修正元素的键值，那是不行的，因为map元素的键值关系到了map的元素的排列顺序。任意改变map的元素键值将会严重破坏map组织。如果是修改元素的实值的话，那是可以的，因为并不会影响map的排列规则。
因此，map iterators 既不是一种constant iterator ，也不是一种 mutable iterators
map 和 list 在迭代器方面有一点相似，就是进行插入和删除操作的时候操作之前的迭代器在操作之后都是有效的。当然删除元素操作所删除的迭代器除外。
Map的 底层是 RBTree，Map 具体实现如下：
|
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 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 |
template <class Key, class T, class Compare = less<Key> class Alloc = alloc> class map { public: //typedefs: 类型定义 typedef Key key_type; typedef T data_type; typedef T mapped_type; typedef pair<const Key, T> value_type; //元素类型 typedef Compare key_compare; //键值比较函数 //以下定义一个 functor，其作用就是调用"元素比较函数" class value_compare : public binary_function<value_type, value_type, bool> { friend class map<Key, T, Compare, Alloc>; protected: Compare comp; value_compare(Compare c) : comp(c) {} public: bool operator()(const value_type& x, const value_type& y) const { return comp(x.first, y.first); } } private: //以map元素型别的第一型别作为RB-Tree节点键值型别 typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type; rep_type t; public: typedef typename rep_type::pointer pointer; typedef typename rep_type::const_pointer const_pointer; typedef typename rep_type::reference reference; typedef typename rep_type::const_reference const_reference; typedef typename rep_type::iterator iterator; //注意上一行,map允许用户通过迭代器修改实值 typedef typename rep_type::const_iterator const_iterator; typedef typename rep_type::reverse_iterator reverse_iterator; typedef typename rep_type::const_reverse_iterator const_reverse_iterator; typedef typename rep_type::size_type size_type; typedef typename rep_type::difference_type difference_type; //allocation deallocation //注意Map是用的insert_unique //MultiMap采用insert_equal map() : t(Compare()){} explicit map(const Compare& comp) : t(comp) {} template <class InputIterator> map(InputIterator first, InputIterator last) : t(Compare()) { t.insert_unique(first, last); } template <class InputIterator> map(InputIterator first, InputIterator last, const Compare& comp) : t(comp) { t.insert_unique(first, last); } map(const set<Key, Compare, Alloc>& x) : t(x.t) {} map <key, Compare, Alloc>& operator=(const map<Key, Compare, Alloc> &x) { t = x.t; return *this; } //以下所有Map的操作，RBTree都已经提供了，所以只用传递调用就行了 //Accessors: key_compare key_comp() const { return t.key_comp(); } value_compare value_comp() const { return t.key_comp(); } iterator begin() const { return t.begin(); } iterator end() const { return t.end(); } reverse_iterator rbegin() const { return t.rbegin(); } reverse_iterator rend() const { return t.rend(); } bool empty() const { return t.empty(); } size_type size() const { return t.size(); } size_type max_size() const { return t.max_size(); } void swap(set<Key, Compare, Alloc>& x) { t.swap(x.t); } //insert erase pair <iterator, bool> insert(const value_type& x) { return t.insert_unique(x); } iterator insert(iterator position, const value_type& x) { return t.insert_unique(position, x); } template <class InputIterator> void insert(InputIterator first, InputIterator last) { t.insert_unique(first, last); } void erase(iterator position) { t.erase(position); } size_type erase(const key_type& x) { return t.erase(x); } void erase(iterator first, iterator last) { t.erase(first, last); } void clear() { t.clear(); } //map operators iterator find(const key_type& x) const { return t.find(x); } const_iterator find(const key_type& x) const { return t.find(x); } size_type count(const key_type& x) const { return t.count(x); } iterator lower_bound(const key_type& x) const { return t.lower_bound(x); } const_iterator lower_bound(const key_type& x) const { return t.lower_bound(x); } iterator upper_bound(const key_type& x) const { return t.upper_bound(x); } const_iterator upper_bound(const key_type& x) const { return t.upper_bound(x); } pair<iterator, iterator>equal_range(const key_type& x) const { return t.equal_range(x); } pair<const_iterator, const_iterator>equal_range(const key_type& x) const { return t.equal_range(x); } friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&); friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&); }; template <class Key, class T, class Compare, class Alloc> inline bool operator == (const map<Key, T, Compare, Alloc>& x, const map<key, T, Compare, Alloc>& y) { return x.t == y.t; } template <class Key, class T, class Compare, class Alloc> inline bool operator < (const map<Key, T, Compare, Alloc>& x, const map<key, T, Compare, Alloc>& y) { return x.t < y.t; } |
注释不多，看完就懂了。
同样的一个测试程序：
|
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 |
#include <iostream> #include <map> #include <string> #include <algorithm> using namespace std; int main() { map <string, int> simap; //string为Key int为Value simap[string("Test1")] = 1; simap[string("Test2")] = 2; simap[string("Test3")] = 3; simap[string("Test4")] = 4; pair<string, int> value(string("Test5"), 5); simap.insert(value); map<string, int>::iterator simap_iter = simap.begin(); for( ; simap_iter != simap.end(); ++simap_iter) { cout << simap_iter->first << " " << simap_iter->second << endl; } int number = simap[string("Test1")]; cout << number << endl; map<string, int>::iterator ite1; //关联式容器 自带的find 比算法的find好 //因为效率更好 ite1 = simap.find(string("Test6")); if(ite1 == simap.end()) { cout << "Test6 not found" << endl; } ite1 = simap.find(string("Test2")); if(ite1 != simap.end()) { cout << "Test2 found" << endl; } ite1->second = 9; //可以通过迭代器改变Value的值 int number2 = simap[string("Test2")]; cout << number2 << endl; } |
然后这里详细讲述一下 map的 [] 操作符…这个操作符真可谓是复杂。
不过我觉得设计的很精妙啊!实现函数如下：
|
1 2 3 4 |
T& operator[](const key_type& k) { return (*((insert_unique(value_type(k, T()))).first)).second; } |
一层一层真是难…我们来分析下：
首先根据键值和实值，我们造一个元素出来…
|
1 |
value_type(k, T()) |
然后插入到map里面去
|
1 |
insert_unique( value_type(k, T()) ) |
插入返回一个pair，第一个元素是迭代器，指向插入的元素或者之前已经存在的相同键值的元素。
所以取出第一个元素first
|
1 |
(insert_unique(value_type(k, T()))).first |
这个first 是一个迭代器，指向被插入的元素
所以我们对他进行解析(解引用，提领)：
|
1 |
*((insert_unique(value_type(k, T()))).first) |
得到的是map的元素，由键值和实值组成，第二元素就是实值，第一元素是键值
取第二元素，得到它的实值。
|
1 |
(*((insert_unique(value_type(k, T()))).first)).second; |
最后注意，是以引用方式传递过去的。这样它作为左值和右值都可以。
【STL】Map