STL源码剖析-5

╰+攻爆jí腚メ 2022-01-20 03:35 194阅读 0赞

## 5.关联容器 ##

*  STL关联容器分为set和map两大类，容器底层均以RB-tree实现，RB-tree也是个容器

### 1.RB-tree的实现 ###

#### 1.1 RB-tree 的node的设计 ####

>  *  STL将node分为两层，父类base记录节点颜色以及父子指针，子类记录节点的值（感觉这样设计是为了避免模板带来的代码冗余）。

#ifndef STL_RB_TREE
    #define STL_RB_TREE
    
    #include<cstddef>
    #include "../allocator/stl_alloc.h"
    #include "../allocator/stl_construct.h"
    
    typedef bool __rb_tree_color_type;
    const __rb_tree_color_type __rb_tree_red=false;
    const __rb_tree_color_type __rb_tree_black=false;
    
    struct __rb_tree_node_base { 
    	typedef __rb_tree_color_type color_type;
    	typedef __rb_tree_node_base *base_ptr;
    
    	color_type color;
    	base_ptr parent;
    	base_ptr left;
    	base_ptr right;
    
    	static base_ptr minimum(base_ptr x) {
    		while(x->left!=nullptr) x=x->left;
    		return x;
    	}
    
    	static base_ptr maximum(base_ptr x) {
    		while (x->right!=nullptr) x=x->right;
    		return x;
    	}
    };
    
    template<typename Value>
    struct __rb_tree_node:public __rb_tree_node_base
    {
    	typedef __rb_tree_node<Value>* link_type;
    	Value value_field;
    };
    复制代码

#### 1.2 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!=nullptr) {
    			node=node->right;
    			while(node->left != nullptr) 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为hearder时等于，见下图
    		}
    	}
    
    	void decrement(){
    		// 当node 为 end()时
    		if (node->color == __rb_tree_red && node->parent->parent == node) node=node->right; //和迭代器实现的临界值（header）有关
    		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 <typename Value, typename Ref, typename Ptr>
    struct __rb_tree_iterator:public __rb_tree_base_iterator{
    	typedef Value value_type;
    	typedef Ref reference;
    	typedef Ptr pointer;
    	typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
    	typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
    	typedef __rb_tree_iterator<Value, Ref, Ptr> self;
    	typedef __rb_tree_node<Value>* link_type;
    
    	__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();
    		return tmp;
    	}
    };
    复制代码

> 一个空的rb\_tree如左图，插入第一个节点之后如右图, `header->parent==root;root->parent==header`

#### 1.3 RB-tree的数据结构 ####

template<typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc=alloc> // keyOfValue 作用是在Value中提取Key值, Compare是比较的仿函数
    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; //第二章空间配置相关的，分配node内存
    		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:
    		link_type get_node() {
        return rb_tree_node_allocator::allocate();}
    		void put_node(link_type p) {rb_tree_node_allocator::deallocate(p);}
    
    		link_type create_node(const value_type& x) {
    			link_type tmp = get_node();
    			try {
    				construct(&tmp->value_field, x);
    			} catch (...) {
    				put_node(tmp);
    				throw;
    			} 
    		}
    		link_type clone_node(link_type x) {
    			link_type tmp = create_node(x->value_field);
    			tmp->color = x->color;
    			tmp->left = 0;
    			tmp->right = 0;
    			return tmp;
    		}
    		void destroy_node(link_type x) {
    			destroy(&x->value_field);
    			put_node(x);
    		}
    		
    	protected:
    		size_type node_count; // 只维护这三个属性
    		link_type header;   // 插入节点需要保证header的正确性
    		Compare key_compare;
    		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 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);
    		}
    	public:
    		typedef __rb_tree_iterator<value_type, reference, pointer> iterator;
    	private:
    		void init() {
    			header = get_node();
    			color(header) = __rb_tree_red;
    			root() = 0;
    			leftmost() = header;
    			rightmost() = header;
    		}
    				
    		rb_tree(const Compare& comp=Compare()):node_count(0), key_compare(comp) {init();}
    		~rb_tree() {
    			clear();
    			put_node(header);
    		}
    	public:
    		iterator begin() {
        return leftmost();}
    		iterator end() {
        return header;}
    		bool empty() const {
        return node_count==0;}
    		size_type max_size() const {
        return size_type(-1);}
    };
    复制代码

#### 1.4 RB\_tree的元素操作 ####

>  *  rb\_tree提供两种插入操作
>     
>      *  insert\_unique, key值如果已经存在，插入操作不会进行
>      *  insert\_equal， key可以重复
>  *  这两种操作世界都是依赖于\_\_insert方法，\_\_insert实现如下

