C++ STL源码剖析之map、multimap、initializer_list

map/multimap 以rb_tree为底层结构，因此有元素自动排序特点，排序的依据是key。

map/multimap提供"遍历"操作及iterators。按正常规则(++iter)遍历，便能够获得排序状态。

我们无法使用map/multimap的iterators改变元素的key(因为key有其严谨排列规则)，但可以用它来改变元素的data。因此map/multimap内部自动将用户指定的key type设定为const，如此便能进制用户对元素key的赋值。

map元素的key必须独立无二，因此其insert使用的是rb_tree的_M_insert_unique()，而multimap元素的key可以重复，因此其insert使用的是rb_tree的_M_insert_equal()。

对于本节，我们将从下面几个内容阐述：

  • map的key为key,value为key+data,与set是不同的，set是key就是value，value就是key。
  • map的key不可修改,map与multimap的插入调用函数不同，影响了其key是否对应value。
  • initializer_list使用
  • map有[]操作符，而multimap没有[]操作符。

1.map

key为key，value为key+data

下面map中我们可以看到value_type为一个pair。

  1. template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
  2. typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  3. class map
  4. {
  5. public:
  6.     typedef _Key                                          key_type;
  7.     typedef _Tp                                           mapped_type;
  8.     typedef std::pair<const _Key, _Tp>                    value_type;
  9.     typedef _Compare                                      key_compare;
  10.     typedef _Alloc                                        allocator_type;
  11. private:
  12.     // key为key,value为key+data
  13.     typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
  14.             key_compare, _Pair_alloc_type> _Rep_type;
  16.     /// The actual tree structure.
  17.     _Rep_type _M_t;
  18. };

map_data.png

上述默认的仿函数为_Select1st，我们在stl_function中看到源码如下：

  1. template<typename _Pair>
  2. struct _Select1st
  3. : public unary_function<_Pair, typename _Pair::first_type>
  4. {
  5.     typename _Pair::first_type&
  6.     operator()(_Pair& __x) const
  7.     { return __x.first; }
  8. };

我们看到上述的_Select1st为一个struct，怎么能说它是仿函数呢？因为里面重载了一个()操作符，哈哈～

下面我们来自己实现一个：

  1. template<typename _T1>
  2. struct mySelect1st
  3.         : public unary_function<_T1, typename _T1::first_type>
  4. {
  5.     template<typename _T2>
  6.     typename _T2::first_type&
  7.     operator()(_T2& __x) const
  8.     { return __x.first; }
  9. };
  10. int main() {
  11.      typedef pair<const int,int> value_type;
  12.     _Rb_tree<int, value_type, mySelect1st<value_type>, less<int>> it;
  13.     it._M_insert_unique(make_pair(1,3));
  14.     it._M_insert_unique(make_pair(3,6));
  15.     for(auto each:it)
  16.         cout<<each.first<<" "<<each.second<<endl;
  17. }

key不能改，data可以改

上述源码中：自动为key添加一个const，所以key不能改。

  1. typedef std::pair<const _Key, _Tp>                    value_type;

2.insert

insert里面采用_M_insert_unique

insert的几种方法：

（1） 插入 pair

  1. std::pair<iterator, bool> insert(const value_type& __x)
  2. { return _M_t._M_insert_unique(__x); }

map里面

（2） 在指定位置，插入pair

  1. iterator insert(iterator __position, const value_type& __x)
  2. { return _M_t._M_insert_equal_(__position, __x); }

（3） 从一个范围进行插入

  1. template<typename _InputIterator>
  2. void
  3. insert(_InputIterator __first, _InputIterator __last)
  4. { _M_t._M_insert_equal(__first, __last); }

（4）从list中插入

  1. void
  2. insert(initializer_list<value_type> __l)
  3. { this->insert(__l.begin(), __l.end()); }

针对最后一个insert，里面有个initializer_list，举个例子大家就知道了。

3.initializer_list使用

实际编程实践 

  1. vector<int> v={1,2,3};   // 底层调用vector的构造函数
  2. v={2,5,6};               // 底层调用vector的=操作符
  3. initializer_list<int> ll={4,5,6};
  4. v.insert(v.begin(),ll);  // 底层调用下面insert函数
  5. for(auto x:v) cout<<x<<" ";
  6. cout<<endl;
  7. vector<int> vv(ll);      // 底层调用vector的构造函数
  8. vector<string> city{"Berlin", "New York", "London", "Cairo","Tokyo", "Cologne"};

针对这个vector初始化，大家很熟悉了，为何可以这样初始化呢？我们看一下vector源码：

  1.  vector&
  2. operator=(initializer_list<value_type> __l)
  3. {
  4.     this->assign(__l.begin(), __l.end());
  5.     return *this;
  6. }
  8. iterator
  9. insert(const_iterator __position, initializer_list<value_type> __l)
  10. { return this->insert(__position, __l.begin(), __l.end()); }
  12. vector(initializer_list<value_type> __l,
  13. const allocator_type& __a = allocator_type())
  14. : _Base(__a)
  15. {
  16. _M_range_initialize(__l.begin(), __l.end(),
  17.     random_access_iterator_tag());
  18. }

