【STL】RB

STL】RB"/>

【STL】RB

今日记

近来，事情颇多，微烦。心想：STL离我远去，荣光渐失。但夜不能寐，终究是抵不过。罢了，罢了，今日无事，就随她吧！这个磨人的***！

当再次翻开《STL源码剖析》，已无往日思绪。唉~

概述

STL容器，放置物品的东西。所谓STL容器，即是一些常用的数据结构实现出来。

容器分为关联式容器和序列容器，而关联容器分为set（集合）和map（映射表）两大类，以及衍生出来的multiset（多键集合）和multimap（多键映射表）。这些容器的底层机制有两种实现方式，红黑树和哈希表。同时，他们也是一种独立容器，但并不对外开放。

所谓关联式容器，每个元素都有一个键值（key）和实值（value），插入后，会以某种规定放置在适当位置。同时，关联式容器没有头尾，所以没有push_back、pop_back等操作。

本章所采用版本为 SGI STL 2.91版本。

RB-tree（红黑树）

树的概况

树，在计算机科学中是一种很基础的数据结构，用途相当广泛。树同属于指针三剑客之一，由结点和边构成。同时，要了解路径长度、深度、高度等概念。

二查搜索树

二叉树，即根节点只有左右两个子节点，并且具有放置规则：任何结点的键值一定大于其左子树的每一个结点的键值，并且小于其右子树中每一个结点的键值。这样就可以提供一个对数时间来进行元素插入和访问。

要删除A的一个结点，若A只有一个子结点可以直接将A的子结点连接到A的父结点。若A有两个子结点，就将右子树最小节点取代A。

要插入新值的话，遇到比当前键值大则向右，否则向左，直到尾端。

平衡二叉搜索树

因为输入值不随机或者某些操作导致二叉树失去平衡，就会造成效率低落的情况。如图所示：

AVL tree

AVL tree是一个“加上额外平衡条件”的二叉搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN)。要求任何结点的左右子树高度相差最多为1。

当出现插入点改变平衡状态时，只需要调整最深的那个节点，便可使整棵树获得平衡。例如：

由于插入点会破坏平衡，假设最深结点为X，由于X最多有两个结点，所以平衡被破坏后，左右子树高度相差2，会出现四种情况：

1. 插入点位于X的左子节点的左子树-左左
2. 插入点位于X的左子节点的右子树-左右
3. 插入点位于X的右子节点的左子树-右左
4. 插入点位于X的右子节点的右子树-右右

1，4 称为外侧插入，可以使用单旋转操作。2，3称为内侧插入，可以采用双旋转操作。

单旋转

双旋转

双旋转即是通过两次单旋转完成操作。

红黑树（RB-tree）

红黑树，不仅是二叉搜索树，并且要满足以下规则：

1. 每个节点不是红色就是黑色
2. 根节点为黑色
3. 如果节点为红，其子节点必须是黑
4. 任一节点至NULL的任何路径，所含黑节点数目必须相同。

根据上述规则，新增节点必须为红；新增节点父结点必须是黑。当不能满足时，就需要进行调整颜色并旋转。

由于，插入删除操作过于复杂，本人能力有限，这部分先不谈了。

RB-tree的节点设计

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;struct _Rb_tree_node_base
{typedef _Rb_tree_Color_type _Color_type;typedef _Rb_tree_node_base* _Base_ptr;_Color_type _M_color; _Base_ptr _M_parent;_Base_ptr _M_left;_Base_ptr _M_right;static _Base_ptr _S_minimum(_Base_ptr __x){while (__x->_M_left != 0) __x = __x->_M_left;return __x;}static _Base_ptr _S_maximum(_Base_ptr __x){while (__x->_M_right != 0) __x = __x->_M_right;return __x;}
};template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{typedef _Rb_tree_node<_Value>* _Link_type;_Value _M_value_field;
};

下面是节点图标，如图所示：

RB-tree的迭代器

要想成功的将红黑树实现为一个泛型容器，其迭代器的设计非常关键。要考虑到类别、前进、后退、提取、访问等操作。
红黑树的节点与迭代器之间的关系如下：