template<class Key, class Value, class KeyOfValue, class Compare, class Alloc> typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
    rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__insert(base_ptr x_, base_ptr y_, const Value& v){
    	link_type x = (link_type) x_;
    	link_type y = (link_type) y_;
    	link_type z;
    	if (y==header || x!=0 || key_compare(KeyOfValue()(v), key(y))) {
        //x应该一直==0
    		z = create_node(v);
    		left(y) = z;
    		if (y==header){
    			root() = z;
    			rightmost() == z;
    		}
    		else if (y==leftmost())
    			leftmost() = z;
    	} else {
    		z = create_node(v);
    		right(y) = z;
    		if (y==rightmost()) 
    			rightmost() = z;
    	}
    	parent(z) = y;
    	left(z) = 0;
    	right(z) = 0;
    	__rb_tree_rebalance(z, header->parent); //调节rb_tree
    	++node_count;
    	return iterator(z);
    
    }
    
    inline void
    _rb_tree_rebalance(__rb_tree_node_base* x, __rb_tree_node_base* &root){
    	x->color = __rb_tree_red; //新节点为红
    	while(x!=root && x->parent->color == __rb_tree_red) {
    		if (x->parent == x->parent->parent->left) {
    			__rb_tree_node_base *y=x->parent->parent->right;
    			if (y && y->color == __rb_tree_red) {   // 伯父节点为红时向上变色，一直到上层某节点的伯父节点为黑，使用伯父节点为黑的调整策略
    				x->parent->color = __rb_tree_black;
    				y->color = __rb_tree_black;
    				x->parent->parent->color = __rb_tree_red;
    				x = x->parent->parent;
    			} else {
    				if (x==x->parent->right) {
    					x = x->parent;
    					__rb_tree_rotate_left(x, root);
    				}
    				x->parent->color = __rb_tree_black;
    				x->parent->parent->color = __rb_tree_black;
    				__rb_tree_rotate_right(x->parent->parent, root);
    			}
    		} else {
    			__rb_tree_node_base* y = x->parent->left;
    			if (y && y->color == __rb_tree_red) {
    				x->parent->color = __rb_tree_black;
    				y->color = __rb_tree_black;
    				x->parent->parent->color = __rb_tree_red;
    				x = x->parent->parent;
    			} else {
    				if (x==x->parent->left) {
    					x = x->parent;
    					__rb_tree_rotate_right(x, root);
    				}
    				x->parent->color = __rb_tree_black;
    				x->parent->parent->color = __rb_tree_black;
    				__rb_tree_rotate_left(x->parent->parent, root);
    			}			
    		}
    	}
    	root->color = __rb_tree_black;
    }
    
    inline void
    __rb_tree_rotate_left(__rb_tree_node_base *x, __rb_tree_node_base*& root){
    	__rb_tree_node_base* y = x->right;
    	x->right = y->left;
    	if (y->left!=0) y->left->parent = x;
    	y->parent = x->parent;
    	if (x==root) root=y;
    	else if (x==x->parent->left) {
    		x->parent->left = y;
    	}else x->parent->right = y;
    	y->left = x;
    	x->parent = y;
    }
    inline void
    __rb_tree_rotate_right(__rb_tree_node_base *x, __rb_tree_node_base*& root){
    	__rb_tree_node_base * y = x->left;
    	x->left = y->right;
    	if (y->right != 0) {
    		y->right->parent = x;
    	}
    	y->parent = x->parent;
    	if (x==root) y=root;
    	else if (x==x->parent->right) x->parent->right = y;
    	else x->parent->left = y;
    	y->right = x;
    	x->parent = y;
    }
    复制代码

### 2.set ###

#ifndef STL_SET
    #define STL_SET
    
    #include "stl_rb_tree.h"
    
    template <class Key, class Compare = less<Key>, class Alloc=alloc> class set{ 
    	public:
    		typedef Key key_type;
    		typedef Key value_type;
    		typedef Compare key_compare;
    		typedef Compare value_compare;
    
    	private:
    		typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;
    
    		rep_type t;
    	public:
    		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;
    // ...
    
    };
    #endif
    复制代码

>  *  set 的实现都是基于 rep\_type t
>  *  其插入操作均是通过insert\_unique 实现
>  *  multiset其他和set一致，除了插入操作是通过insert\_equal

### 3.map ###

