STL关联容器

发表于2022-01-08更新于2023-04-25字数统计3.3k阅读时长14分阅读次数

摘要

标准的STL关联式容器分为set(集合) 和map(映射表) 两大类，以及这两大类的衍生体multiset和multimap，这些容器底层都是基于红黑树(red-black tree)实现的。 此外C++11标准也提出了基于hashtable实现的无序容器，分别为 unordered_set和unordered_map。所以这里会先简单的介绍一下红黑树，然后介绍上述几种容器的特性。

红黑树介绍

由于std::map和std::set都是基于红黑树实现的，这里有必要介绍一下典型的搜索树结构以及红黑树的大致工作原理。

二叉搜索树

首先，二叉树是一种特殊的树，每个节点最多只允许两个子节点，这两个子节点称为左子节点和右子节点。递归的来说，一棵二叉树由根节点和左子树以及右子树组成。

二叉搜索树(Binary Serach)是一种特殊的二叉树，它可以提供平均对数时间复杂度的元素插入和访问。二叉搜索树的节点放置规则是：任何节点的键值一定大于其左子树中的每一个节点键值，并小于其右子树中的每一个节点的键值。也就是说从根节点一直往左走，就能找到最小元素，从根节点一直往右走，就能找到最大元素。

例如，对于下图所示的一棵二叉搜索树，为了找到元素5，只需要进行4次比较，也就是说最多搜索到树的最底层就可以找到结果：
二叉搜索树

关于二叉搜索树的详细介绍可以参考算法导论3th第12章的内容。一般的二叉搜索树有个最大的问题是：经过若干次的插入和删除操作之后，树可能会失去平衡，即左子树和右子树的高度差很大。这样就导致树的搜索时间复杂度增大，最坏的情况是二叉树退化成链表，这样搜索的复杂度变为O(n)。

为了解决这个问题，有若干种平衡二叉树出现，较为常见的有AVL-tree,RB-tree等，所谓平衡二叉树，指左子树和右子树的高度差接近(一般而言，很难追求左右子树的绝对平衡，这样代价很高。因此实际的平衡树都是指近似平衡树，能够维持搜索的时间复杂度是对数复杂度。)

AVL-tree要求任何节点的左右子树高度相差最多为1。这一点是如何保证的呢？或者说，当一棵已经平衡的树执行插入或删除操作之后导致树不满足平衡要求之后，怎么做呢？一般而言调整树的平衡是通过节点旋转来实现的(单旋转和双旋转)。这里不展开说。总之，能够在树失衡之后，通过节点调整操作使得树恢复平衡。

实际过程发现，AVL-tree对平衡度要求还是过于苛刻，这导致了元素插入和删除时会有频繁的节点调整操作，这很耗时。于是有一种更为常用的平衡树结构：红黑树(RB-tree)。红黑树平衡度并不如AVL-tree，但它能够确保没有一个子树会比另一个子树长度长两倍。也就是说红黑树是一种平衡性比AVL-tree更弱的搜索树，这点牺牲带来的是插入和删除元素速度的提升，也就是说红黑树的树形调整频率更低。红黑树能够保证最坏情况下基本动态集合的操作时间复杂度为O(logn)。

红黑树(RB-tree)

首先，红黑树是一棵特殊的二叉搜索树，它在每个结点上增加了一个存储位来表示树的颜色，可以是红或黑。具有以下基本约束：

  1. 节点不是红色就是黑色。
  2. 根节点是黑色。
  3. 如果节点是红的，那么它的两个儿子节点都是黑色。
  4. 任一节点到NULL(树尾端)的任何路径，所含的黑节点数相同。

当插入或删除破坏了上述性质时，会通过调整颜色和旋转树形来重新满足条件。
红黑树
至于如何调整，分为很多种情况，实际实现起来也比较复杂。这里给出几个详细介绍红黑树这种数据结构的地方：
30张图带你彻底理解红黑树
硬核图解面试最怕的红黑树【建议反复摩擦】
算法导论第三版 P174