struct __rb_tree_base_iterator
{typedef __rb_tree_node_base::base_ptr base_ptr;typedef bidirectional_iterator_tag iterator_category;typedef ptrdiff_t difference_type;base_ptr node;    // 用来连接红黑树的节点// 寻找该节点的后继节点上void increment(){if (node->right != 0) { // 如果存在右子节点node = node->right;       // 直接跳到右子节点上while (node->left != 0) // 然后一直往左子树走，直到左子树为空node = node->left;}else {                    // 没有右子节点base_ptr y = node->parent;    // 找出父节点while (node == y->right) {    // 如果该节点一直为它的父节点的右子节点node = y;                       // 就一直往上找，直到不为右子节点为止y = y->parent;}if (node->right != y)      // 若此时该节点不为它的父节点的右子节点node = y;                // 此时的父节点即为要找的后继节点// 否则此时的node即为要找的后继节点，此为特殊情况，如下// 我们要寻找根节点的下一个节点，而根节点没有右子节点// 此种情况需要配合rbtree的header节点的特殊设计，后面会讲到}                        }// 寻找该节点你的前置节点void decrement(){if (node->color == __rb_tree_red && // 如果此节点是红节点node->parent->parent == node)       // 且父节点的父节点等于自己node = node->right;                               // 则其右子节点即为其前置节点// 以上情况发生在node为header时，即node为end()时// 注意：header的右子节点为mostright，指向整棵树的max节点，后面会有解释else if (node->left != 0) {                 // 如果存在左子节点base_ptr y = node->left;            // 跳到左子节点上while (y->right != 0)               // 然后一直往右找，知道右子树为空y = y->right;           node = y;                          // 则找到前置节点}else {                                   // 如果该节点不存在左子节点base_ptr y = node->parent;         // 跳到它的父节点上while (node == y->left) {          // 如果它等于它的父子节点的左子节点node = y;                   // 则一直往上查y = y->parent;                                  }                               // 直到它不为父节点的左子节点未知node = y;                       // 此时他的父节点即为要找的前驱节点}}
};template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{//...型别声明// 迭代器的构造函数__rb_tree_iterator() {}__rb_tree_iterator(link_type x) { node = x; }__rb_tree_iterator(const iterator& it) { node = it.node; }// 提领和成员访问函数，重载了*和->操作符reference operator*() const { return link_type(node)->value_field; }pointer operator->() const { return &(operator*()); }// 前置++和后置++self& operator++() { increment(); return *this; }self operator++(int) {self tmp = *this;increment();        // 直接调用increment函数return tmp;}// 前置--和后置--self& operator--() { decrement(); return *this; }self operator--(int) {self tmp = *this;decrement();        // 直接调用decrement函数return tmp;}
};

RB-tree数据结构

template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;       typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator; // 专属配置器typedef __rb_tree_color_type color_type;
public:// 一些类型声明typedef Key key_type;typedef Value value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type& reference;typedef const value_type& const_reference;typedef rb_tree_node* link_type;typedef size_t size_type;typedef ptrdiff_t difference_type;
protected:// RB-tree的数据结构size_type node_count; // 记录树的节点个数link_type header;         // header节点设计Compare key_compare;  // 节点间的键值大小比较准则// 以下三个函数用来取得header的成员link_type& root() const { return (link_type&) header->parent; }link_type& leftmost() const { return (link_type&) header->left; }link_type& rightmost() const { return (link_type&) header->right; }// 以下六个函数用来取得节点的成员static link_type& left(link_type x) { return (link_type&)(x->left); }static link_type& right(link_type x) { return (link_type&)(x->right); }static link_type& parent(link_type x) { return (link_type&)(x->parent); }static reference value(link_type x) { return x->value_field; }static const Key& key(link_type x) { return KeyOfValue()(value(x)); }static color_type& color(link_type x) { return (color_type&)(x->color); }// 以下六个函数用来取得节点的成员，由于双层设计，导致这里需要两个定义static link_type& left(base_ptr x) { return (link_type&)(x->left); }static link_type& right(base_ptr x) { return (link_type&)(x->right); }static link_type& parent(base_ptr x) { return (link_type&)(x->parent); }static reference value(base_ptr x) { return ((link_type)x)->value_field; }static const Key& key(base_ptr x) { return KeyOfValue()(value(link_type(x)));} static color_type& color(base_ptr x) { return (color_type&)(link_type(x)->color); }// 求取极大值和极小值，这里直接调用节点结构的函数极可static link_type minimum(link_type x) { return (link_type)  __rb_tree_node_base::minimum(x);}static link_type maximum(link_type x) {return (link_type) __rb_tree_node_base::maximum(x);}public:// RBTree的迭代器定义typedef __rb_tree_iterator<value_type, reference, pointer> iterator;typedef __rb_tree_iterator<value_type, const_reference, const_pointer> const_iterator;
private://...void init() {   //构造一个空treeheader = get_node();   //产生一个节点空间，令header指向它color(header) = __rb_tree_red;  //令header为红色，用来将//root与header区分开root() = 0;          leftmost() = header;       //header的左子节点为自己rightmost() = header;      //header的右子节点为自己}
public:Compare key_comp() const { return key_compare; }  // 由于红黑树自带排序功能，所以必须传入一个比较器函数iterator begin() { return leftmost(); }        // RBTree的起始节点为左边最小值节点const_iterator begin() const { return leftmost(); }iterator end() { return header; }                         // RBTree的终止节点为右边最大值节点const_iterator end() const { return header; }bool empty() const { return node_count == 0; }    // 判断红黑树是否为空    size_type size() const { return node_count; }     // 获取红黑树的节点个数size_type max_size() const { return size_type(-1); }  // 获取红黑树的最大节点个数，// 没有容量的概念，故为sizetype最大值
};