#ifndef STL_MAP
    #define STL_MAP
    
    #include "stl_rb_tree.h"
    
    template <class Key, class T, class Compare = less<Key>, class Alloc=alloc> class map{ 
    	public:
    		typedef Key key_type;
    		typedef T data_type;
    		typedef T mapped_type;
    		typedef pair<const Key, T> value_type;
    		typedef Compare key_compare;
    
    		class value_compare: public binary_function<value_type, value_type, bool> {
    			friend class map<Key, T, Compare, Alloc>;
    			protected:
    				Compare comp;
    				value_compare(Compare c): comp(c) {}
    			public:
    				bool operator() (const value_type &x, const value_type& y) const {
    					return comp(x.first, y.first);
    				}
    		};
    
    	private:
    		typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
    
    		rep_type t;
    复制代码

>  *  map和set 类似，只是value\_type 传的会是const Key 和 T的pair

### 4.hashtable ###

STL也提供了hashtable作为关联容器的底层容器，然后使用开链策略

>  *  hashtable buckets使用vector，vector保存的是node的指针。

// node 实现，链表
    template<class Value> struct __hashtable_node{ 
    	__hashtable_node *next;
    	Value val;
    };
    复制代码

// 迭代器实现
    template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> struct __hashtable_iterator{ 
    	typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;
    
    	typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
    	
    	typedef __hashtable_node<Value> node;
    	
    	typedef forward_iterator_tag iterator_category;
    	typedef Value value_type;
    	typedef ptrdiff_t difference_type;
    	typedef size_t size_type;
    	typedef Value& reference;
    	typedef Value* pointer;
    
    	node* cur; //迭代器目前指向节点
    	hashtable* ht;//为了保持从bucket跳转bucket
    
    	__hashtable_iterator(node* n, hashtable* tab): cur(n), ht(tab) {}
    	__hashtable_iterator(){}
    	reference operator*() const {
        return cur->val;}
    	pointer operator->() const {
        return &(operator*());} //注意一定会是表现的value的指针，而不是node
    	
    	iterator operator++() {
    		const node* old = cur;
    		cur =cur->next;
    		if (!cur) {
    			size_type bucket = ht->bkt_num(old->val);
    			while (!cur && ++bucket < ht->buckets.size()){
    				cur = ht->buckets[bucket];
    			}
    		}
    		return *this;
    	}
    
    };
    复制代码

//hashtable 实现
    template<class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
    class hashtable{
    	public:
    		typedef HashFcn hasher;
    		typedef EqualKey key_equal;
    		typedef size_t size_type;
    
    	private:
    		hasher hash;
    		key_equal equals;
    		ExtractKey get_key;
    
    		typedef __hashtable_node<Value> node;
    		typedef simple_alloc<node, Alloc> node_allocator;
    
    		vector<node*, Alloc> buckets;
    		size_type num_elements;
    
    	public:
    		size_type bucket_count() const {return buckets.size();}
    
    		node *new_node(const value_type& obj) {
    			node* n = node_allocator::allcocate();
    			n->next = 0;
    			try{
    				construct(&n->val, obj);
    				return n;
    			} catch (...){}
    		}
    		void delete_node(node* n);
    
    		pair<iterator, bool> insert_unique(const value_type& obj){
    			resize(num_elements+1);
    			return insert_unique_noresize(obj);
    		}
    
    		size_type bkt_num(const value_type& obj, size_t n) const{ //决定这个值在哪个bucket上
    			return bkt_num_key(get_key(obj), n);
    		}
    		size_type bkt_num_key(const key_type& key) const {
    			return bkt_num_key(key, buckets.size();)
    		}
    		size_type bkt_num_key(const key_type& key, size_t n) const {
    			return hash(key) % n;
    		}
    
    		void reseize(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); // next_size 是找出大于hint的下一个质数
    				if (n>old_n){
    					vector<node*,  Alloc> tmp(n, (node*) 0);
    					for (size_type bucket=0; bucket< old_n; ++buckets){
    						node* first = buckets[bucket];
    						while(first){
    							size_type new_bucket = bkt_num(first->val, n);
    							buckets[bucket] = first->next; //替换原先bucket的first
    							first->next = tmp[new_bucket]; //将first加到新的bucket的第一位做准备(加上下面一行逻辑)
    							tmp[new_bucket] = first;
    							first = buckets[bucket];
    
    						}
    					}
    					buckets.swap(tmp);
    				}
    			}
    		}
    		pair<iterator, bool> 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;
    			return pair<iterator, bool> (iterator(tmp. this), true);
    		}
    复制代码

### 5.hashset 等实现，略 ###