std::set

概述

std::set是以特定顺序存储元素的容器，且容器中的元素不允许重复。也就是说set中的元素是有序且独一无二的。

set中的元素不像map的元素同时拥有实值(value)和键值(key)，set只有键值，或者说其键值就是实值。实际上set的底层的数据结构就是上面所说的红黑树，因此元素之间是有序的。也正是这点导致元素的值不能够原地修改，也就是说不能够通过元素的迭代器来修改元素的值，因为原地修改元素的值会影响破坏二叉搜索树。实际上，set的迭代器set<T>::iterator被定义为底层rb-tree的 const_iterator,且是一个bidirectional iterator，不允许写操作。 常用的修改set的操作是删除(erase)和插入(insert)。

由于底层实现是一颗二叉搜索树，set的元素插入、删除、搜索的时间复杂度都是O(logn)。

set的声明如下：

1
2
3
4
template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

类似与priority_queue，模板参数Compare是一个仿函数或函数指针，它接受两个类型为T的参数a,b，返回一个bool类型的值，当希望a排在b之前时返回true。默认是less<T>，也就是a < b时排在前面，升序排列。

常用接口

  • 构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
//empty (1)   
explicit set (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
explicit set (const allocator_type& alloc);
//range (2)   
template <class InputIterator>
  set (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& = allocator_type());
//initializer list (5)    
set (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());
  • 大小
1
2
3
bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
  • 插入/删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pair<iterator,bool> insert (const value_type& val);    //插入元素，返回值pair.first为插入元素的迭代器(插入失败则是重复元素的迭代器)，pair.second为是否插入成功，成功为true
iterator insert (const_iterator position, const value_type& val); //带有提示的插入操作，注意参数position只起插入位置的提示作用，具体插入位置根据排序来，当position指向将要被插入值的前一个时，能获得最大效率
template <class InputIterator>
void insert (InputIterator first, InputIterator last);  //范围插入
void insert (initializer_list<value_type> il);  //initializ list插入

iterator  erase (const_iterator position);  //返回的迭代器指向删除元素的后一个元素，或者set::end()
size_type erase (const value_type& val);  //返回移除的元素个数
iterator  erase (const_iterator first, const_iterator last);

void clear() noexcept;

template <class... Args>
  pair<iterator,bool> emplace (Args&&... args);
template <class... Args>
  iterator emplace_hint (const_iterator position, Args&&... args);  //带有位置提示的emplace
  • 迭代器/元素访问
1
2
3
4
5
6
7
iterator begin() noexcept;
iterator end() noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend () const noexcept;

iterator find (const value_type& val);  //查找元素，返回元素的迭代器，没有则返回end迭代器
size_type count (const value_type& val) const;  //元素计数，由于set特性，所以返回值1或者0

std::unordered_set

概述

std::unordered_set是c++11中的新容器，它和set类似保存独一无二的元素集合，但是保存的元素之间是无序的。同样的，unordered_set中的元素也不能原地修改，其提供的迭代器也是const_iterator，它的使用方式和set基本完全一致。且一般而言插入、删除和查找速度会比set快。

实际上，unordered_set底层实现的数据结构是散列表(hashtable)，也叫哈希表。哈希表将元素通过hash function进行映射之后，存放在相应的位置，这样做的好处就是，当需要查找一个元素时，只需进行一次hash function的运算便能够得到存储的位置。查找元素的时间复杂度是常数O(1)。

hashtable的一个很大的问题是，使用的hash function时可能会导致不同的元素经过运算之后得到的存储位置相同，也即发生了哈希碰撞。哈希碰撞几乎是不能避免的，但是有若干中方法能够解决发生碰撞后的问题。常用的方法有：线性探测、二次探测、开链等。

线性探测就是当发生哈希碰撞之后，将元素存放在下一个空的位置，查找的时候也一样，当计算出来的位置没有需要的元素之后，线性的往后查找，线性探测最大问题是主集团问题，也就是插入过程导致在某个局部频繁的碰撞。二次探测用于解决主集团问题，它的基本思路是：当发生碰撞之后，将元素依次尝试存放在H+i^2的位置。

开链的方式是另一种常用的解决哈希碰撞的方法，在侯捷老师的《STL源码解析》中的标准库版本就是使用这种方法实现的哈希表。它在每个表格元素中维护一个链表，如下图，当发生碰撞之后，将其放在链表的头部使链表的长度加1即可。

hashtable

常用接口

unordered_set常用接口和set几乎一致，这里不多介绍。

std::map

概述

map和set一样是一种有序容器，只是其每个元素都是一个std::pair，pair的第一个元素被视为键值(key)，第二个元素被视为实值(value)，以key之间的大小进行排序。同样的map不允许两个元素拥有相同的key。

map底层也是实现了一棵红黑树，只是节点之间比较大小时使用的是pair中的key。其声明如下：

1
2
3
4
5
template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

常用接口

  • 构造函数
1
2
3
4
5
6
7
8
9
10
11
12
13
//empty (1)   
explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
explicit map (const allocator_type& alloc);
//range (2)   
template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& = allocator_type());
//initializer list (5)    
map (initializer_list<value_type> il,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());
  • 大小