作为map及set的底层数据结构，RB-tree的重要性不言而喻，而且面试时几乎是必考题，所以掌握RB-tree会受益匪浅

hashtable（哈希表）

二叉搜索树具有对数平均时间的查找表现，但他建立在一个假设：输入数据具有足够随机性。但哈希表也具有这种“常熟平均时间”的表现，不需依赖元素的随机性。

hashtable概述

hash table可以提供对任何有名项的存取和删除操作。例如：一个数组A，存放10个数字，便可对其常数时间操作，A[i]++等。而有名项的范围就很广，16-bits 的整数就有0~65535，还要包括字符串、char等类型。这就遇到两个现实问题：第一，要想把所有有名项表示一边，需要很大的空间，不切实际。第二，字符串等类型无法作为数组的索引。

对于第一个问题，解决办法之一就是使用某种映射函数，将大数变成小数。该函数被称为hash function。第二个问题，可以将一些字符串或者其他类型通过某种形式转化成整型作为索引。

但与之而来另一个问题就是，当两个数字映射到同一位置怎么办？这就是“碰撞”问题即“哈希冲突”。解决这种碰撞有很多方法，包括：

• 开放定址法：所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
• 再哈希法： 再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数，计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
• 链地址法： 每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。
• 建立公共溢出区： 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

比较常用的是链地址法。

hashtable的桶子与节点

下图即是链地址法的一种结构。包括桶子和存储数据的链表。

下面是节点定义：

template<calss Value>
struct __hashtable_node
{__hashtable_node* next;Value val;
}

如图所示：

这里存储数据的链表并非STL里的list或slist，而是自行维护的node。桶子则是由vector完成，拥有动态扩充的能力。

hashtable的迭代器

hashtable的迭代器维持整个“bucket vector”之间的关系，前进操作是尝试当前结点的下一个位置，如果到达list的尾端，就跳到下一个bucket身上。同时，不提供倒退的操作。

template <class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>
struct _Hashtable_iterator {typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> _Hashtable;typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> iterator;typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> const_iterator;typedef _Hashtable_node<_Val> _Node;typedef forward_iterator_tag iterator_category;typedef _Val value_type;typedef ptrdiff_t difference_type;typedef size_t size_type;typedef _Val& reference;typedef _Val* pointer;_Node* _M_cur;    	//迭代器目前所指的节点_Hashtable* _M_ht;	//保持对容器的连接关系_Hashtable_iterator(_Node* __n, _Hashtable* __tab) : _M_cur(__n), _M_ht(__tab) {}_Hashtable_iterator() {}reference operator*() const { return _M_cur->_M_val; }iterator& operator++();iterator operator++(int);bool operator==(const iterator& __it) const{ return _M_cur == __it._M_cur; }bool operator!=(const iterator& __it) const{ return _M_cur != __it._M_cur; }
};

operator++的非const版本

template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
{const _Node* __old = _M_cur;_M_cur = _M_cur->_M_next;if (!_M_cur) {size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())_M_cur = _M_ht->_M_buckets[__bucket];}return *this;
}template <class _Val, class _Key, class _HF, class _ExK, class _EqK,  class _All>
inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>_Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int)
{iterator __tmp = *this;++*this;return __tmp;
}

hashtable的数据结构

下面是hashtable的部分定义摘要：

template <class _Val, class _Key, class _HashFcn, class _ExtractKey, class _EqualKey, class _Alloc>
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;private:hasher                _M_hash;key_equal             _M_equals;_ExtractKey           _M_get_key;vector<_Node*,_Alloc> _M_buckets;    			//hashtable的桶是由vector实现的size_type             _M_num_elements;...public:size_type bucket_count() const { return _M_buckets.size(); }.....
};

其中，模板的几个参数分别代表：

• _Val：节点的值的类型
• _Key：节点键值类型
• _HashFcn：哈希函数的型别
• _ExtractKey：从节点中取出键值的方法
• _EqualKey：判断键值是否相同的方法
• _Alloc：空间配置器

如果桶满了怎么办，SGI提供了一个质数来设计表格大小，以备随时访问，进行扩充。当然，这只是SGI这么做的，并不确保所有STL都是这么做的。

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
};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);return pos == __last ? *(__last - 1) : *pos;
}

hashtable的构造与内存管理

• 节点配置与释放

node* new_node(const value_type& obj)
{node* n = node_allocator::allocate();n->next = 0;__STL_TRY {construct(&n->val, obj);return n;}__STL_UNWIND(node_allocator::deallocate(n));
}
void delete_node(node* n)
{destroy(&n->val);node_alllocaor::deallocate(n);
}