因为它的构造函数里面，参数有个initializer_list,因此我们可以针对这个对map进行使用。但是map没有类似的构造，它也应用在map构造函数，insert与=处，跟上面是一样的，都是三处，哈哈～

使用initializer_list三处：

  1. // map构造
  2. map(initializer_list<value_type> __l, const allocator_type& __a)
  3. : _M_t(_Compare(), _Pair_alloc_type(__a))
  4. { _M_t._M_insert_unique(__l.begin(), __l.end()); }
  5. // =操作符重载
  6. map&
  7. operator=(initializer_list<value_type> __l)
  8. {
  9.     this->clear();
  10.     this->insert(__l.begin(), __l.end());
  11.     return *this;
  12. }
  13. // insert插入
  14. void
  15. insert(std::initializer_list<value_type> __list)
  16. { insert(__list.begin(), __list.end()); }

实际编程实践

map使用initializer_list(set使用一样)：

  1. // 这里要注意，pair的first参数必[须是const
  2. initializer_list<pair<const strin[g,int>> l = {{"hello", 1}, {"world", 2}};
  3. map<string,int> mm(l);  // map构造函数
  4. map<string, int> m2{{"hello", 1}, {"world", 2}}; // map构造函数
  5. map<string, int> m1={{"hello", 1}, {"world", 2}};   // map构造函数
  6. m1 = {{"h", 1}, {"w", 3}};             // 底层调用map的=操作符
  7. map<string, int> mp;
  8. mp.insert(l);       // insert插入[

上述会引出另一个问题：

  1. map<string, int> m1={{"hello", 1}, {"world", 2}};   // map构造函数
  2. m1 = {{"h", 1}, {"w", 3}};             // 底层调用map的=操作符

这两个为何一个调用的构造，一个调用=操作符呢？

在初始化的时候，定义及赋值的时候就直接调用构造，后面再次赋值，就是先调用拷贝构造(有可能会被编译器优化)，再调用=操作符。

实例分析

下面用一个具体实例来分析一下：

  1. template <typename _Tp>
  2. class Foo
  3. {
  4. public:
  5.     Foo(initializer_list<_Tp> &list)
  6.     {
  7.         cout << "Foo(initializer_list<_Tp> &list)"<< endl;
  8.     }
  10.     Foo(int)
  11.     {
  12.         cout << "Foo(int )"<< endl;
  13.     }
  15.     Foo(const Foo& f)
  16.     {
  17.         cout << "调用了拷贝构造函数"<< endl;
  18.     }
  19.     Foo& operator=(initializer_list<_Tp> __l)
  20.     {
  21.         cout<<"调用了=操作符重载"<<endl;
  22.         return *this;
  23.     }
  25. };

调用：

  1. Foo<int> foo=ll;
  2. foo={1,2};

编译器未被优化的结果：

  1. Foo(initializer_list<_Tp> &list)
  2. 调用了=操作符重载

我们通过禁用编译器优化：g++ -o rb rbtree.cpp -std=c++11 -fno-elide-constructors

  1. Foo(initializer_list<_Tp> &list)
  2. 调用了拷贝构造函数
  3. 调用了=操作符重载

4.multimap

同map一样multimap不允许修改key。但是插入使用的是_M_insert_equal。

  1. template <typename _Key, typename _Tp,
  2. typename _Compare = std::less<_Key>,
  3. typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
  4. class multimap
  5. {
  6. public:                                      
  7.     typedef std::pair<const _Key, _Tp> value_type;   
  8. }

下面使用multimap与rbtree两种方式来联系。

  1. multimap<int, string> c;
  2. c.insert(make_pair(1,"asdqw"));
  3. c.insert(make_pair(1,"qweq"));
  5. for(auto each:c) cout<<each.first<<" "<<each.second<<endl;
  7. typedef pair<const int,string> valueT;
  8. _Rb_tree<int, valueT, _Select1st<valueT>, less<int>> mulm;
  9. mulm._M_insert_equal(make_pair(2,"abc"));
  10. mulm._M_insert_equal(make_pair(2,"cde"));
  11. for(auto each:mulm)
  12. cout<<each.first<<" "<<each.second<<endl;

输出：

  1. 1 asdqw
  2. 1 qweq
  3. 2 abc
  4. 2 cde

5.map与multimap的重要操作符

map与multimap[]操作符，map的[]操作符返回传递给map的第二个参数。

传递给[]一个key，如果查找到，就是value，否则就是默认值0。

  1. mapped_type&
  2. operator[](const key_type& __k)
  3. {
  4.     iterator __i = lower_bound(__k);// 找到__k第一个。
  5.     // __i->first is greater than or equivalent to __k.
  6.     if (__i == end() || key_comp()(__k, (*__i).first))
  7.     #if __cplusplus >= 201103L
  8.     __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
  9.                     std::tuple<const key_type&>(__k),
  10.                     std::tuple<>());
  11.     #else
  12.         __i = insert(__i, value_type(__k, mapped_type()));
  13.     #endif
  14.     return (*__i).second;  // 返回key的value，此value为传递进map的第二个参数。
  15. }

但是multimap没有[]操作符！！！

我们思考一下，因为multimap会根据key，有可能会对应多个value，那如果我们通过[]获取对应key的value，此时到底获取的是哪个value呢，所以在STL源码中没有重载这个操作符！