本文共 15222 字，大约阅读时间需要 50 分钟。

分类

RB-tree 介绍与应⽤

，RB Tree 全称是 Red-Black Tree，⼜称为“红⿊树”，它是一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红 (Red) 或⿊ (Black)。

特性：

• 每个节点是红色或者黑色
• 根节点是黑色
• 每个叶子节点（null）是黑色 [注意：这⾥叶⼦节点，是指为空(NIL或NULL)的叶⼦节点！]
• 如果一个节点是红色的，那么它的子节点一定是黑色的
• 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点。这里可以确保没有⼀条路径会⽐其他路径⻓出俩倍。因⽽，红⿊树是相对是接近衡的⼆叉树

红黑树保证了最坏情况下在O(logn)时间负责度内完成查找、插入以及删除操作，效率非常高

因此红黑树可以用于很多场景，比如：

RB-tree 的基本操作

红⿊树的基本操作包括 添加、删除。

在对红黑树进行添加或者删除之后，都会用到旋转方法。原因在于添加或者删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的五条性质，也就是说不再是一颗红黑树了，而是一颗普通的树。

通过旋转，可以使得这棵树重新成为红黑树。简单来说，旋转的目的是让树保持红黑树的特性

在红⿊树⾥的旋转包括两种：左旋和右旋。

• 左旋： 对节点 X 进⾏左旋，也就说让节点 X 成为左节点。
• 右旋： 对节点 X 进⾏右旋，也就说让节点 X 成为右节点。
  
  说完了旋转，我们再来看⼀下它的插⼊，有两种插⼊⽅式：

//不允许键值᯿复插⼊pair
   
     insert_unique(const value_type& x);//允许键值᯿复插⼊iterator insert_equal(const value_type& x);
   

RB-tree里面分两种插入方式，一种是允许键值重复插入，一种不允许。可以简单的理解，如果调用insert_unique插入重复的元素，在RB-tree里面是无效的。

其实在 RB-tree 源码⾥⾯，上⾯两个函数⾛到最底层，调⽤的是同⼀个 __insert() 函数

知道了数据的操作方式，我们再来看RB-tree的构造方式：内部调用rb_tree_node_allocator，每次恰好配置一个节点，会调用simple_alloc空间配置器来配置节点。并分别调用四个节点函数来初始化和构造化（get_node(), put_node(), create_node(), clone_node(), destroy_node();）

RB-tree的构造方式也有两种：一种是以现有的RB-tree复制一个新的RB-tree，另一种是产生一颗空的树。

哈希表（hashtable）介绍和应⽤

我们知道数组的特点是寻址容易，插入和删除困难，而链表的特点是寻址困难，插入和删除容易，而哈希表就综合了这两者的特性，寻址容易，插入删除也容易。

哈希表，也叫做散列表，是一种常用的数据结构，这种结构在插入、删除、查找等操作上也具有“常数平均时间"的表现。也可以看作是一种字典结构。

在讲具体的 hashtable 源码之前，我们先来认识两个概念：

• 散列函数：使⽤某种映射函数，将⼤数映射为⼩数。负责将某⼀个元素映射为⼀个”⼤⼩可接受内的索引“，这样的函数称为 hash function（散列函数）。
• 使⽤散列函数可能会带来问题：可能会有不同的元素被映射到相同的位置，这⽆法避免，因为元素个数有可能⼤于分配的 array 容量，这就是所谓的碰撞问题，解决碰撞问题⼀般有：线性探测、⼆次探测、开链等。

STL是用开链法来处理的。拉链法，可以理解为“链表的数组”，其思路是：如果多个关键字映射到了哈希表的同一个位置处，则将这些关键字记录在同一个线性链表中，如果有重复的，就顺序拉在这条链表的后面

hash table 的定义：