• hashtable构造：

hashtable(size_type n, const HashFcn& hf, const EqualKey& eql): hash(hf), equals(eql), get_key(ExtractKey()), num_elements(0)
{initialize_buckets(n);
}
void initialize_buckets(size_type n)
{buckets.reserve(n_bckets);buckets.insert(buckets.end(), n_buckets, (node*) 0);num_elements = 0;
}

• 插入元素：分为两种，insert_unique与insert_equal

// 插入操作,不允许重复pair<iterator, bool> insert_unique(const value_type& obj){resize(num_elements + 1);return insert_unique_noresize(obj);}template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::insert_unique_noresize(const value_type& obj)
{const  size_type  n = bkt_num(obj);node*  first = buckets[n];// 如果已经存在则直接返回for (node* cur = first; cur;  cur = cur->_next)if (equals(get_key(cur->val), get_key(obj)))return pair<iterator, bool>(iterator(cur, this), false);// 插入新节点node* tmp = new_node(obj);  //产生新节点tmp->next = first;        //将新节点插入链表头部buckets[n] = tmp;++num_elements;      //节点个数累计加1return pair<iterator, bool>(iterator(tmp, this), true); ///返回一个迭代器，指向新增节点
}//插入操作，允许重复iterator insert_equal(const value_type& obj){resize(num_elements + 1);return insert_equal_noresize(obj);}
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::insert_equal_noresize(const value_type& obj)
{const  size_type  n = bkt_num(obj);node*  first = buckets[n];// 如果已经存在则直接插入并返回for (node* cur = first; cur;  cur = cur->_next)if (equals(get_key(cur->val), get_key(obj))) {node* tmp = new_node(obj);  //产生新节点tmp->next = first;        //将新节点插入链表头部buckets[n] = tmp;++num_elements;      //节点个数累计加1return pair<iterator, bool>(iterator(tmp, this), true); ///返回一个迭代器，指向新增节点}// 表示没有发现新节点node* tmp = new_node(obj);  //产生新节点tmp->next = first;        //将新节点插入链表头部buckets[n] = tmp;++num_elements;      //节点个数累计加1return pair<iterator, bool>(iterator(tmp, this), true); ///返回一个迭代器，指向新增节点
}//判断是否需要重建表格
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::resize(size_type num_elements_hint)
{const size_type old_n = buckets.size();// 超过原来表格的大小时才进行调整if (__num_elements_hint > old_n) {// 新的表格大小const size_type  n = next_size(num_elements_hint);// 在边界情况下可能无法调整(没有更大的素数了)if (n > old_n) {vector<node*, All> tmp(n, (node*)(0),__STL_TRY {// 填充新的表格for (size_type bucket = 0;bucket < old_n; ++bucket) {node* first = buckets[bucket];  //指向节点所对应的起始节点while (first) {//以下找出节点落在哪一个新bucket内size_type __new_bucket = bkt_num(first->val, n);//令旧节点指向对应串行的下一个节点buckets[bucket] = first->next;//将当前节点插入到新bucket内first->next = tmp[new_bucket];tmp[new_bucket] = first;//准备处理下一个节点first = buckets[bucket];}}// 通过swap交换buckets.swap(tmp); }}}
}

• 判知元素的落脚处：

size_type bkt_num(const value_type& obj, size_t n)  const {return bkt_num_key(get_key(obj), n);
}
size_type bkt_num(const value_type& obj)  const 
{return bkt_num_key(get_key(obj));
}
size_type bkt_num_key(const value_type& key)  const {return bkt_num_key(key, buckets.size());
}
size_type bkt_num_key(const value_type& key,szie_t n)  const {return hash(key) % n;
}

元素操作

操作	功能
copy_from	复制整个hashtable
clear	hashtable整体删除
find	搜寻键值为key的元素
count	计算键值为key的元素个数

hash functions

hash function是计算元素位置的函数，SGI将这项任务交给bkt_num函数，然后再调用下列提供的hash function，取得一个可以对hashtable进行模运算的值

template <class Key> struct hash{}
//以下这个转换函数还没看太懂？？？？？
inline size_t __stl_hash_string(const char* s)
{unsigned long h  = 0;for (; *s; ++s)h = 5*h + *s;return size_t(h);
}template <>
__STL_TEMPLATE_NULL struct hash<char*>
{size_t operator()(const char *s)  const { return __stl_hash_string(s); }
};
//...

总结

红黑树与哈希表作为关联式容器的底层容器，重要性不言而喻，本人对于其理解非常浅薄，本文只是粗略的介绍，并未有实质的东西，望谅解。

参考资料：
《STL源码剖析》 - 侯捷