【STL】从源码看map

不念不忘少年蓝@ 2022-07-15 11:53 225阅读 0赞

**map**

与set相同，map同样是以红黑树RB\_Tree为底层机制的关联式容器。map的每一个元素都拥有两个值，一个键值（key）和一个实值（value）。它的内部实现是用一个pair来保存这个两个值。所以，map的每一个元素又是一个pair。下面是STL源码中stl\_pair.h对pair的定义。

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) {}
    #ifdef __STL_MEMBER_TEMPLATES
      template <class U1, class U2>
      pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
    #endif
    };

因为map底层是一棵红黑树（RB\_Tree），红黑树的又是一种平衡二叉搜索树，自动排序效果很好。因此map内所有的元素都会根据元素的键值（key）自动排序。这一点也限制了我们不能修改map内元素的键值（key），键值（key）关系到map元素的排列规则，任意改变map的元素键值将会严重破坏map组织结构。那么STL源码是如何限制我们呢？

打开stl\_map.h，你会看到这么一句话：

typedef pair<const Key, T> value_type;

它将pair重命名成value\_type，同时将pair的key声明成了const类型，限制我们不能对它做出修改。

map的底层是红黑树，map的各种操作接口红黑树也都提供了，所以几乎所有的map操作行为，都是调用红黑树RB\_Tree的操作行为。下面我将从源码角度讲，map是如何调用红黑树的。

**类型：“是你的又怎么样，我改个名字就是我的了”**

请允许我用“不要脸”和“暴力”这两个名字来形容map在这里的做法，尽管它的整个实现都很“不要脸”。它先把红黑树重命名。再用重命名的红黑树把红黑树内的参数类型再次重命名。好像这样就变成自己的了，但的确是这样。

这里，我们可以明显感觉到STL库的 代码复用性是多么的高，它的编写者是多么的厉害。

源码：

private:
      //将红黑树重命名
      typedef rb_tree<key_type, value_type,
                      select1st<value_type>, key_compare, Alloc> rep_type;
      rep_type t;  // red-black tree representing 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;
      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;

当然，它也可以有一些自己的东西。

源码：

typedef Key key_type;
      typedef T data_type;
      typedef T mapped_type;
      typedef pair<const Key, T> value_type;
      typedef Compare key_compare;

**对象成员**

map的源码里面对私有成员（private）的定义有以下四行：

private:
      typedef rb_tree<key_type, value_type,select1st<value_type>, key_compare, Alloc> rep_type;
      rep_type t;  // red-black tree representing map

我们可以看到，它直接将一个红黑树类型rb\_tree（它的模板参数不再讲，想了解的可以去看看rb\_tree的源码）重命名成rep\_ type，并且利用rep\_ type构建了一个红黑树对象t。如果你接着往下看，你会发现，map的所有方法中都有t的身影。

**方法**

**基本方法**

这里我将构造，赋值运算符重载定义为基本方法。（纯属本人为了方便）

**构造**

打开c++Reference，会看到map的构造有三种实现。前两种是构造函数，第三种是拷贝构造函数。但是它远远没有表面上这么简单。

**1.（构造）**

explicit map(const Compare& comp = Compare(),const Allocator& = Allocator());

关键字explicit的作用是 防止隐式转换或者说防止构造函数被隐式调用。参数compare的作用是传一个比较类型，这么说可能不严谨，但是好理解些。开头说过，因为map底层机制是红黑树，所以它有自动排序的功能。既然要排序，那就肯定有升序降序之分。compare的作用就是决定升序还是降序。 它内部有实现了一个operator(),功能是大小比较。在默认情况下，STL源码库内的Compare实现的是升序。如果我们自己写一个compare给它传参，它会按照我们自己写的compare进行排序。

回头来说，为了显示它和红黑树是一对好基友，它在内部实现的时候直接调用了红黑树的构造函数。从源码我们可以看出，它的缺省构造和非缺省构造都是调用相应的红黑树的构造函数。

源码：

map() : t(Compare()) {}
      explicit map(const Compare& comp) : t(comp) {}//

**2.（构造）**

template <class InputIterator>
    map(InputIterator first, InputIterator last,const Compare& comp = Compare(), const Allocator& = Allocator());

