STL关联式容器之map_stl关联式容器map

map概述
map的特性是，所有元素都会根据元素的键值自动被排序。map的所有元素都是pari，同时拥有实值（value）和键值（key）。pari的第一元素被视为键值，第二元素被视为实值。map不允许两个元素拥有相同的键值。下面是<stl_pari.h>中的pari定义：

template<calss T1,class T2>
struct pari
{
     typedef T1 first_type;
     typedef T2 second_type;
     T1 first;// 注意，它是public
     T2 second;// 注意，它是public
     pari(): first(T1(), second(T2)){}
     pari(const T1& a, const T2& b): first(a), second(b){}
};
1
2
3
4
5
6
7
8
9
10

我们可以通过map的迭代器改变map的元素内容么？如果想要修正元素的键值，答案是不行。因为map元素的键值关系到map元素的排列规则。任意改变map元素键值将会严重破坏map组织，但如果想要修正元素的实值，答案是可以，因为map元素的实值并不影响map元素的排列规则。因此，map iterators既不是一种constant iterators，也不是一种mutable iterators。
map拥有和list相同的某些性质：当客户端对它进行元素新增操作（insert）或删除操作（erase）时，操作之前的所有迭代器，在操作完成之后都依然有效。当然，被删除的那个元素的迭代器必然是个例外。
由于RB-tree是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的STL map即以RB-tree为底层机制。又由于map所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的map操作行为，都只是转调用RB-tree的操作行为而已。
map的架构：

map源码摘录

//注意，以下key为键值（key）型别，T为实值型别
template<class Key,class T, calss 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>
            {
 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:    
           //以下定义表述型别（representation type）。一map元素型别（一个ipair）的第一型别，作为RB-tree节点的键值型别
           typedef rb_tree<value_type, value_type, selectlst<value_type>,key_compare,Alloc> rep_type;
           rep_type t;//以红黑树（RB-tree）表现map
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并不像set一样将iterator定义为RB-tree的
          //const_iterator.因为它允许用户通过其迭代器修改元素的实值（value）
          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::differnece_type difference_type;
          //allocation/deallocation
          //注意map一定使用底层RB-tree的insert_unique()而非insert_equal()
          //multimap才使用insert_equal()
          //因为map不允许相同键值存在，multimap才允许相同键值存在
          map(): t(Compare()){}
          explicit map(const Compare& comp): t(comp){}

          template<class InputItertor>
          map(InputIterator  first, InputIterator last): t(Compare()){t.insert_unique(first,last);}
           template<class InputItertor>
          map(InputIterator  first, InputIterator last, const Compare& comp): t(comp){t.insert_unique(first,last);}
          map(const map<Key, T, Compare, Alloc>& x):t(x.t){}
          map<Key, T, Compare,Alloc>& operator=(const map<Key, T, Compare, Alloc>& x){t=x.t;return *this;}

          //accessors:
          //以下所有的map操作行为，RB-tree都已提供
          key_compare key_comp() const {return t.key_comp();}
          value_compare value_comp() const {return value_compare(t.key_comp());}
          iterator begin() const {return t,begin();}
          const_iterator begin() const{return t.begin();}
          iterator end(){return t.end();}
          const_iterator end() const{return t.end();}
          reverse_iterator rbegin() {return t.rbegin();}
          const_revserse_iterator rbegin() const {return t.begin();}
          reverse_iterator rend(){return t.rend();}
          const_reverse_iterator rend()const {return t.rend();}
          bool empty() const {return t.empty();}
          size_type size()const {return t.szie();}
          size_type max_size() const {rturn t.max_size();}
          T& operator[](const key_type& k)
          {
                return (*(insert(value_type(k,T())).first)).second;
          }
          void swap(map<Key,T,Compare,Alloc>& x){t.swap(x.t);}
          //insert/erase
          //注意以下insert的操作返回的型别
          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<calss 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.erasw(first,last);}
          void clear(){t.clear();}

         //map operations:
         iterator find(const key_type& x){return t.find();}
         const_iterator find(const key)type& x)const {return t.find(x);}
         size_type count(const key_type&x){return t.find(x);}
         iterator lower_bound(const key_type& x){return t.lower_bount(x);}
         const_iterator lower_bound(const key_type& x) const {return t.lower_bound(x);}
         iterator upper_bound(const key_type& x){return t.upper_bound(x);}
         const_iterator upper_bound(const key_type& x) const{return t.lower_bound(x);}
         pair<iterator, ioterator>equal_range(const key_type& x)
         {return t.equal_range(x);}
         pair<const_iterator,const_iteator>equal_range(const key_type&x)
         {return t.equal_range(x);}
         friend bool operator==_STL_NULL_TMPL_ARGS(const map& x)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<calss Key,class T,class Compare,Alloc>
nline bool operator<(const map<Key,T, Compare,Alloc>& x,const map<Key, T, Compare,Alloc& y>){return x.t<y.t;}
//(md,终于敲完了，要吐了【吐血】)
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