【决战西二旗】|理解STL Map使用和原理

大白斯基后端技术指南针

明星容器Map

笔者在使用Python进行日常开发时，最常用的数据结构就是list和dict，其中dict在Python底层是基于hash_table来实现的，我们今天就介绍一下对标dict的STL关联容器Map。

在使用map时总让我有种在使用NoSQL的感觉，因为说到底都是key-value，感觉STL中的map可以对标LevelDB之类的普通NoSQL，倒更加的贴切。

结合C++11来说，目前STL支持的map类型包括：map、multimap、unordered_map。虽然都是map，但是在使用和底层实现上会有一些差异，因此深入理解一下才能更好将map用于日常开发工作中。

Map的定义

map的所有元素都是pair，同时具备key和value，其中pair的第一个元素作为key，第二个元素作为value。map不允许相同key出现，并且所有pair根据key来自动排序，其中pair的定义在如下：

template <typename T1, typename 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) { }};

从定义中看到pair使用模板化的struct来实现的，成员变量默认都是public类型。

map的key不能被修改，但是value可以被修改，STL中的map是基于红黑树来实现的，因此可以认为map是基于红黑树封装了一层map的接口，底层的操作都是借助于RB-Tree的特性来实现的，再来进一步看下map的定义，如下(温馨提示:代码主要体现map与RB-Tree在实现上的交互，大致看懂即可):

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>class map {public:  typedef Key key_type;                         //key类型  typedef T data_type;                          //value类型  typedef T mapped_type;  typedef pair<const Key, T> value_type;        //元素类型, const要保证key不被修改  typedef Compare key_compare;                  //用于key比较的函数private:  //内部采用RBTree作为底层容器  typedef rb_tree<key_type, value_type,                  identity<value_type>, key_compare, Alloc> rep_type;  rep_type t; //t为内部RBTree容器public:  //iterator_traits相关  typedef typename rep_type::const_pointer pointer;              typedef typename rep_type::const_pointer const_pointer;  typedef typename rep_type::const_reference reference;          typedef typename rep_type::const_reference const_reference;  typedef typename rep_type::difference_type difference_type;   //迭代器相关  typedef typename rep_type::iterator iterator;            typedef typename rep_type::const_iterator const_iterator;  typedef typename rep_type::const_reverse_iterator reverse_iterator;  typedef typename rep_type::const_reverse_iterator const_reverse_iterator;  typedef typename rep_type::size_type size_type;  //迭代器函数  iterator begin() { 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_reverse_iterator rbegin() const { return t.rbegin(); }  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.size(); }  size_type max_size() const { return t.max_size(); }  //key和value比较函数  key_compare key_comp() const { return t.key_comp(); }  value_compare value_comp() const { return value_compare(t.key_comp()); }  //运算符  T& operator[](const key_type& k)  {    return (*((insert(value_type(k, T()))).first)).second;  }  friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&);  friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&);}

Map的成员函数

map的成员函数(部分常用)可以分为几类：

构造函数、析构函数、赋值构造函数
迭代器返回函数
容量空间函数
取值操作
修正处理(插入、删除、交换、清空)
比较函数
查找函数
构造器函数

Map的常用操作举例

std::map::insert

map的insert操作是非常常见的，并且插入操作不存在迭代器失效问题，其中根据insert的重载类型，可以支持多种插入方式，在C++11中增加了第四种重载函数，本文暂列举C++98的3种重载定义，先看下insert的几种定义：

//single element (1)    pair<iterator,bool> insert (const value_type& val);//with hint (2)    iterator insert (iterator position, const value_type& val);//range (3)    template <class InputIterator>void insert (InputIterator first, InputIterator last);

上述代码给出了3种插入方式分别是单元素pair、指定位置、范围区间，看下实际的例子：

//map::insert (C++98)#include <iostream>#include <map>int main (){  std::map<char,int> mymap;  //first insert function version (single parameter):  //注意返回值 是两个 迭代器和是否成功  mymap.insert ( std::pair<char,int>('a',100) );  mymap.insert ( std::pair<char,int>('z',200) );  std::pair<std::map<char,int>::iterator,bool> ret;  ret = mymap.insert ( std::pair<char,int>('z',500) );  if (ret.second==false) {    std::cout << "element 'z' already existed";    std::cout << " with a value of " << ret.first->second << '\n';  }  // second insert function version (with hint position):  //由于map的key的有序性 插入位置对效率有一定的影响  std::map<char,int>::iterator it = mymap.begin();  mymap.insert (it, std::pair<char,int>('b',300));  // max efficiency inserting  mymap.insert (it, std::pair<char,int>('c',400));  // no max efficiency inserting  // third insert function version (range insertion):  //第三种重载 范围区间  std::map<char,int> anothermap;  anothermap.insert(mymap.begin(),mymap.find('c'));  // showing contents:  //迭代器遍历  std::cout << "mymap contains:\n";  for (it=mymap.begin(); it!=mymap.end(); ++it)    std::cout << it->first << " => " << it->second << '\n';  std::cout << "anothermap contains:\n";  for (it=anothermap.begin(); it!=anothermap.end(); ++it)    std::cout << it->first << " => " << it->second << '\n';  return 0;}

std::map::erase

清除操作也是非常重要的操作，并且存在迭代器失效问题，删除操作同样在C++98中有3个重载函数，定义如下：

void erase (iterator position);size_type erase (const key_type& k);void erase (iterator first, iterator last);

可以看到这三个函数分别支持：迭代器位置删除、指定key删除、迭代器范围删除，看下实际的例子：

// erasing from map#include <iostream>#include <map>int main (){  std::map<char,int> mymap;  std::map<char,int>::iterator it;  // insert some values:  mymap['a']=10;  mymap['b']=20;  mymap['c']=30;  mymap['d']=40;  mymap['e']=50;  mymap['f']=60;  it=mymap.find('b');  mymap.erase (it);                   // erasing by iterator  mymap.erase ('c');                  // erasing by key  it=mymap.find ('e');  mymap.erase ( it, mymap.end() );    // erasing by range  // show content:  for (it=mymap.begin(); it!=mymap.end(); ++it)    std::cout << it->first << " => " << it->second << '\n';  return 0;}

针对迭代器失效问题，本文不做过多说明，后续计划单独写一篇关于STL迭代器失效问题的文章。

std::map::swap

交换操作可以实现两个相同类型的map的交换，即使map元素容量不同，这个操作看着很神奇并且效率很高，可以想下是如何实现的，举个使用栗子：

// swap maps#include <iostream>#include <map>int main (){  std::map<char,int> foo,bar;  foo['x']=100;  foo['y']=200;  bar['a']=11;  bar['b']=22;  bar['c']=33;  foo.swap(bar);  std::cout << "foo contains:\n";  for (std::map<char,int>::iterator it=foo.begin(); it!=foo.end(); ++it)    std::cout << it->first << " => " << it->second << '\n';  std::cout << "bar contains:\n";  for (std::map<char,int>::iterator it=bar.begin(); it!=bar.end(); ++it)    std::cout << it->first << " => " << it->second << '\n';  return 0;}

代码输出：

foo contains:a => 11b => 22c => 33bar contains:x => 100y => 200

Map与红黑树

建造者红黑树

前面说了一些定义，现在介绍今天的重点内容Map与红黑树。

从定义可以看到map的定义中本质上是在内部实现了一棵红黑树，因为红黑树的增删改查的所有操作都可以在有时间保证的前提下完成，然而这些操作也正是map所需要的。

换句话说map应该提供的接口功能，红黑树也都有，从而map的所有操作都是内部转向调用RB-Tree来实现的。

提到红黑树感觉很难很复杂并且离我们日常开发很远，其实不然，红黑树不仅是作为AVL的工程版本，在增加节点颜色、不严格平滑等特性实现了更高效的插入和删除。

更重要的是RB-Tree作为一种基础的数据结构，经常被用于构建其他对外的结构，我们今天说的map以及STL的set底层都是基于红黑树的，所以要把RB-Tree当做是一种基础构造类型的数据结构。

SGI STL并没有直接只用RB-Tree，而是对其进行了模板化处理以及增加一些有益节点，从而来更加高效的为STL中的容器服务，所以STL中使用的可以认为是变种的红黑树。

比如SGI STL针对RB-Tree采用了header技巧，header指向根节点的指针，与根节点互为对方的父节点，并且left和right指向左子树最小和右子树最大，如图所示：

为什么是红黑树

这里引入一个常见的问题：

面试官：stl的map是基于红黑树实现的，那么为什么要基于红黑树？

这个问题也算是高频问题，很多人上来就回答红黑树的各种好处，那确实也没错，但是这样也最多算答上来一半。

其实也是如此，没有对比就没有发言权，总说A好，不和BCD对比一下怎么知道？

map的一些原则

map的场景本质上就是动态查找过程，所谓动态就是其中包含了插入和删除，并且数据量会比较大而且元素的结构也比较随意，并且都是基于内存来实现的，因此我们就需要考虑效率和成本，既要节约内存又要提高调整效率和查找速度。

备选的数据结构

说到查找问题必然有几种备选的数据结构不乏：

线性结构及其变种：数组、链表、跳跃链表
树形结构：BST、AVL、RB-Tree、Hash_Table、B-Tree、Splay-Tree、Treap
当然还有一些其他我可能不知道的，但是热门的基本都在这里了，那么一一来看进行优劣势分析：
数组和链表不用多说，动态高效的插入、删除、查找都不能满足要求。
跳跃链表SkipList在Redis中和LevelDB中都有应用，并且当时是声称要替代RB-Tree，那为什么map不是使用跳跃链表来实现的呢？
BST和AVL是二叉搜索树和平衡二叉树，这两个比较容易排除，BST可能退化成为链表，那么树就相当于很高，时间无法保证，AVL作为严格平衡的二叉搜索树对平衡性要求很高，因此在插入和删除数据时会造成不断地重度调整，影响效率，有点学术派而非工程派，但是AVL是后面很多变种树的基础也很重要，但是确实不适合用在map中。
Hash_Table其实目前已经有基于哈希表的map版本了，相比红黑树查找更快，然而时间的提升也是靠消耗空间完成的，哈希表需要考虑哈希冲突和装载因子的处理，在1994年左右内存很小并且很贵，因此哈希表在当时并没有被应用于实现map，现在内存相对来说已经很大并且不再昂贵，哈希表自然也有用武之地了。
Splay-Tree伸展树也是一种变种，它是一种能够自我平衡的二叉查找树，它能在均摊O(log n)的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特（Daniel Sleator）和罗伯特·塔扬在1985年发明的。
Treap就是Tree+heap，树堆也是一种二叉搜索树，是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(log{n})。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。
B-Tree这里可以认为是B树族包括B树、B+树、B*树，我们都知道B树在MySQL索引中应用广泛，构建了更矮更胖的N叉树，这种结构结点可以存储更多的值，有数据块的概念，因此应对磁盘存储很有利，事实上即使内存中使用B树也可以提高CacheHit的成功率，从而提高效率，网上有的文章提到STL之父说如果再有机会他可能会使用B树来实现一种map，也就是借助于局部性原理来提高速度。

关于跳跃链表的一些猜测

在网上也并没有这种为什么不用跳表的对比，笔者试着想了一下：

对于这个对比一定要结合map的发明年代背景来说，就好像我们现在问10年前的人们为什么不用微信、QQ、淘宝一样，因为那时候压根没有或者刚出来暂时没有推广等诸多原因。

SGI STL是大约1994年左右开发的，然而跳跃链表是1990年左右由William Pugh发明的，也就是可以认为二者是同时期的产物，然而Redis是2005年之后的产物，再看看红黑树是1978年左右发明出现的，所以对发明STL的那帮大牛，最开始考虑跳跃链表的可能性很小。

在国外的网站上有求知者试着用跳表实现map但是性能和红黑树有一定的差距，另外跳表本身是概率平衡的，节点大小相比于红黑树更大，但是我觉得这并不是致命的问题，或许过些年STL就会出现基于跳表的实现版本，这个很难说，所以不能一棒子打死说必须是红黑树。

百舸争流

从上面我所知道的数据结构来看，选择红黑树有很多历史原因和性能考虑、时代在进步，并不一定后续就不会出现基于Treap树堆和B树的map版本，或许现在就有公司或者大佬自己使用跳表、Treap、B树来实现map。

所以我们不能教条地记忆stl使用红黑树的原因，至于真正的原因只有创造者知道，不要把推测当做结论，没有最好只有更好。

参考资料

https://zcheng.ren/sourcecodeanalysis/stlsetandmap/
http://www.cplusplus.com/reference/map/map/
https://www.kancloud.cn/digest/stl-sources/177279
http://cn.voidcc.com/question/p-bfsmtkfi-et.html
http://luodw.cc/2015/11/19/STL-map/

【决战西二旗】|理解STL Map使用和原理