这个构造函数有一个模板参数，这个参数的类型一般是迭代器。通过传入first，last两个迭代器。将左闭右开区间\[first，last)的内容插入新构造的map中。Allocator是一个空间配置器。

基友情深似海，它同样以调用红黑树构造函数的方式来实现它自己构造函数的功能。但，这次没那么简单，使用模板参数必定意味着它有多种的实现。在STL源码中，它通过改变参数，实现函数重载，进而来实现多种参数类型的传参。光说可能有点迷糊，看一下源码你就悟到了。

源码：

#ifdef __STL_MEMBER_TEMPLATES
      //原版
      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); }
    #else
      //value_type（也就是pair）的指针类型
      map(const value_type* first, const value_type* last)
        : t(Compare()) { t.insert_unique(first, last); }
      map(const value_type* first, const value_type* last, const Compare& comp)
        : t(comp) { t.insert_unique(first, last); }
      //const类型迭代器
      map(const_iterator first, const_iterator last)
        : t(Compare()) { t.insert_unique(first, last); }
      map(const_iterator first, const_iterator last, const Compare& comp)
        : t(comp) { t.insert_unique(first, last); }
    #endif /* __STL_MEMBER_TEMPLATES */

**3.（拷贝构造）**

map(const map<Key, T, Compare, Allocator>& x);

拷贝构造就不需要多说了，同样是调用红黑树的拷贝构造。直接上源码。

源码：

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; 
    }

**功能方法**

从上面我们就看到了，map的无赖。所以它准备接着无赖下去。它大部分功能的实现都是调用的红黑树的方法。但是也有几个需要注意的我会放在下面 *特殊的功能方法*一栏去讲，此栏只贴出源码。不分析。（因为没什么可分析的）

（ps：以下标注C++的是我们可以调用的接口，标注STL的是源码的实现）

**正向迭代器**

C++:

iterator begin();
      const_iterator begin() const;
      iterator end();
      const_iterator end() const;

STL:

iterator begin() { return t.begin(); }
      const_iterator begin() const { return t.begin(); }
      iterator end() { return t.end(); }
      const_iterator end() const { return t.end(); }

**反向迭代器**

C++:

reverse_iterator rbegin();
      const_reverse_iterator rbegin() const;
      reverse_iterator rend();
      const_reverse_iterator rend() const;

STL:

reverse_iterator rbegin() { return t.rbegin(); }
      const_reverse_iterator rbegin() const { return t.rbegin(); }
      reverse_iterator rend() { return t.rend(); }
      const_reverse_iterator rend() const { return t.rend(); }

**判空、求size、求max\_size**

C++:

bool empty() const;
    size_type size() const;
    size_type max_size() const;

STL:

bool empty() const { return t.empty(); }
     size_type size() const { return t.size(); }
     size_type max_size() const { return t.max_size(); }

**erase、clear、swap**

C++:

void erase(iterator position);
      size_type erase(const key_type& x);
      void erase(iterator first, iterator last);
      void clear();
      void swap(map<Key, T, Compare, Allocator>& mp);

STL:

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(); }
      template <class Key, class T, class Compare, class Alloc>
      inline void swap(map<Key, T, Compare, Alloc>& x,
             map<Key, T, Compare, Alloc>& y) {
             x.swap(y);
      }

**key\_comp、value\_comp**

C++:

key_compare key_comp() const;
    value_compare value_comp() const;
    STL:
    key_compare key_comp() const { return t.key_comp(); }
    value_compare value_comp() const { return value_compare(t.key_comp()); }

我在上面说过，compare是一个比较类型。这两个函数方法就是返回给我们一个这个类型的匿名对象。

注意这里的value\_comp，map的key是关键码，value是实值。进行比较的时候只能比较key。所以我们会看到它将一个key\_comp墙专程value\_compare类型，本质上还是key\_compare，比较的是key。下面是value\_compare的源码定义：

STL：

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);// first为key
        }
      };

**find、count**

C++:

iterator find(const key_type& x);
      const_iterator find(const key_type& x) const;
      size_type count(const key_type& x) const;

STL:

iterator find(const key_type& x) { 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); }

find的作用是查找元素是否存在，若存在，返回指向元素位置的迭代器。若不存在，返回end();