1
2
3
bool empty() const noexcept;
size_type size() const noexcept;
size_type max_size() const noexcept;
  • 插入/删除操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
pair<iterator,bool> insert (const value_type& val);
iterator insert (const_iterator position, const value_type& val);  //带提示位置的插入，只是提示，最终的插入位置根据红黑树的节点排序来决定，当提示位置的元素在插入元素的前一个时有很高的效率
template <class InputIterator>
  void insert (InputIterator first, InputIterator last);
void insert (initializer_list<value_type> il);

iterator  erase (const_iterator position);
size_type erase (const key_type& k);  //返回删除的元素个数，这里是0或1
iterator  erase (const_iterator first, const_iterator last);

void clear() noexcept;

template <class... Args>
  pair<iterator,bool> emplace (Args&&... args);
template <class... Args>
  iterator emplace_hint (const_iterator position, Args&&... args);  //带提示的插入
  • 迭代器/元素访问
1
2
3
4
5
6
7
8
9
10
iterator begin() noexcept;
iterator end() noexcept;
const_iterator cbegin() const noexcept;
const_iterator cend () const noexcept;

mapped_type& operator[] (const key_type& k);  //当不和容器中任何值匹配的时候，会插入键值为k的一个元素，并返回其对应value的引用
mapped_type& at (const key_type& k);

iterator find (const key_type& k);  //未找到元素返回尾迭代器
size_type count (const key_type& k) const;  //key为k的元素个数

std::unordered_map

底层实现上和unordered_set一样，为hashtable，内部存储的元素同样是pair，这一点和map一致，使用上和map也几乎一致。一般而言无序容器在插入元素、删除元素和查找元素上比有序容器快。

总结

本篇文章首先将简单介绍了二叉搜索树以及一种较为特殊的二叉搜索树：红黑树，这种数据结构作为关联容器map和set的底层数据结构，具有插入和查找元素的操作为对数时间复杂度的优点。之后介绍了有序和无序关联容器的底层数据结构和常用的接口，其中有序容器使用红黑树作为底层数据结构，无序容器则使用哈希表作为底层数据结构。至此，就将STL中的常见容器介绍完了，包括序列容器和关联容器。

参考资料

  1. 《STL源码剖析》侯捷
  2. http://www.cplusplus.com/reference/
  3. 《算法导论 3th》
  4. 30张图带你彻底理解红黑树
  5. 硬核图解面试最怕的红黑树【建议反复摩擦】