//模板参数定义/*Value： 节点的实值类型Key： 节点的键值类型HashFcn： hash function的类型ExtractKey：从节点中取出键值的⽅法（函数或仿函数）EqualKey：判断键值是否相同的⽅法（函数或仿函数）Alloc：空间配置器*///hash table的线性表是⽤ vector 容器维护template 
   
    class hashtable {
   public:	 typedef _Key key_type;	 typedef _Val value_type;	 typedef _HashFcn hasher;	 typedef _EqualKey key_equal;	 typedef size_t size_type;	 typedef ptrdiff_t difference_type;	 typedef value_type* pointer;	 typedef const value_type* const_pointer;	 typedef value_type& reference;	 typedef const value_type& const_reference;	 hasher hash_funct() const {
    return _M_hash; }	 key_equal key_eq() const {
    return _M_equals; }private:	 typedef _Hashtable_node<_Val> _Node;
   

这里需要注意的是，hashtable的迭代器是正向迭代器，而且必须维持这个buckets vector的关系，并记录目前所指的节点。其前进操作是目前所指的节点，前进一个位置。

//以下是hash table的成员变ᰁprivate:	 hasher _M_hash;	 key_equal _M_equals;	 _ExtractKey _M_get_key;	 vector<_Node*,_Alloc> _M_buckets;//⽤vector维护buckets	 size_type _M_num_elements;//hashtable中list节点个数public:	 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> 	 iterator;	 typedef _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey, _Alloc> const_iterator;public:	 //构造函数	 hashtable(size_type __n,		 const _HashFcn& __hf,		 const _EqualKey& __eql,		 const _ExtractKey& __ext,		 const allocator_type& __a = allocator_type())   : __HASH_ALLOC_INIT(__a)	 _M_hash(__hf),	 _M_equals(__eql),	 _M_get_key(__ext),	 _M_buckets(__a),	 _M_num_elements(0) {
   	 _M_initialize_buckets(__n);//预留空间,并将其初始化为空0	 //预留空间⼤⼩为⼤于n的最⼩素数 }

提供两种插⼊元素的⽅法：insert_equal允许᯿复插⼊；insert_unique不允许᯿复插⼊。

//插⼊元素节点,不允许存在᯿复元素 pair
   
     insert_unique(const value_type& __obj) {
   	 //判断容ᰁ是否够⽤, 否则就᯿新配置	 resize(_M_num_elements + 1);	 //插⼊元素,不允许存在᯿复元素	 return insert_unique_noresize(__obj); } //插⼊元素节点,允许存在᯿复元素 iterator insert_equal(const value_type& __obj) {
   	//判断容ᰁ是否够⽤, 否则就᯿新配置	 resize(_M_num_elements + 1);	 //插⼊元素,允许存在᯿复元素	 return insert_equal_noresize(__obj); }
   

hashtable 的基本操作

关联容器set、multiset、map和multimap的底层机制都是基于RB-tree红黑树，虽然能够实现在插入、删除和搜索操作能够达到对数平均时间，但是要求输入数据具有足够的随机性。

而hashtable不需要输入数据具有随机性，在插入、删除和搜索操作都能达到常数平均时间。

SGI中实现hash table的方式，是在每个buckets表格元素中维护一个链表，然后在链表上执行元素的插入、查询、删除等操作，该表格中的每个元素被成为桶。

`

虽然开链法并不要求表格⼤⼩为质数，但 SGI STL 仍然已质数来设计表格⼤⼩，并且将 28 个质数计算好，以备随时访问。

// Note: assumes long is at least 32 bits.// 注意：假设long⾄少为32-bits, 可以根据⾃⼰需要修改//定义28个素数⽤作hashtable的⼤⼩enum {
    __stl_num_primes = 28 };static const unsigned long __stl_prime_list[__stl_num_primes] = {
   	 53ul, 97ul, 193ul, 389ul, 769ul,	 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,	 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,	  1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,	 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,	 1610612741ul, 3221225473ul, 4294967291ul};//返回⼤于n的最⼩素数inline unsigned long __stl_next_prime(unsigned long __n) {
   	 const unsigned long* __first = __stl_prime_list;	 const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes;	 const unsigned long* pos = lower_bound(__first, __last, __n);

hashtable的节点配置和释放分别由 new_node 和 delete_node 来完成，并且插⼊操作和表格᯿整分别由

insert_unique 和 insert_equal ,resize 三个函数来完成

C++ STL标准库中，不仅是unordered_xxx容器，所有无序容器的底层都采用hash表存储结构。更准确的说，是采用拉链法解决数据存储发生冲突的哈希表，整个存储结构如下图：

其中，$Pi$表示存储的各个键值对。

最左边的绿⾊称之为 bucket 桶，可以看到，当使用无序容器存储键值对时，会先申请一整块连续的存储空间，但是此空间并不用来直接存储键值对，而是存储各个链表的头指针，各键值对真正的存储位置时各个链表的节点。

在C++ STL标准库中，将图1中的各个链表成为桶（buket），每个桶都有自己的编号（从0开始）。当有新键值对存储到无序容器中时，整个存储过程分为如下几步：

• 将该键值对中键的值带⼊设计好的哈希函数，会得到⼀个哈希值（⼀个整数，⽤ H 表示）；
• 将 H 和⽆序容器拥有桶的数ᰁ n 做整除运算（即 H % n），该结果即表示应将此键值对存储到的桶的编号；
• 建立一个新节点存储键值对，同时将该节点链接到相应编号的桶上。

另外，哈希表存储结构还有一个重要的属性，叫做负载因子。

该属性同样适用于无序容器，用于衡量容器存储键值对的空/满程序，即负载因⼦越⼤，意味着容器越满，即各链表中挂载着越多的键值对，这⽆疑会降低容器查找⽬标键值对的效率；反之，负载因⼦越⼩，容器肯定越空，但并不⼀定各个链表中挂载的键值对就越少。

举个例⼦，如果设计的哈希函数不合理，使得各个键值对的键带⼊该函数得到的哈希值始终相同（所有键值对始终存储在同⼀链表上）。这种情况下，即便增加桶数是的负载因⼦减⼩，该容器的查找效率依旧很差。

⽆序容器中，负载因⼦的计算⽅法为：负载因⼦ = 容器存储的总键值对 / 桶数

默认情况下，无序容器的最大负载因子位1.0。如果操作无序容器过程中，使得最大复杂因子超过了默认值，则容器会自动增加桶数，并重新进行哈希，以此来减少负载因子的值。

需要注意的是，此过程会导致容器迭代器失效，但是指向单个键值对的引用或者指针仍然有效。

这也就解释了，为什么我们在操作⽆序容器过程中，键值对的存储顺序有时会“莫名”的发⽣变动。

C++ STL 标准库为了⽅便⽤户更好地管控⽆序容器底层使⽤的哈希表存储结构，各个⽆序容器的模板类中都提供表所示的成员⽅法。

• bucket_count()：返回当前容器底层存储键值对时，使⽤桶的数量
• max_bucket_count()：返回当前系统中，unordered_xxx 容器底层最多可以使⽤多少个桶
• bucket_size(n)：返回第 n 个桶中存储键值对的数量
• bucket(key)：返回以 key 为键的键值对所在桶的编号
• load_factor()：返回 unordered_map 容器中当前的负载因⼦
• max_load_factor()：返回或者设置当前 unordered_map 容器的最⼤负载因⼦
• rehash(n)：尝试᯿新调整桶的数量为等于或⼤于 n 的值。如果 n ⼤于当前容器使⽤的桶数，则该⽅法会是容器重新哈希，该容器新的桶数将等于或⼤于 n。反之，如果 n 的值⼩于当前容器使⽤的桶数，则调⽤此⽅法可能没有任何作⽤。
• reserve(n)：将容器使⽤的桶数（bucket_count() ⽅法的返回值）设置为最适合存储 n 个元素的桶
• hash_function()：返回当前容器使⽤的哈希函数对象

对于关联式容器，只要是前缀带了unordered的就是⽆序，后缀带了multi的就是允许键᯿复，插⼊采⽤ insert_equal ⽽不是 insert_unique。

set、multiset、unordered_set、unordered_multiset

先来看一下set的性质：

• set以RB-tree作为其底层机制，所有元素都会根据元素的键值自动被排序
• set的元素就是键值，set不允许两个元素有相同的键值
• 不允许通过set的迭代器来改变set的元素值。因为set的元素值就是键值，更改了元素值就会影响其排列规则，如果任意更改元素值，会严重破坏set组织，因此在定义set的迭代器时被定义成了RB-tree的const_iterator
• 由于set不允许有两个相同的键值，所以插入时采用的是RB-tree的insert_unique方式
• 这⾥的类型的定义要注意⼀点, 都是 const 类型, 因为 set 的主键定义后就不能被修改了, 所以这⾥都是以const类型。

set 的主要实现⼤都是调⽤ RB-tree 的接⼝，这⾥的类型的定义要注意⼀点, 都是 const 类型， 因为 set 的主键定义后就不能被修改了，所以这⾥都是以 const 类型。

#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate 
   
    , class Alloc = alloc>#elsetemplate 
    
     #endifclass set {
   public:	 // typedefs:	 typedef Key key_type;	 typedef Key value_type;	 typedef Compare key_compare;	 typedef Compare value_compare;private:	 // ⼀RB-tree为接⼝封装	 typedef rb_tree
     
      , key_compare, Alloc>	rep_type;	 rep_type t; // red-black tree representing setpublic:	 // 定义的类型都是const类型, 不能修改	 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::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;	 typedef typename rep_type::difference_type difference_type; ...};
     
    
   

构造函数构造成员的时候调⽤的是 RB-tree 的 insert_unique。

class set {
   public:	 ...	 set() : t(Compare()) {
   }	 explicit set(const Compare& comp) : t(comp) {
   } // 不能隐式转换	 // 接受两个迭代器	 // 构造函数构造成员的时候调⽤的是RB-tree的insert_unique	 template 
   
    	 set(InputIterator first, InputIterator last)	 : t(Compare()) {
    t.insert_unique(first, last); }	 template 
    
     	 set(InputIterator first, InputIterator last, const Compare& comp)	 : t(comp) {
    t.insert_unique(first, last); }	  set(const value_type* first, const value_type* last)	 : t(Compare()) {
    t.insert_unique(first, last); }	 set(const value_type* first, const value_type* last, const Compare& comp)	 : t(comp) {
    t.insert_unique(first, last); }	 set(const_iterator first, const_iterator last)	 : t(Compare()) {
    t.insert_unique(first, last); }	 set(const_iterator first, const_iterator last, const Compare& comp)	 : t(comp) {
    t.insert_unique(first, last); }	 ...};
    
   

成员属性获取

class set {
   public:	 ...	 // 所有的操作都是通过调⽤RB-tree获取的	 key_compare key_comp() const {
    return t.key_comp(); }	 value_compare value_comp() const {
    return t.key_comp(); }	 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(); }	 // 交换	 void swap(set
   
    & x) {
    t.swap(x.t); }	 // 其他的find, count等都是直接调⽤的RB-tree的接⼝	 iterator find(const key_type& x) const {
    return t.find(x); }	 size_type count(const key_type& x) const {
    return t.count(x); }	 iterator lower_bound(const key_type& x) const {
   		 return t.lower_bound(x);	 }	 iterator upper_bound(const key_type& x) const {
   	 	return t.upper_bound(x);	 }	 pair
    
      equal_range(const key_type& x) const {
   		 return t.equal_range(x);	 }	 ...};
    
   

insert 操作源码

public:	 ...	 // pair类型我们准备下⼀节分析, 这⾥是直接调⽤insert_unique, 返回插⼊成功就是pair( , true), 插⼊失败则是( , false)	 typedef pair
   
     pair_iterator_bool;	 pair
    
      insert(const value_type& x) {
   		 pair
     
       p = t.insert_unique(x);		 return pair
      
       (p.first, p.second);	 }	 // 指定位置的插⼊	 iterator insert(iterator position, const value_type& x) {
   		 typedef typename rep_type::iterator rep_iterator;		 return t.insert_unique((rep_iterator&)position, x);	 }	 // 可接受范围插⼊	 template 
       
        	 void insert(InputIterator first, InputIterator last) {
   		 t.insert_unique(first, last);	 } ...
       
      
     
    
   

erase 的实现是通过调⽤ RB-tree 实现的 erase。

class set {
   public:	 ...	// erase的实现是通过调⽤RB-tree实现的erase	 void erase(iterator position) {
   		 typedef typename rep_type::iterator rep_iterator;		 t.erase((rep_iterator&)position);	 }	 size_type erase(const key_type& x) {
   		 return t.erase(x);	 }	 void erase(iterator first, iterator last) {
   		 typedef typename rep_type::iterator rep_iterator;	 	t.erase((rep_iterator&)first, (rep_iterator&)last);	 }	 void clear() {
    t.clear(); }	 ...};

最后剩下⼀个重载运算符，也是以 RB-tree 为接⼝调⽤。

multiset 与 set 特性完全相同，唯⼀差别在于它允许键值᯿复，因此插⼊操作采⽤的是底层机制 RB-tree 的insert_equal() ⽽⾮ insert_unique()

接下来我们来了解⼀下两个新的数据结构：hash_set 与 unordered_set。它们都属于基于hashtable构建的数据结构，并且时关键字和键值相等的关联容器。

那 hash_set 与 unordered_set 哪个更好呢？实际上 unordered_set 在C++11的时候被引⼊标准库了，⽽

hash_set 并没有，所以建议还是使⽤ unordered_set ⽐较好，这就好⽐⼀个是官⽅认证的，⼀个是⺠间流传的。

set、multiset、unordered_set、unordered_multiset 总结：

map、multimap、unordered_map、unordered_multimap

在分析 map 之前，我们来分析⼀下 pair 这种结构。pair 是⼀个有两个变量的结构体, 即谁都可以直接调⽤它的变量, 毕竟 struct 默认权限都是 public

template 
   
     // 两个参数类型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 
    
     	 pair(const pair
     
      & p) : first(p.first), second(p.second) {
   }	#endif};
     
    
   

重载实现：

template 
   
    inline bool operator==(const pair
    
     & x, const pair
     
      & y) {
    return x.first == y.first && x.second == y.second; }template 
      
       inline bool operator<(const pair
       
        & x, const pair
        
         & y) { return x.first < y.first || (!(y.first < x.first) && x.second < y.second);}
        
       
      
     
    
   

pair 将两个变量绑定在一起，这就为map< T1, T2 >提供了存储的基础。

map 基本结构定义如下：

#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate 
   
    , class Alloc = alloc>#elsetemplate 
    
     #endifclass map {
   public:	 typedef Key key_type; // 定义键值	 typedef T data_type; // 定义数据	 typedef T mapped_type;	 typedef pair
     
       value_type; // 这⾥定义了map的数据类型为pair, 且键值为const类型,不能修改	 typedef Compare key_compare; private:	 typedef rb_tree
      
       , key_compare, Alloc> rep_type; // 定义红⿊树,map是以rb-tree结构为基础的	 rep_type t; // red-black tree representing mappublic:...
      
     
    
   

构造函数：map 所有插⼊操作都是调⽤的 RB-tree 的 insert_unique，不允许出现᯿复的键。

class map {
   public: 	...public:	 // allocation/deallocation	 map() : t(Compare()) {
   } // 默认构造函数	 explicit map(const Compare& comp) : t(comp) {
   }	#ifdef __STL_MEMBER_TEMPLATES	 // 接受两个迭代器	 template 
   
    	 map(InputIterator first, InputIterator last)	 : t(Compare()) {
    t.insert_unique(first, last); }	 template 
    
     	 map(InputIterator first, InputIterator last, const Compare& comp)	 : t(comp) {
    t.insert_unique(first, last); }...
    
   

基本属性的获取

public:	 // 实际调⽤的是RB-tree的key_comp函数	 key_compare key_comp() const {
    return t.key_comp(); }	 // value_comp实际返回的是⼀个仿函数value_compare	 value_compare value_comp() const {
    return value_compare(t.key_comp()); }	 // 以下的begin, end等操作都是调⽤的是RB-tree的接⼝	 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(); }	 // 交换, 调⽤RB-tree的swap, 实际只交换head和count	 void swap(map
   
    & x) {
    t.swap(x.t); }	 ...};template 
    
     inline void swap(map
     
      & x,	 map
      
       & y) {
   	 x.swap(y);}
      
     
    
   

重载的分析

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

• insert(value_type(k, T()) : 查找是否存在该键值, 如果存在则返回该pair, 不存在这᯿新构造⼀该键值并且值为空
  -*((insert(value_type(k, T()))).first) : pair的第⼀个元素表示指向该元素的迭代器, 第⼆个元素指的是(false与true)是否存在, first 便是取出该迭代器⽽ * 取出pair
• *((insert(value_type(k, T()))).first)).second : 取出pair结构中的second保存的数据

注意，重载 operator[]，这⼀步返回是实值 value(即pair.second)的引⽤，假如原先没有定义 map 对象，即你访问的键值 key 不存在，则会⾃动新建⼀个 map 对象，键值 key 为你访问的键值 key，实值 value 为空

map、 multimap、unordered_map、unordered_multimap 总结：

map 和 multimap 的共同点：

• 底层都是红黑树，不可以通过迭代器修改元素的键，但是可以修改元素的值
• 拥有和list某些相同的特性，进行元素的增加和删除后，操作前的迭代器仍然可以用

不同点：

• map 键不能重复，⽀持 [] 运算符；
• multimap ⽀持᯿重复的键，不⽀持 [] 运算符；

map 并不像 set ⼀样将 iterator 设为 RB-tree 的 const_iterator，因为它允许⽤户通过其迭代器修改元素的实值。

map 和 unordered_map 共同点：

• 两者均不能有重复的建，均⽀持[]运算符

不同点

• map 底层实现为红⿊树
• unordered_map 底层实现为哈希表

unordered_map 是不允许存在相同的键存在，底层调⽤的 insert_unique() 插⼊元素

unordered_multimap 可以允许存在多个相同的键，底层调⽤的 insert_equal() 插⼊元素

map 并不像 set ⼀样将 iterator 设为 RB-tree 的 const_iterator，因为它允许⽤户通过其迭代器修改元素的实值。

转载地址：https://blog.csdn.net/zhizhengguan/article/details/122655266 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！