count一样可以查找元素是否存在，若存在，返回元素的个数。若不存在，返回0；（主要在multimap中使用）

**lower\_bound、upper\_bound**

C++:

iterator lower_bound(const key_type& x);
      const_iterator lower_bound(const key_type& x) const;
    
      iterator upper_bound(const key_type& x);
      const_iterator upper_bound(const key_type& x) const;

STL:

iterator lower_bound(const key_type& x) {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) {return t.upper_bound(x); }
      const_iterator upper_bound(const key_type& x) const {
        return t.upper_bound(x);
      }

我们可以看到，这两个参数的返回值都是一个key值。

lower\_bound的作用是查找并返回 大于等于这个key值的第一个元素的迭代器。

upper\_bound的作用是查找并返回 大于这个key值的第一个元素的迭代器。

**equal\_range**

C++:

pair<iterator, iterator> equal_range(const key_type& x);
      pair<const_iterator, const_iterator> equal_range(const key_type& x) const;

STL:

pair<iterator,iterator> equal_range(const key_type& x) {
        return t.equal_range(x);
      }
      pair<const_iterator,const_iterator> equal_range(const key_type& x) const {
        return t.equal_range(x);
      }

只要你搞明白了lower\_bound与upper\_bound，搞懂equal\_range就很容易了。因为这个就是他们两个的结合体。

我们可以看到，equal\_bound的参数同样是个key值，返回值是一个pair。pair里面是两个迭代器。第一个就是 大于等于这个key值的第一个元素的迭代器。第二个迭代器就是 大于这个key值的第一个元素的迭代器。

**特殊的功能方法**

这里的特殊是指的它与set不同，因为set与map都是以红黑树为基础实现，所以我们经常拿它两做对比。

**insert**

我们看到的insert有三种接口，仔细看这个三个insert的实现，你会发现原来他们都一样，全部调用红黑树的insert\_unique。这也是map与multimap不同的地方。STL的红黑树实现了两种insert，一种是insert\_uniq

C++：

pair<iterator, bool> insert(const value_type& x);

返回值为一个pair。pair的first是一个迭代器，second是一个bool值。当插入成功时，返回值pair的迭代器指向插入元素的位置，bool值为true。插入失败时（说明该元素已经存在），迭代器指向已存在元素的位置，bool值为false。

STL：

pair<iterator,bool> insert(c
    onst value_type& x) { return t.insert_unique(x); }

C++：

iterator insert(iterator position, const value_type& x);

返回值为一个迭代器。当插入成功时，迭代器指向新插入元素。当插入失败时，迭代器指向已存在元素位置。

STL:

iterator insert(iterator position, const value_type& x) {
        return t.insert_unique(position, x);
      }

C++:

template <class InputIterator>
      void insert(InputIterator first, InputIterator last);

将区间\[first,last)的值插入map中。与参数类型相同的构造函数一样。因为使用了模板，所以它STL源码有多种实现。以便支持多种类型的参数。

STL:

#ifdef __STL_MEMBER_TEMPLATES
      template <class InputIterator>
      void insert(InputIterator first, InputIterator last) {
        t.insert_unique(first, last);
      }
    #else
      void insert(const value_type* first, const value_type* last) {
        t.insert_unique(first, last);
      }
      void insert(const_iterator first, const_iterator last) {
        t.insert_unique(first, last);
      }
    #endif /* __STL_MEMBER_TEMPLATES */

**operator\[\]**

它的operator\[\]是最特殊的一个。因为它有多中功能。

C++：

T& operator[] (const key_type& x);

STL:

T& operator[](const key_type& k) {
        return (*((insert(value_type(k, T()))).first)).second;
      }

1.读功能。它的参数是一个key值，返回值是一个T的引用。T就是实值（value）的类型。我们利用它的返回值可以读到key值为x的元素的value。

2.写功能。写入一个新元素

先搞清楚下面几点。

①巧妙的点就在于它的源码实现，它在里面调用了一个insert。它将insert的返回值得first解引用，并返回解引用后的到值得second。

②从上面我们知道insert的返回值是一个pair。pair的first是一个迭代器。当插入成功时，迭代器指向新插入元素。当插入失败时，迭代器指向已存在元素位置。

③文章开头我们就知道，map的元素是pair类型。pair的second就是value。