带你深入理解STL之Set和Map_stl set 和map 都是基于什么实现的

在上一篇博客 带你深入理解STL之RBTree中，讲到了STL中关于红黑树的实现，理解起来比较复杂，正所谓前人种树，后人乘凉，RBTree把树都种好了，接下来就该set和map这类关联式容器来“乘凉”了。

STL的set和map都是基于红黑树实现的，和stack和queue都是基于deque一样，它们仅仅是调用了RBTree提供的接口函数，然后进行外层封装即可。本篇博客理解起来比较轻松，set和map的源代码也不多，大家可以慢慢“品味”。另外，还会介绍multiset和multimap这两个容器，并给出它们的区别和应用等。还等什么呢？走吧，带你理解理解set和map吧！

set

set是一种关联式容器，其特性如下：

• set以RBTree作为底层容器
• 所得元素的只有key没有value，value就是key
• 不允许出现键值重复
• 所有的元素都会被自动排序
• 不能通过迭代器来改变set的值，因为set的值就是键

针对这五点来说，前四点都不用再多作说明，第五点需要做一下说明。如果set中允许修改键值的话，那么首先需要删除该键，然后调节平衡，在插入修改后的键值，再调节平衡，如此一来，严重破坏了set的结构，导致iterator失效，不知道应该指向之前的位置，还是指向改变后的位置。所以STL中将set的迭代器设置成const，不允许修改迭代器的值。

set的数据结构

// 比较器默认采用less，内部按照升序排列，配置器默认采用alloc
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set
{
public:
  //  在set中key就是value, value同时也是key
  typedef Key key_type;
  typedef Key value_type;

  // 用于比较的函数
  typedef Compare key_compare;
  typedef Compare value_compare;

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<I>支持
  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; 
  // 设置成const迭代器，set的键值不允许修改
  typedef typename rep_type::const_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() 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(); }

  // 返回用于key比较的函数
  key_compare key_comp() const { return t.key_comp(); }
  // 由于set的性质, value比较和key使用同一个比较函数
  value_compare value_comp() const { return t.key_comp(); }

  // 声明了两个友元函数，重载了==和<操作符
  friend bool operator== __STL_NULL_TMPL_ARGS (const set&, const set&);
  friend bool operator< __STL_NULL_TMPL_ARGS (const set&, const set&);
  // ...
}
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

set的构造函数

set提供了如下几个构造函数用于初始化一个set

// 注：下面相关函数都在set类中定义，为了介绍方便才抽出来单独讲解
// 空构造函数，初始化一个空的set
set() : t(Compare()) {}
// 支持自定义比较器，如set<int,greater<int> > myset的初始化
explicit set(const Compare&am
1
2
3
4
5