王权个人博客
0%

STL源码剖析

发表于 更新于 分类于 ，
本文字数： 50k 阅读时长 ≈ 46 分钟

迭代器概念与traits编程技法

迭代器是一种smart pointer

我们为list设计一个迭代器，则有如下 

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
tempalte <typename T>
class ListItem{
public:
	T value()const{return _value;}
	ListItem*next()const{return _next;}
	...
private:
	T _value;
	ListItem*_next;//单向链表
};


template <typename T>
class T{
public:
void insert_front(T value);
void insert_end(T value);
void display(std::ostream&os=std::cout)const;
//...
private:
ListItem<T>*_end;
ListItem<T>*_front;
long _size;
};


template<class Item>//Item可以是单向/双向链表
struct ListIter{
Item*ptr;
ListIter(Item*p=0):ptr(p){}
Item&operator*()const{return *ptr;}
Item*operator->()const{return *ptr;}

ListIter&operator++(){
ptr=ptr->next;
return *this;
}

ListIter operator++(int){
ListIter temp=*this;
++*this;
return temp;
}

bool operator==(const ListIter&i)const{
return ptr==i.ptr;
}

bool operator!=(const ListIter&i)const{
return ptr!=i.ptr;
}

}

void main(){

	List<int>myList;
	
	for(int i=0;i<5;++i){
		myList.insert(i);
		myList.insert(i+2);
	}
	
	myList.display();
	
	ListIter<ListItem<int> > begin(myList.front());
	ListIter<ListItem<int> > end;
	ListIter<ListItem<int> > begin;
	ListIter<ListItem<int> > iter;
	
	iter=find(begin,end,3);
	if(iter==end)
	cout<<"not found"<<endl;
	else
	cout<<"found."<<iter->value()<<endl;
}

Traits编程技法

class template可以用来“萃取”迭代器的特性。

1
2
3
4
template<class I>
struct iterator_traits{
typedef typename I::value_type value_type;
}

这个traits，其意义为，如果I定义有自己的value_type，那么通过这个traits的作用，萃取出来的value_type就是I::value_type。有

1
2
3
4
5
template<class T>
typename iterator_traits<T>::value_type //返回值 
func(I ite){
return *ite;
}

使用此种方法的好处是我们traits拥有一个特化版本

1
2
3
4
template<class T>
struct iterator_traits<T*>{ //偏特化版——迭代器是个原生指针
typedef T value_type;
}

image-20220917201732978

其中迭代器相应的型别有能以下五种：

1
2
3
4
5
value type
difference type
pointer
reference
iterator catagoly

若想要与STL容器兼容，则需要定义这五种型别。

1
2
3
4
5
6
7
8
template<class I>
struct iterator_traits{
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typename I::difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
}

迭代器型别之一:value type

value type是指迭代器所指对象的类别 。

迭代器型别之二: difference type

difference type为两个迭代器之间的距离，在STL中的count()，其传回值就必须要使用迭代器的difference type:

1
2
3
4
5
6
7
8
template<class I,class T>
typename iterator_traits<I>::difference_type;//函数返回型别 
count(I first,I last,const T&value){
typename iterator_traits<I>::difference_type n=0;
 for(;first!=last;++first)
 	if(*frist==value)++n;
 return n;
}

迭代器型别之三：reference type

在C++中，函数要传回左值，以by reference方式进行，当p是个mutable iterators时，如果value type是T，那么*p的型别不就是T，则是T&。

迭代器型别之四：pointer type

现在我们把reference type和pointer type的这两个型别加入traits内，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class I>
struct iterator_traits{
	...
	typedef typename I::pointer pointer;
	typedef typename I::reference reference;
};

//针对原生指针的"偏特化版"
template<class T>
struct iterator_traits<T*>{
	...
	typedef T*pointer;
	typedef T& reference;
}

//针对原生指针的pointer-to-const设计的偏特化版
template<class T>
struct iterator_traits<const T*>{
	...
	typedef const T* pointer;
	typedef const T& reference;
}

迭代器型别之五：iterator_category

根据移动特性与施行操作，迭代器被分为五类：

  • Input Iterator：这种迭代器所指的对象，不允许被外界改变，只读。
  • Output Iterator：唯写。
  • Forward Iterator：允许“写入型”算法(例如 replace())在此种迭代器所形成的区间上进行读写操作。
  • Bidirectional Iterator：可双向移动，某些算法需要逆向走访某个迭代器区间(如逆向拷贝某范围内元素)，可使用Bidirectional Iterators。
  • Random Access Iterator：前四种迭代器都只供应一部分指针算术能力(前三种支持 operator++，第四种再加上operator—)，第五种则涵盖所有指针算法能力，包括p+n，p-n，p[n]，p1-p2，p1<p2。

image-20220917204855810

拿advance()函数为例，该函数有两个参数，迭代器P和数据n，函数内部将p累进n次，下面有三份定义。

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
template<class InputIterator,class Distance>
void advance_II(InputIterator&i,Distance n){
	//单向，逐一前进
	while(n--)++;
}

template<class BidirectionalIterator,class Distance>
void advance_BI(BidirectionalIterator&i,Distance n){
	//双向，逐一前进
	if(n>=0)
		while(n--)++i;
	else 
		while(n++)--i;
}

template<class RandomAccessIterator,class Distance>
void advance_RAI(RandomAccessIterator&i,Distance n){
	//双向，跳跃前进
	i+=n;
}

//我们有函数运行时才进行选择则有如下做法
template<class InputIterator,class Distance>
void advance(InputIterator&i,Distance n){
	if(is_random_access_iterator(i))
		advance_RAI(i,n);
	else if(is_bidirectional_iterator(i))
		advance_RI(i,n);
	else
		advance_IT(i,n);
}

如下为我们在在编译期就确定使用某个版本，运用重载函数机制来达到这个目标。

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
//五个作为标记用的型别(tag types)
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct random_access_iterator_tag:public bidirectional_iterator_tag{};

//上术classes只作为标记用

template<class InputIterator,class Distance>
inline void _advance(InputIterator&i,Distance n,input_iterator_tag){
	//单向，逐一前进
	while(n--)++i;
}

//单纯的传递调用函数
template<class ForwardIterator,class Distance>
inline void _advance(ForwardIterator&i,Distance n,forward_iterator_tag){
	//单纯的进行传递调用
	_advance(i,n,input_iterator_tag());
}

template<class BidiectionalIterator,class Distance>
inline void _advance(BidiectionalIterator&i,Distance n,bidirectional_iterator_tag){
	//双向，逐一前进
	if(n>=0)
		while(n--)++i;
	else 
		while(n++)--i;
}

template<class RandomAccessIterator,class Distance>
inline void _advance(RandomAccessIterator&i,Distance n,random_access_iterator_tag){
	//双向，跳跃前进
	i+=n;
}

//使用traits机制，从迭代器中推导出类型

template<class InputIterator,class Distance>
inline void advance(InputIterator&i,Distance n){
	_advance(i,n,iterator_traits<InputIterator>::iterator_category());
}

//为了满足以上行为，traits须再增加一个相应的型别 
template<class T>
struct iterator_traits{
	....
	typedef typename I::iterator_category iterator_category;
}

我们可以通过继承来消除“单纯只做传递调用”的函数

image-20220917211848060

std::iterator 的保证

以distance为例，我们使用消除“单纯只做传递调用”的函数。

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
template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
_distance(InputIterator first,InputIterator last,input_iterator_tag){
	iterator_traits<InputIterator>::difference_type n=0;
	//逐一累计距离 
	while(first!=last){
		++first;
		++n;
	}
	return n;
}

template<class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
_distance(RandomAccessIterator first,RandomAccessIterator last,random_access_iterator_tag){
	//直接计算差距
	return last-first;
}

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first,InputIterator last){
	typedef typename iterator_traits<InputIterator>::iterator_category category;
	return _distance(first,last,category());
}

STL提供了一个iterators class如下，如果每个新设计的迭代器都继承自它，则可保证符合STL所需规范。

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class Category,class T,class Distance=ptrdiff_t,class Pointer=T*,class Reference=T&>
struct iterator{
	typedef Category iterator_category;
	typedef T value_type;
	typedef Distance difference_type;
	typedef Pointer pointer;
	typedef Reference reference;
}

template<class Item>
struct ListIter:public std::iterator<std::forwared_iterator_tag,Item>{

}

iterator源代码完整重列

image-20220917225724580

image-20220917225939967

序列式容器

image-20220918145701304

vector容器

vector定义

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
template<class T,class Alloc=alloc>
class vector{
public:
//vector嵌套型别定义
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;

void push_back(const T&x){
	if(finish!=end_of_storage){//若有备用空间则使用备用空间
		construct(finish,x);
		++finish;
	}else //没有就开拓新空间
		insert_aux(end(),x);
}
void pop_back(){
	--finish;
	destroy(finish);
}
iterator erase(iterator position){//清除某位置上的元素
	if(position+1!=end()){
		copy(position+1,finish,position);//把position后续的位置逐一往前移动一个，并进行覆盖
		--finish;
	}
	destory(finish);
	return position;
}
private:
iterator start;//表示目前使用空间的头
iterator finish;//表示目前使用空间的尾
iterator end_of_storage;//表示目前可用空间的尾

}

image-20220918152216237

vector的构造与内存管理

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
template<class T,class Alloc>
void vector<T,Alloc>::insert_aux(iterator position,const T&x){
	if(finish!=end_of_strong){//若还有备用空间
		//在备用空间起始处构造一个元素，并以vector最后一个元素为其初值
		construct(finish,*(finish-1));
		++finish;
		T x_copy=x;
		copy_backward(position,finish-2,finish-1);
		*postion=x_copy;
	}else{//无备用空间
		const size_type old_size=size();
		const size_type len=old_size!=0?2*old_size:1;
		//若空间大小为0，则配置1个元素大小
		//如果原大小不为0，则配置原大小的两倍
		//前半段用来放置原数据，后半段准备用来旋转新数据
		
		iterator new_start=data_allocator::allocate(len);//实际配置
		iterator new_finish=new_start;
		try{
			//将原数据拷贝到新的空间
			new_finish=uninitialized_copy(start,position,new_start);
			//为新元素设定初始值为x
			construct(new_finish,x);
			++new_finish;
			//将安插点的原内容也拷贝过来
			new_finish=uninitialized_copy(position,finish,new_finish);
		}
		catch(...){
			...	
		}
		//析构释放原vector
		destory(begin(),end());
		deallocate();
		
		//调整迭代器
		start=new_start;
		finish=new_finish;
		end_of_storage=new_start+len;
		
	}
}

当有备用空间时，示意图如下

绘图2

绘图3

当无备用空间时，先扩展空间，再复制前半段的数据，再插入值，再复制后半段的数据。

vector的元素操作：pop_back,erase,clear,insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//将尾端元素拿掉，并调整大小
void pop_back(){
	--finish;	//将尾端标记往前移动一格
	destory(finish);
}

//清除erase[first,last)中所有元素
iterator erase(iterator first,iterator last){
	iterator i=copy(last,finish,first);//把[last,finish]的元素移动到头
	destory(i,finish);
	finish=finish-(last-first);
	return first;
}

//清除某个位置上的元素
iterator erase(iterator position){
	if(position+1!=end())
		copy(position+1,finish,position);
	--finish;
	destory(finish);
	return position;
}

void clear(){erase(begin(),end());}

image-20220918161517293

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
//从position开始,插入n个元素，元素初值为x
template<class T,class Alloc>
void vector<T,Alloc>::insert(iterator position,size_type n,const T&x){
	if(n!=0){
		if(size_type(end_of_storage-finish)>=n){
			//备用空间大于等于"新增元素个数"
			T x_copy=x;
			//以下计算插入点之后的现有元素个数
			const size_type elems_after=finish-position;
			iterator old_finish=finish;
			if(elems_after>n){
				//插入点之后的现有元素大于"新增元素个数"
				uninitialized_copy(finish-n,finish,finish);//后移finish-n个元素，为插入元素让出位置		finish+=n;
				copy_backward(position,old_finish-n,old_finish);//拷贝
				fill(position,position+n,x_copy);//从插入点开始填入新值
			}else{
				//插入点之后的现有元素个数小于等于新增元素个数 
				uninitialize_fill_n(finish,n-elems_after,x_copy);//在结尾处，去初始化n-elems_after个元素
				finish+=n-elems_after;
				uninitialize_copy(position,old_finish,finish);//后移拷贝
				finish+=elems_after;
				fill(position,old_finish,x_copy);//去赋初始值
			}
		}else{
			//备用空间小于"新增元素个数 "
			//首先决定新长度,旧长度的两倍，或旧长度+新增元素个数 
			const size_type old_size=size();
			const size_type len=old_size+max(old_size,n);
			//以下配置新的vector空间
			iterator new_start=data_allocator::allocate(len);
			iterator new_finish=new_start;
			//以下首先将旧vector的插入点之前的元素复制到新空间
			new_finish=uinitialized_copy(start,position,new_start);
			//以下再将新增元素填入新空间
			new_finish=uninitialized_fill_n(new_finish,n,x);
			//以下再新旧vector的插入点之后的元素复制到新空间
			new_finish=uninitialized_copy(position,finish,new_finish);
		}
	}
}

image-20220918173022204

List容器

list节点

1
2
3
4
5
6
7
8
//list节点结构:
template<class T>
struct _list_node{
	typedef void*void_pointer;
	void_pointer prev;//指向上一节点
	void_pointer next;//指向下一节点
	T data;
}

image-20220918173740864

list的迭代器

image-20220918174116134

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
template<class T,class Ref,class Ptr>
struct _list_iterator{
	typedef _list_iterator<T,T&,T*> iterator;
	typedef _list_iterator<T,Ref,Ptr> self;
	
	typedef bidirectional_iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef _list_node<T>*link_type;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	
	link_type node;//指向List节点
	
	self&operator++(){
		node=(link_type)(*(node).next);
		return *this;
	}
	
	self operator++(int){
		self temp=*this;
		++*this;
		return temp;
	}
	
	self& operator--(){
		node=(link_type)((*node).prev);
		return *this;
	}
	
	self operator--(){
		self temp=*this;
		--*this;
		return temp;
	}
}

list的结构是个环状双向链表

image-20220918174753565

list的元素操作

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
//插入一个节点，作为头节点
void push_front(const T&x){insert(begin(),x);}
//插入一个节点，作为尾节点
void push_back(const T&x){insert(end(),x);}

//移除迭代器position所指的节点
iterator erase(iterator position){
	link_type next_node=link_type(position.node->next);//保存上一节点
	link_type prev_node=link_type(position.node->prev);//保存下一节点
	prev_node->next=next_node;//使上一节点的下一节点指向当前节点的下一节点
	next_node->prev=prev_node;//使下一节点的上一节点指向当前节点的上一节点
	destroy_node(position.node);
	return iterator(next_node);
}

//移除头节点
void pop_front(){erase(begin());}
//移除尾节点
void pop_back(){
	iterator temp=end();
	erase(--temp);
}

//清除所有节点
template<class T,class Alloc>
void list<T,Alloc>::clear(){
	link_type cur=(link_type)node->next;//begin()//排除头节点
	while(cur!=node){//遍历节点
		link_type temp=cur;
		cur=(link_type)cur->next;
		destroy_node(temp);//销毁一个节点
	}
	//恢复node原始状态
	node->next=node;
	node->prev=node;
}

//将数值为value之所有元素移除
template<class T,class Alloc>
void list<T,Alloc>::remove(const T&value){
	iterator first=begin();
	iterator last=end();
	while(first!=last){ //遍历每一个节点
		iterator next=first;
		++next;
		if(*first==value)erase(first);//移除
		first=next;
	}
}

image-20220918181231236

1
2
3
4
5
6
7
8
9
10
11
12
13
//将[first,last)内所有元素移动到position之前
void transfer(iterator position,iterator first,iterator last){
	//过程分为两部，1为先取出[first,last)链表，2再把[first,last)缝合进position
	if(position!=last){
		(*(link_type)((*last.node).prev))).next=position.node;//使last的上一节点的下一节点指向position
		(*(link_type)((*frist.node).prev))).next=last.node;//使frist的上一节点的下一节点指向last，因为不会移动last
		(*(link_type)((*position.node).prev))).next=frist.node;//使position节点的上一节点的下一节点指向first
		link_type temp=link_type((*position.node).prev);
		(*position.node).prev=(*last.node).prev;
		(*last.node).prev=(*frist.node).prev;
		(*first.node).prev=temp;
	}
}

image-20220918182657558

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//merge()将x合并到*this身上，两个list的内容必须要先经过递增排序 
template<class T,class Alloc>
void list<T,Alloc>::merge(list<T,Alloc>&x){
	iterator first1=begin();
	iterator last1=end();
	iterator first2=x.begin();
	iterator last2=x.end();
	
	//注意，前提是，两个lists都已递增排序 
	while(first1!=last1 && first2!=last2)
		if(*frist2<*frist1){//如果frist2中的元素小于first1中某个节点，就把frist2的元素持续插入first中
			iterator next=first2;
			transfer(first1,first2,++next);
			first2=next;
		}else
			++first1;
	if(first2!=last2)transfer(last1,first2,last2);//若frist2中还有元素大于first1中最大的元素，则插入first2中的剩余元素到first1中
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//reserve将*this的内容逆向重置
template<class T,class Alloc>
void list<T,Alloc>::reverse(){
	//如果是空链表，或仅有一个元素，就不进行任何操作
	if(node->next==node||link_type(node->next)->next==node)
		return;
	iterator first=begin();
	++first;
	while(first!=end){
		iterator old=first;
		++first;
		transfer(begin(),old,first);//持续插入头节点
	}
}

deque容器

deque是一种双向开口的连续线性空间，双向开口指在头尾两端分别做元素的插入和删除操作。

image-20220919222749075

deque与vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入或移除操作。二在于deque没有所谓容量观念，因为它是动态地以分段连接空间组合而成，随时可以增加一段新的空间并链接起来。

deque的中控器

deque采用一块所为的map作为主控。这里所谓的map是一小块连续空间，其中每个元素都是指针，指向另一段连续线性空间，称为缓冲区，缓冲区才是deque的储存空间主体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T,class Alloc=alloc,size_t BUfsiz=0>
class deque{
public:
	typedef T value_type;
	typedef value_type*pointer;
	...
protected:
	//元素指针的指针
	typedef pointer*map_pointer;
protected:
	map_pointer map;//指向Map,Map是块连续空间，其内每个元素都是一个指针(称为节点),指向一块缓冲区
	size_type map_size;//Map内可容纳多少指针
	...
}

image-20220919224250620

deque的迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class T,class Ref,class Ptr,size_t BufSize>
struct _deque_iterator{
	typedef _deque_iterator<T,T&,T*,BufSize> iterator;
	typedef _deque_iteartor<T,const T&,const T*,BufSize>const_iterator;
	static size_t buffer_size(){return _deque_buf_size(BufSize,sizeof(T));}
	
	typedef random_access_iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef T**map_pointer;
	
	typedef _deque_iterator self;
	
	//保持与容器的联结
	T*cur;//此迭代器所指之缓冲区中的现行元素
	T*frist;//此迭代器所指之缓冲区的头
	T*last;//此迭代器所指之缓冲区的尾(含备用空间)
	map_pointer node;//指向管控中心
	...
}

image-20220920085356368

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
//跳过一个缓冲区
void set_node(map_pointer new_node){
	node=new_node;
	first=*new_node;
	last=first+difference_type(buffer_size);
}
difference_type operator-(const self&x)const{
	return difference_type(buffer_size()*(node-x.node-1)+(cur-first)+(x.last-x.cur));
	//返回相隔多个元素
}
self&operator++(){
	++cur;//切换至下一元素
	if(cur==last){//如果已达到所在缓冲区的尾端
		set_node(node+1);//切换至下一节点
		cur=first;
	}
	return *this;
}
self&operator(){
	if(cur==first){
		set_node(node-1);//切换至前一节点
		cur=last;
	}
	--cur;
	return *this;
}

//以下实现随机存放,迭代器可以直接跳跃N个距离
slef&operator+=(difference_type n){
	difference_type offset=n+(cur-first);//偏移n个距离 
	if(offset>0&&offset<difference_type(buffer_size())){
		//目标位置在同一缓冲区
	}else{
		//目标位置不在同一缓冲区
		difference_type node_offset=offset>0?offset/difference_type(buffer_size()):
									-difference_type((-offset-1)/buffer_size())-1;
		//切换至正确的节点
		set_node(node+node_offset);
		//切换至正确元素
		cur=first+(offset-node_offset*difference_type(buffer_size()));
	}
	return *this;
}

deque的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<class T,class Alloc=alloc,size_t BufSize=0>
class deque{
	public:
		typedef T value_type;
		typedef value_type* pointer;
		typedef size_t size_type;
	public:
		typedef _deque_iterator<T,T&,T*,BufSize>iterator;
	
	protected:
		//元素指针的指针
		typedef pointer* map_pointer;
	protected:
		iterator start;//表现第一个节点
		iterator finish;//表现最后一个节点
		
		map_pointer map;//指向map,map是块连续空间
						//其每个元素都是个指针，指向一个节点(缓冲区)
		size_type map_size;//map内有多少个指针
}
1
2
3
4
5
6
7
8
9
10
11
template<class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::fill_initialize(size_type n,const value_type&value){
	create_map_and_nodes(n);//把deque的结构都产生并安排好
	map_pointer cur;
	//为每个节点的缓冲区设定初值
	for(cur=start.node;cur<finish.node;++cur){
		uninitialized_fill(*cur,*cur+buffer_size(),value);
	}
	//最后一个节点，因为尾端可能有备用空间，不必设置初值
	uninitialize_fill(finish.first,finish.cur,value);
}
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
//create_map_and_nodes()负责产生并安排好deque结构 
template<class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::create_map_and_nodes(size_type num_elements){
	//需要的节点数=(元素个数/每个缓冲区可容纳的元素个数)+1
	//如果刚好整除，会多配一个节点
	size_type num_nodes=num_elements/buffer_size()+1;
	
	//一个map要管理几个节点,最少8个，最多为所需节点数+2
	//前后各预留一个，扩充时使用
	map_size=max(initial_map_size(),num_nodes+2);
	//配置出一个具有map_size个节点的map
	map=map_allocator::allocate(map_size);
	
	//以下令nstart和nfinish指向所拥有之全部节点的最中央区域
	//保存在最中央，可使头尾端的扩充能量一样大，每个节点对应一个缓冲区
	map_pointer nstart=map+(map_size-num_nodes)/2;//在中间位置
	map_pointer nfinish=nstart+num_nodes+1;
	
	map_pointer cur;
	//为map内的每个现用节点配置缓冲区。所有缓冲区加起来就是deque的可用空间
	for(cur=nstart;cur<=nfinish;++cur){
		*cur=allocate_node();
	}
	
	start.set_node(nstart);
	finish.set_node(nfinish);
	start.cur=start.first;
	//指向最后一个未装满元素的缓冲区
	finish.cur=finish.first+num_elements%buffer_size();
	
}

image-20220922090758860

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void push_back(const value_type&t){
	if(finish.cur!=finish.last-1){
		//最后缓冲区尚有两个(含)以上的元素备用空间
		construct(finish.cur,t);//直接在备用空间上构造元素
		++finish.cur;//调整使用缓冲区的状态
	}else{//最后缓冲区只剩一个元素备用空间
		push_back_aux(t);
	}
}

template<class T,class Alloc,size_t BufSize>
void deque<T,Alloc,size_t BufSize>::push_back_aux(const value_type&t){
	value_type t_copy=t;
	reserve_map_at_back();//若符合某种条件则必须重新换一个map
	*(finish.node+1)=allocate_node();//配置一个新节点(缓冲区)，调整中控器
	construct(finish.cur,t_copy);//针对标的元素设值
	finish.set_node(finish.node+1);//改变finish，令其指向新节点
	finish.cur=finish.first;//设定finish的状态
}

image-20220922092516084

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void push_front(const value_type&t){
	if(start.cur!=start.first){//第一缓冲区尚有备用空间
		construct(start.cur-1,t);//直接在备用空间上构造元素
		--start.cur;//调整第一缓冲区的使用状态
	}else{
		push_front_aux(t);
	}
}

//当第一缓冲区没有备用元素时才会调用
template<class T,class Alloc,size_t BufSize>
void deque<T,class Alloc,size_t BufSize>::push_front_aux(const value_type&t){
	value_type t_copy=t;
	reserve_map_at_front();//若符合某种条件则必须重新换一个map
	*(start.node-1)=allocate_node();//配置一个新节点
	start.set_node(start.node-1);//改变start,令其指向新节点
	start.cur=start.last-1;//设定start的状态
	construct(start.cur,t_copy);//针对标的元素设值
	
	start.set_node(start.node+1);
	start.cur=start.first;
	deallcoate_node(*(start.node-1));
}

image-20220922093835348

image-20220922094019218

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void push_front(const value_type&t){
	if(start.cur!=start.frist){//第一缓冲区尚有备用空间
		construct(start.cur-1,t);//直接在备用空间上构造元素
		--start.cur;//调整第一缓冲区的使用状态
	}else //第一缓冲区已无备用空间
		push_front_aux(t);
}
//在目前状态下，第一缓冲区并无备用空间，调用push_front_aux()
//只有当第一缓冲区没有任何备用元素时才会调用
template<class T,class Alloc,size_t BuffSize>
void deque<T,Alloc,BufSize>::push_front_aux(const value_type&t){
	value_type t_copy=t;
	reserve_map_at_front();//符合条件，重新更换一个map
	*(start.node-1)=allocate_node();//配置一个新节点(缓冲区)
	start.set_node(start.node-1);//改变start,令其指向新节点
	start.cur=start.last-1;//设定start的状态
	construct(start.cur,t_copy);//针对标的元素设值 
	
	start.set_node(start_node+1);
	start.cur=start.first;
	deallocate_node(*(start.node-1));
}

image-20220922220700986

image-20220922220722442

我们判断map什么时候需要重新整治,可以同reserve_map_at_back()和reserve_map_at_front()进行，实际的操作由reallocate_map()进行执行

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
void reserve_map_at_back(size_type nodes_to_add=1){
	if(nodes_to_add+1>map_size-(finish.node-map)){
		//如果map尾端的节点备用空间不足
		//符合以上条件则必须重新换一个map(拷贝原来的,配置更大的)
		reallocate_map(nodes_to_add,false);
	}
}
void reserve_map_at_front(size_type nodes_to_add=1){
	if(nodes_to_add>start.node-map){
		//如果map前端的节点备用空间不足
		//符合以上条件则必须要重新换一个map
		reallocate_map(nodes_to_add,true);
	}
}
template<class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BUfSize>::reallocate_map(size_type nodes_to_add,bool add_at_front){
	size_type old_num_nodes=finish.node-start.node+1;//获得两个迭代器之间的元素数
	size_type new_num_nodes=old_num_nodes+nodes_to_add;
	
	map_pointer new_nstart;
	//map_size为中控器之前定义，用于初始化map的大小
	if(map_size>2*new_num_nodes){//如果之前的map还有多余的大小
		new_nstart=map+(map_size-new_num_nodes)/2+(add_at_front?notes_to_add:0);
		if(new_nstart<start.node)
			copy(start.node,finish.node+1,new_nstart);//复制内容
		else
			//逆序复制
			copy_backward(start.node,finish.node+1,new_nstart+old_num_nodes);
	}else{
		size_type new_map_size=map_size+max(map_size,nodes_to_add)+2;
		//配置一块空间，给新map使用
		map_pointer new_map=map_allocator::allocate(new_map_size);
		new_start=new_map+(new_map_size-new_num_nodes)/2+
				  (add_at_front?nodes_to_add:0);
		//把原map内容拷贝过来
		copy(start.node,finish.node+1,new_nstart);
		//释放原map
		map_allocator::deallocate(map,map_size);
		//设定新map的起始地址大小
		map=new_map;
		map_size=new_map_size;
	}
	start.set_node(new_nstart);
	finish.set_node(new_nstart+old_num_nodes-1);
}

image-20220922230241676

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
void pop_back(){
	if(finish.cur!=finish.first){
		//最后缓冲区有一个(或更多)元素
		--frist.cur;
		destroy(finish.cur);
	}else
		//最后缓冲区没有任何元素
		pop_back_aux();
}

template<class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::pop_back_aux(){
	deallocate_note(finish.first);//释放最后一个缓冲区
	finish.set_node(finish.node-1);//使之指向上一个缓冲区的最后一个元素
	finish.cur=finish.last-1;//上一个缓冲区的最后一个元素
	destory(finish.cur);//析构该元素
}

void pop_front(){
	if(start.cur!=start.last-1){
		//第一缓冲区还有更多元素
		destory(start.cur);
		++start.cur;//移动指针
	}else{
		pop_front_aux();//第一缓冲区仅有一个元素
	}
}

template<class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::pop_front_aux(){
	destroy(start.cur);
	deallocate_node(start.first);//释放第一缓冲区
	start.set_node(start.node+1);//调整start的状态，使之指向下一缓冲区的第一个元素
	start.cur=start.first;

}

template<class T,class Alloc,size_t BufSize>
void deque<T,Alloc,BufSize>::clear(){
	//指针非头尾缓冲区以外的部分，它们的缓冲区元素一定都是满的
	for(map_pointer node=start.node+1;node<finish.node;++node){
		//将缓冲区中所有元素析构 
		destroy(*node,*node+buffer_size());
		//释放缓冲区内存
		data_allocator::deallocate(*node,buffer_size());
	}
	
	if(start.node!=finish.node){//至少有头尾两个缓冲区
		destory(start.cur,start.last);//析构头缓冲区所有元素
		destory(finish.cur,finish.last);//析构尾缓冲区所有元素
		//释放尾部缓冲区,保留头部缓冲区
		data_allocator::deallocate(finish.first,buffer_size());
	}else{//头尾在一个缓冲区
		destory(start.cur,finish.cur);
	}
	finish=start;
}

//清除Pos所指的元素,pose为消除点
iterator erase(iterator pos){
	iterator next=pos;
	++next;
	difference_type index=pos-start;//消除点之前的元素个数 
	if(index<(size())>>1){ //如果消除点之前的元素较少，就移动消除点之前的元素size()>>1约等于size()/2
	copy_backward(start,pos,next);//移动元素
	pop_front();//冗余元素
	}else{//消除点之后的元素较少
		copy(next,finish,pos);
		pop_back();
	}
	return start+index;
}

//清除[first,last)区间内的所有元素
template<class T,class Alloc,size_t BufSize>
deque<T,Alloc,Bufsize>::iterator
deque<T,Alloc,BufSize>::earase(iterator first,iterator last){
	if(first==start&&last==finish){//如果清除区间为整个deque
		clear();
		return finish;
	}else{
		difference_type n=last-first;	//清除区间长度
		difference_type elems_before=first-start;//清除区间前方的元素个数 
		if(elems_before<(size()-n)/2){ //如果前方元素较少
			copy_backward(start,first,last);//向后移动前方元素
			iterator new_start=start+n;//标记deque的新起点
			destory(start,new_start);//移动完毕，将冗余的元素析构 
			//以下将冗余的缓冲区释放
			for(map_pointer cur=start.node;cur<new_start.node;++cur){
				data_deallocate::deallocate(*cur,buffer_size());
				start=new_start;//设定deque的新起点
			}
		}else{//消除区间后方的元素较少
			copy(last,finish,first);//向前移动后方元素
			iterator new_finish=finish-n;//标记deque的新起点
			destory(new_finish,fiish);//将冗余元素析构
			//以下将冗余缓冲区释放
			for(map_pointer cur=new_finish.node+1;cur<=finish.node;++cur){
				data_allocator::deallocate(*cur,buffer_size());
			}
			finish=new_finish;
		}
		return start+elems_before;
	}
}

heap(堆)

image-20220925153605844

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class RandomAccessIterator>
inline void push_heap(RandomAccessIterator first,RandomAccessIterator last){
	_push_heap_aux(fist,last,distance_type(first),value_type(first));
}

template<class RandomAccessIterator,class Distance,class T>
inline void _push_heap_aux(RandomAccessIterator first,RandomAccessIterator last,Distance*,T*){
	_push_heap(fist,Distance((last-first)-1),Distance(0),T(*(last-1)));
}

template<class RandomAccessIterator,class Distance,class T>
void _push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){
	Distance parent=(holeIndex-1)/2;//找到父节点
	while(holeIndex>topIndex&&*(first+parent)<value){
		//当尚未到达顶端，且父节点小于新值
		*(first+holeIndex)=*(first+parent);//令洞值为父值
		holeIndex=parent;//调整洞号,向上提升至父节点
		parent=(holeIndex-1)/2;//新的洞的父节点
	}//持续至顶端
	*(first+holeIndex)=value;//令洞值为新值，完成插入操作
}


image-20220925164901821

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
template<class RandomAccessIterator>
inline void pop_heap(RandomAccessIteraor first,RandomAccessIterator last){
	_pop_heap_aux(first,last,value_type(first));
}

template<class RandomAccessIterator,class T>
inline void _pop_heap_aux(RandomAccessIterator fist,RandomAccessIterator last,T*){
	_pop_heap(first,last-1,last-1,T(*(last-1)),distance_type(first));
	//pop操作的结果就为底部容器的第一个元素,因此，首先欲调整值为尾值，然后将首值调至尾节点(所以以上将迭代器Result设为last-1)。然后重整[first,last-1)使之重新成为一个合格的heap
}

template<Class RandomAccessIteartor,class T,class Distance>
inline void _pop_heap(RandomAccessIterator first,RadomAccessIterator last,
					  RandomAccessIterator result,T value,Distance*){
	*result=*frist;//设置尾值为首值 
	_adjust_heap(fist,Distance(0),Distance(last-first),value);
	//以上欲调整heap,洞号为0,欲调整值为value(原尾值)
}

template<class RandomAccessIterator,class Distance,class T>
void _adjust_heap(RandomAccessIteartor first,Distance holeIndex,Distance len,T value){
	Distance topIndex=holeIndex;
	Distance secondChild=2*holeIndex+2;//洞节点之右子节点
	while(secondChild<len){
		//比较洞之节点之左右两个子值，然后以secondChild代表较大的节点
		if(*(first+secondChild)<*(first+(secondChild-1)))
			secondChild--;
		//令较大子值为洞值，再令洞号下称至较大子节点处
		*(first+holeIndex)=*(first+secondChild);
		holeIndex=secondChild;
		//找出新洞节点的右子节点
		secondChild=2*(secondChild+1);
	}
	if(secondChild==len){//没有右子节点,只有左子节点
		//令左子值为洞值，再令洞号下移至左子节点处
		*(first+holeIndex)=*(first+(secondChild-1));
		holeIndex=secondIndex-1;
	}
}

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first,RandomAccessIterator last){
	//以下，每执行一次pop_heap()，极值即被放在尾端
	//扣除尾端再执行一次pop_heap(),次极值又被放在新尾端,一直下去，最后即得排序结果
	while(last-first>1){
		pop_heap(first,last--);//每执行一次,操作范围即退缩一格
	}
}

image-20220925171710482

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class RandomAccessIterator>
inline void make_heap(RandomAccessIterator frist,RandomAccessIterator last){
	_make_heap(first,last,value_type(first),distance_type(first));
}

template<class RandomAccessIterator,class T,class Distance>
void _make_heap(RandomAccessIterator first,RandomAccessIterator last,T*,Distance*){
	if(last-first<2)return;//如果长度为0或1,不必重新排列
	//找出第一个需要重排的子树头部,以parent标示出,由于任何叶节点都不需执行
	Distance parent=(len-2)/2;
	
	while(true){
		//重排以parent为首的子树,len是为了让_adjust_heap()判断操作范围
		_adjust_heap(first,parent,len,T(*(first+parent)));
		if(parent==0)return;//走完根节点，结束 
		parent--;
	}
}

priority_queue

image-20220925173243946

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
template<class T,class Sequence=vector<T>,
		class Compare=less<typename Sequence::value_type>>
class priority_queue{
	public:
		typedef typename Sequence::value_type value_type;
		typedef typename Sequence::size_type size_type;
		typedef typename Sequence::reference reference;
		typedef typename Sequence::const_reference const_reference;
	protected:
		Sequence c;//底层容器
		Compare comp;//元素大小比较标准
	public:
		priority_queue():c(){}
		explicit priority_queue(const Compare&x):c(),comp(x){}
		template<class InputIterator>
		priority_queue(InputIterator first,InputIterator last,const Compare&x)
		:c(first,last){
			make_heap(c.begin(),c.end(),comp);
		}
		priority_queue(InputIterator first,InputIterator last)
		:c(first,last){
			make_heap(c.begin(),c.end(),comp);
		}
		bool empty()const{
			return c.empty();
		}
		size_type size()const{
			return c.size();
		}
		const_reference top()const{
			return c.front();
		}
		void push(const value_type&x){
			c.push_back(x);
			push_heap(c.begin(),c.end(),comp);
		}
		void pop(){
			pop_heap(c.begin(),c.end(),comp);
			c.pop_back();
		}
}

slist

slist为单向链表。

slit的节点

image-20220925175234334

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//单向链表的节点基本结构 
struct _slist_node_base{
	_slist_node_base*next;
}
//单向链表的节点结构 
template<class T>
struct _slist_node:public _slist_node_base{
	T data;
}
//已知某一节点，插入新节点于其后
inline _slist_node_base*_slist_make_link(_slist_node_base*prev_node,_slist_node_base*new_node){
	//令new节点的下一节点为prev节点的下一节点
	new_node->next=prev_node->next;
	prev_node->next=new_node;
	return new_node;
}
inline size_t _slist_size(_slist_node_base*node){
	size_t result=0;
	for(;node!=0;node=node->next)
		++result;
	return result;
}

slist迭代器

image-20220925175758091

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
53
54
55
56
57
//单向链表的迭代器的基本结构 
struct _slist_iterator_base{
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef forward_iterator_tag iterator_category;//单向
	
	_slist_node_base*node;//指向节点基本结构 
	
	_slist_iterator_base(_slist_node_base*x):node(x){}
	
	void incr(){
		node=node->next;
	}
	
	void operator==(const _slist_iterator_base&x)const{
		return node==x.node;
	}
	
	void operator!=(const _slist_iterator_base&x)const{
		return node!=x.node;
	}
};
//单向链表迭代器结构 
template<class T,class Ref,class Ptr>
struct _slist_iterator:public _slist_iterator_base{
	typedef _slist_iterator<T,T&,T*> iterator;
	typedef _slist_iterator<T,const T&,const T*>const_iterator;
	typedef _slist_iterator<T,Ref,Ptr>self;
	
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	tyepdef _slist_node<T> list_node;
	
	_slist_iterator(list_node*x):_list_iterator_base(x){}
	_slist_iterator():_slist_iterator_base(0){}
	_slist_iterator(const iterator:x):_slist_iterator_base(x.node){}
	
	reference operator*()const{
		return ((list_node*)node)->data;
	}
	
	pointer operator->()const{
		return &(operator*());
	}
	
	self&operator++(){
		incr();
		return *this;
	}
	
	self operator++(int){
		self temp=*this;
		incr();
		return temp;
	}
}

slist的数据结构

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
template<class T,class Alloc=alloc>
class slist{
	public:
		typedef T value_type;
		typedef value_type* pointer;
		typedef const value_type* const_pointer;
		typedef value_type& reference;
		typedef const value_type& const_reference;
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;
		
		typedef _slist_iterator<T,T&,T*> interator;
		typedef _slist_iterator<T,const T&,const T*>const_iterator;
		
	private:
		typedef _slist_node<T> list_node;
		typedef _slist_node_base list_node_base;
		typedef _slist_iterator_base iterator_base;
		typedef simple_alloc<list_node,Alloc>list_node_allocator;
		
		static list_node*create_node(const value_type&x){
			list_node*node=list_node_allocator::allocate();//配置空间
			construct(&node->data,x);//构造元素
			node->next=0;
			return node;
		}
		
		static void destroy_node(list_node*node){
			destory(&node->data);
			list_node_allocator::deallocate(node);
		}
		
	private:
		list_node_base head; //头部
	
    public:
    	slist(){head.next=0;}
    	~slist(){clear();}
    	
	public:
		iterator begin(){
			return iterator((list_node*)head.next);
		}
		
		iterator end(){
			return iterator(0);
		}
		
		size_type size()const{
			return _slist_size(head.size);
		}
		
		bool empty()const{
			return head.next=0;
		}
		//两个slist互换，只需要将head交换即可
		void swap(slist&L){
			list_node_base*temp=head.next;
			head.next=L.head.next;
			L.head.next=temp;
		}
		
	public:
		//取头部元素
		reference front(){
			return ((list_node*)head.next)->data;
		}
		//从头部插入元素
		void push_front(const value_type&x){
			_slist_make_link(&head,create_node(x));
		}
		
		//从头部取走元素(删除)
		void pop_front(){
			list_node*node=(list_node*)head.next;
			head.next=node->next;
			destroy_node(node);
		}
}

关联式容器

平衡二叉树

普通二叉树与平衡二叉树的区别是，当一些随机输入值插入树中时，普通二叉树会出现极度不平衡的情况，该情况会导致插入、查找 、删除相较于平衡二叉树有较差的效率。而平衡二叉树可以自动调整，使得整个树保持在一个平衡的状态。

image-20220928223207195

AVL tree

AVL tree是一个”加上额外平衡条件”的二查搜索树。其平衡条件的建立是为了确保整棵树的深度为O(logN)。

image-20220928223948012

在插入了节点11之后，灰色节点违反了AVL tree 的平衡条件.只有插入点至根节点路径上的各节点有可能改变平衡状态。因此，只需要调整其中最深的那个节点，便可使得整棵树重新获得平衡。

假设最深节点为X，由于节点最多拥有有两个子节点，而所谓”平衡被破坏”意味着X的左右两棵子树的高度为相相差为2，因此我们可以将情况分为以下四种情况。

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

情况1,4彼此对称 ，称为外侧插入。采用单侧旋转来调整。而情况2,3彼此对称 ，称为内侧插入，采用双旋转操作来调整。

image-20220928224731335

单旋转

image-20220928224912559

我们把键值11插入后，导致左右两边深度不平衡。在18的左边深度为3，而右边的深度为1。故我们需要对该树进行旋转操作。

双旋转

image-20221002181559205

双旋转主要是修正因内侧插入而导致的不平衡。

image-20221002182152029

2-3查找树

为了保证查找树的平衡性，我们需要允许在树中的一个结点保存多个键。

定义：一棵2-3查找树或为一棵空树，由以下结点组成。 2-结点，含有一个键(及其对应的值)和两条链接，左链接指向的2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。3-结点，含有两个键(及其对应的值)和三条链接，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间。右链接指向的2-3树中的键都大于该结点。

image-20221002184127147

一棵完美平衡的2-3查找树中的所有空链接到根结点的距离应该都相同。

将二叉查找树的查找算法一般化我们能直接得到2-3树的查找算法。要判断一个键是否存在树中。我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中。否则，我们根据比较的结果找到指向相应区间的链接，并在其指向的子树中递归地继续查找。如果这是个空链接，查找未命中。

image-20221002185532144

向2-结点中插入新键

image-20221002185840119

向一棵只含有一个3-结点的树中插入新键

image-20221002185924690

image-20221002190243377

2-3树的变化过程

image-20221002190947746

2-3树的构造过程

image-20221002191030021

2-3查找树的删除过程

2-3查找树的删除与AVL tree删除过程差不多，只不过比AVL tree的情况更多而已。我们有如果策略，我们可以在被删除的节点处，找到左侧的最大值，或右侧的最小值用以顶替被删除的值。如

image-20221002195302553

假设我们要删除节点C，则有

image-20221003131949318

在删除C后，我们可以从左子树中寻找最大节点或从右子树中寻找最小节点来替代节点C。即我们有节点树

image-20221003132703768

image-20221003133056578

image-20221003134745313

image-20221003135231952

红黑二叉查找树

红黑二叉查找树其本质是用额外的信息来表示2-3树。即用标准二叉树(完全由2-结构构成)和一些额外的信息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型:红链接将两个2-结点连接起来构成一个3-结点，黑链接则是2-3树中普通链接。即我们将3-结点表示为由一条左斜的红色链接(两个2-结点其中之一是另一个左子结点)相连的两个结点。

image-20221002192302522

红黑树的另一种定义

红黑树的另一种定义是含有红黑链接并满足以下条件的二叉查找树：

  • 红链接均为左链接
  • 没有任何一个结点同时和两条红链接相连
  • 该树是完美黑色平衡的，即任意空链接到根结点的路径数量相同

image-20221002192641135

颜色表示

每个结点都只会有一条指向自己链接(从它的父结点指向它)，我们将链接的颜色保存在给结点的Node数据类型的布尔变量中。如果指向它的链接是红色的，那么该变量为true，黑色为false。则我们有结构定义

1
2
3
4
5
6
7
class Node{
 Key key;//键
 Value val;//相关联的值
 Node Left,Right;//左右子树
 int N;//这棵树的总结点数
 boolean color;//其父结点指向它链接的颜色
}

image-20221003140855674

旋转

我们在实现某些操作中可能会出现红色右链接或都两条连续的红色链接，但在操作完成前这些情况都会被小心地旋转并修复。旋转操作会改变红链接的指向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//左旋转
Node rotateLeft(Node h){
	Node x=h.right;//保存右子节点
	h.right=x.left;
	x.left=h;
	x.color=h.color;
	h.color=RED;
	x.N=h.N;
	h.N=1+size(h.left)+size(h.right);
	return x;
}
//右旋转
Node rotateRight(Node h){
	Node x=h.left;
	h.left=x.right;
	x.right=h;
	x.color=h.color;
	h.color=RED;
	x.N=h.N;
	h.N=1+size(h.left)+size(h.right);
	return x;
}

image-20221003142618496

向树底部的2-结点插入新建

image-20221003143015154

向一棵双键树(即一个3-结点)中插入新键

可分为三种子情况：新建小于树中的两个键，在两者之间，或是大于树中的两个键。每种情况都会产生一个同时连接到两条红链接的结点，我们的目标就是修正这一点。

  • 当新键大于原树中的两个键，因此会被连接到3-结点的左路链接。此时树是平衡的，根结点为中间大小的键。它有两条红链接分别和较小和较大的结点相连。如果我们将两条链接的颜色都由红变黑，那么我们会得到一棵由三个结点组成，高为2的平衡树。见下图。
  • 如果新键小于原树中的两个键，它会被链接到最左边的空链接，会产生两条连续的红链接，此时我们只需要将上层的红链接右旋转即可得到第一种情况。
  • 如果新键介于原树中的两个键之间，这又会产生两条连续的红链接，一条红色左链接接一条红色右链接，只需要将下层的红链接左旋转即可得到第二种情况。

image-20221003144229126

颜色转换

我们使用一个方法filpColors()来转换一个结点的两个红色子结点的颜色。除了将子结点的颜色由红变黑之外，还需要将父结点的颜色由黑变红。

1
2
3
4
5
void filpColors(Node h){
	h.color=RED;
	h.left.color=BLACK;
	h.right.color=BLACK;
}

注：根结点总是黑色的

image-20221003145356460

向树底部的3-结点插入新键

image-20221003150235184

在沿着插入点到根结点的路径向上移动时在所经过每个结点中顺序完成以下操作，我们能完成插入操作。

  • 如果右子结点是红色的而左子结点是黑色的，进行左旋转。
  • 如果左子结点是红色的且它的左子结点也是红色的，进行右旋转。
  • 如果左右子结点均为红色，进行颜色转换。

image-20221003150514433

插入实现

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
public class RedBlackBST<Key extends Comparable<Key>,Value>{
	private Node root;
	private class Node;
	
	private boolean isRed(Node h);
	private Node rotateLeft(Node h);
	private Node rotateRight(Node h);
	private void filpColors(Node h);
	
	private int size();
	
	public void put(Key key,Value val){
		//查找key,找到则更新其值，否则为它新建一个结点 
		root=put(root,key,val);
		root.color=Black;
	}
	
	public Node put(Node h,Key key,Value val){
		if(h==null){ //新建结点,父节点用红链接相连
			return new Node(key,val,1,RED);
		}
		int cmp=key.compareTo(h.key);
		if(cmp<0)
			h.left=put(h.left,key,val);
		else if(cmp>0)
			h.right=put(h.right,key,val);
		else 
			h.val=val;
		
		if(isRed(h.right)&&!isRed(h.left))//右节点为红链接
			h=rotateLeft(h);
		if(isRed(h.left)&&isRed(h.left.left)){//左节点与左节点的左节点都为红链接
			h=rotateRight(h);
		}
		if(isRed(h.left)&&isRed(h.right))
			flipColors(h);
		h.N=size(h.left)+size(h.right)+1;
		return h;
	}
}

image-20221003152248525

自顶向下的2-3-4树

2-3-4树的插入算法，2-3-4树中允许存在我们以前见过的4-结点。它的插入算法沿查找路径向下进行变换是为了保证当前结点不是4-结点(这样树底才有空间来插入新的键)，沿查找路径向上进行变换是为了将之前创建的4-结点配平。

  • 如果根结点是4-结点，则将它分解成三个2-结点，使得树高加1。
  • 在向下查找的过程中，如果遇到一个父结点为2-结点的4-结点，将4-结点分解为两个2-结点并将中间键传递给它的父结点，使得父结点变成一个3-结点。
  • 在向下查找的过程中，如果遇到一个父结点为3-结点的4-结点，我们将4-结点分解为两个2-结点并将中间键传递给它的父结点，使得父结点变成一个4-结点。

注：该算法在查找要删除的值的过程进行变换，使得只保留2-和3-结点，并且要删除的值必在一棵2-结点中(不包括父结点)，这样做可以删除值之后能较好进行插入。

image-20221003155011678

在实现这个算法，我们需要

  • 将4-结点表示为由三个2-结点组成的一棵平衡的子树，根结点和两个子结点都用红链接相连
  • 在向下的过程中分解所有4-结点并进行颜色转换
  • 和插入操作一样，在向上的过程中用旋转将4-结点进行配平
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
//实现
public void put(Key key,Value val){
		//查找key,找到则更新其值，否则为它新建一个结点 
		root=put(root,key,val);
		root.color=Black;
	}
	
	public Node put(Node h,Key key,Value val){
		if(h==null){ //新建结点,父节点用红链接相连
			return new Node(key,val,1,RED);
		}
		if(isRed(h.left)&&isRed(h.right))
			flipColors(h);
		int cmp=key.compareTo(h.key);
		if(cmp<0)
			h.left=put(h.left,key,val);
		else if(cmp>0)
			h.right=put(h.right,key,val);
		else 
			h.val=val;
		
		if(isRed(h.right)&&!isRed(h.left))//右节点为红链接
			h=rotateLeft(h);
		if(isRed(h.left)&&isRed(h.left.left)){//左节点与左节点的左节点都为红链接
			h=rotateRight(h);
		}
	
		h.N=size(h.left)+size(h.right)+1;
		return h;
	}

删除最小键

我们注意到从树底部的3-结点中删除键是很简单的，但是2-结点则不然。从2-结点中删除一个键会留下一个空结点，一般我们会将它替换成一个空链接，我们沿着左链接如下进行变换，确保当前结点不是2-结点(可能是3-结点，也可能是4-结点)。

首先根结点可能有两种情况(见下图)。

  • 如果根是2-结点且它的两个子结点都是2-结点，我们可以直接将这三个结点变成一个4-结点。
  • 如果根为2-结点且左子结点是2-结点，但右子结点不2-结点，则我们需要从右子结点中借一个结点过来。

在沿着左链接如下的过程中，需要保证以下情况之一成立(见下图)。

  • 如果当前结点的左子结点不是2-结点，完成。
  • 如果当前结点的左子结点是2-结点而它亲兄弟结点不是2-结点，将左子结点的兄弟结点中的一个键移动到左子结点中。
  • 如果当前结点的左子结点和它的亲兄弟结点都是2-结点，将左子结点、父结点中的最小键和左子结点最近的兄弟结点合并为一个4-结点，使父结点由3-结点变为2-结点或由4-结点变为3-结点

image-20221003173237428

在遍历的过程中执行这个过程，最后能够得到一个含有最小键的3-结点或4-结点，然后我们可以直接从中将其删除，将3-结点变为2-结点，或者将4-结点变为3-结点，然后再回头向上分解所有临时的4-结点。

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
private Node moveRedLeft(Node h){
	//假设结点h为红色,h.left和h.left.left都是黑色
	//将h.left或h.left的子结点之一变红
	flipColors(h);//如果结点h为红色则将父结点设为黑，两节点设为红，即合并成一个4-结点
	if(isRed(h.right.left)){//即从右子节点中借一个节点过来
		h.right=rotateRight(h.right);//从右旋转
		h=rotateLeft(h);//左旋转
	}
	return h;
}
public void deleteMin(){
	if(!isRed(root.left)&&!isRed(root.right)){//左右节点皆为2-结点，合并为4-结点
		root.color=RED;
	}
	root=deleteMin(root);
	if(!isEmpty())
		root.color=BLACK;
}
private Node deleteMin(Node h){
	if(h.left==null)
		return null;
	if(!isRed(h.left)&&!isRed(h.left.left)){
		h=moveRedLeft(h);
	}
	h.left=deleteMin(h.left);
	return balance(h);//向上进行合并
}
private Node balance(Node h){
	if(isRed(h.right))
		h=rotateLeft(h);
	if(isRed(h.right)&&!isRed(h.left))//右节点为红链接
		h=rotateLeft(h);
	if(isRed(h.left)&&isRed(h.left.left)){//左节点与左节点的左节点都为红链接
		h=rotateRight(h);
	}
	if(isRed(h.left)&&isRed(h.right))
		flipColors(h);
	h.N=size(h.left)+size(h.right)+1;
	return h;
}

删除最大键

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
private Node moveRedRight(Node h){
	//假设结点h为红色,h.right和h.right.left都是黑色
	//将h.right或h.right的子结点之一变红
	filpColors(h);
	
	if(!isRed(h.left.left)){
		h=rotateRight(h);
	}
	return h;
}
public void deleteMax(){
	if(!isRed(root.left)&&!isRed(root.right)){
		root.color=RED;
	}
	root=deleteMax(root);
	if(!isEmpty())
		root.color=BLACK;
}
public Node deleteMax(){
	if(!isRed(root.left)&&!isRed(root.right))
		root.color=RED;
	root=deleteMax(root);
	if(!isEmpty())
		root.color=BLACK;
}
private Node deleteMax(Node h){
	if(isRed(h.left))
		h=rotateRight(h);
	if(h.right==null)
		return null;
	if(!isRed(h.right)&&!isRed(h.right.left))
		h=moveRedRight(h);
	h.right=deleteMax(h.right);
	return blance(h);
}

删除操作

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
public void delete(Key key){
	if(!isRed(root.left)&&!isRed(root.right))
		root.color=RED;
	root=delete(root,key);
	if(!isEmpty())
		root.color=BLACK;
}
private Node delete(Node h,Key key){
	if(key.compareTo(h.key)<0){
		if(!isRed(h.left)&&!isRed(h.left.left))
			h=moveRedLeft(h);
		h.left=delete(h.left.key);
	}else{
		if(isRed(h.left))
			h=rotateRight(h);
		if(key.compareTo(h.key)==0&&(h.right==null)){
			return null;
		}
		if(!isRed(h.right)&&!isRed(h.right.left)){
			h=moveRedRight(h);
		}
		if(key.compareTo(h.key)==0){
			h.val=get(h.right,min(h.right).key);
			h.key=min(h.right).key;
			h.right=deleteMin(h.right);
		}
		else
			h.right=delete(h.right,key);
	}
	return balance(h);
}

RB-Tree的节点设计

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
typedef bool _rb_tree_color_type;
typedef _rb_tree_color_type _rb_tree_red=false;//红色为0
typedef _rb_tree_color_type _rb_tree_black=true;//黑色为1

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;//RB树的许多操作,必须知道父节点
	base_ptr left;//指向左节点
	base_ptr right;//指向右节点
	
	static base_ptr minimum(base_ptr x){
		while(x->left!=0) x=x->left; //一直向左走，就会找到最小值
		return x; 
	}
	
	static base_ptr maximum(base_ptr x){
		while(x->right!=0) x=x->right;
		return x;
	}
};
template<class Value>
struct _rb_tree_node:public _rb_tree_node_base{
	typedef _rb_tree_node<Value>* link_type;
	Value value_field;//节点值
}

image-20221004161812403

image-20221004162148787

RB-tree的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class Key,class Value,class KeyOfValue,class Compare,class Alloc=alloc>
class rb_tree{
protected:
	size_type node_count;//追踪记录树的大小(即节点数量)
    link_type header;
    Compare key_compare;//节点的键值大小比较准则
	typedef simple_alloc<rb_tree_node,Alloc> rb_tree_node_allocator;
	link_type get_node(){ return rb_tree_node_allocator::allocate();}
	void init(){
		header=get_node();//产生一个节点空间,使header指向它
		color(header)=_rb_tree_red;//令header为红色
		root()=0;
		leftMost()=header;//令左子节点为自已
		rightMost()=header;//令右子节点为自己
	}
}

set

set的特性是所有元素都会根据元素的键值自动被排序。set的元素不像map那样可以同时拥有有实值(value)和键值(key)。set元素的键值就是实值，实值就是键值，set不允许两个元素有相同的键值。

我们无法通过set的迭代器去改变set的元素。因为set::iterator 被 定义为底层RB-tree的const_iterator。

由于RB-tree是一种平衡二叉树，自动排序效果很不错，所以标准的STL set即以RB-Tree的为底层机制。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
template<class Key,class Compare=less<Key>,class Alloc=alloc>
class set{
	public:
		typedef Key key_type;
		typedef Key value_type;
		//以下key_compare和value_compare使用同一比较函数
		typedef Compare key_compare;
		typedef Compare value_compare;
	private:
		/*
			template<class T>
			struct identity:public unary_function<T,T>{
				const T& operator()(const T&x)const{
					return x;
				}
			}
		*/
		typedef rb_tree<key_type,value_type,identity<value_type>,key_compare,Alloc>rep_type;
		rep_type t;//采用红黑树来表现set
	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_iteraotr 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;
		
		set():t(Compare()){}
		explicit set(const Compare&comp):t(comp){}
		
		template<class InputIterator>
		set(InputIterator first,InputIterator last):t(Compare()){
			t.insert_unique(first,last);
		}
		
		template<class InputIterator>
		set(InputIterator first,InputIterator last,const Compare&comp):t(comp){
			t.insert_unique(first,last);
		}
		
		set<const set<Key,Compare,Alloc>&x>:t(x.t){}
		set<Key,Compare,Alloc>&operator=(const set<Key,Compare,Alloc>&x){
			t=x.t;
			return *this;
		}
		
		key_compare key_comp()const {retur 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<Key,Compare,Alloc>&x) {t.swap(x.t); }
		
		typedef pair<iterator,bool>pair_iterator_bool;
		pair_iterator_bool insert(const value_type&x){
			pair<typename rep_type::iterator,bool>p=t.insert_unique(x);
			return pair<iterator,bool>(p.first,p.second);
		}
		
		size_type erase(const key_type&x){
			return x.erase(x);
		}
		
		size_type count(const key_type&x)const{
			return t.count(x);
		}
}

set底层运用rb-tree进行数据的插入、删除和查找 。

map

map的特性是,所有元素都会根据元素的键值自动被排序。map的所有元素都是pair，同时拥有实值和键值,pair的第一元素被视为键值，第二元素被视为实值。Map不允许两个元素拥有相同的键值。

1
2
3
4
5
6
7
8
9
10
11
//pair定义
template<class T1,class T2>
struct pair{
	typedef T1 first_type;
	typedef T2 second_type;
	
	T1 first;
	T2 second;
	piar():first(T1()),second(T2()){}
	pair(const T1&a,const T2&b):first(a),second(b){}
}

image-20221004173222962

image-20221004173404834

multiSet

image-20221004173639998

multiMap

image-20221004173718338

hashtable(哈希表)

hash table可提供对任何有名项的存取操作和删除操作。由于操作对象是有名项，所以hash table也可被视为一个字典结构，这种结构的用意在于提供常数时间之基本操作。

线性探测

负载系数 ，指元素个数除以表格大小。负载系统永远在0-1之间——除非采用开链策略。

若当hash function计算出某个元素的插入位置，而该位置上空间已不再可用时，我们需要循序往下一一寻找(如果到达尾端，就绕到头部继续寻找)，直到找到一个可用空间为止。只要表格足够大，总是能够找到一个可以插入的空间。而元素的删除，必须要采用惰性删除，也就只标记删除记号，实际删除操作则待表格重新整理时再进行——这是因为hash table中的每一个元素不仅表述它自己，也关系到其它元素的排列。

image-20221004191752187

二次探测

二次探测主要用来解决线性探测频繁碰撞的问题。其方程为

如果hash function 计算出新元素的位置为H，而该位置实际上已被使用，那么我们依序尝试$H+1^2$，

，。

image-20221004192243391

如果我们假设表格大小为质数，而且永远保持负载系统在0.5以下(也就是超过0.5就重新配置并重新整理表格)，那么就可确实每插入一个新元素所需要探测次数不多于2。

二次探测可以消除主集团(频率碰撞)，即可能造成次集团：两个元素经hash funciton计算出来的位置若相同，则插入时所探测的位置也相同，形成某种浪费。

开链

开链是在每一个表格元素中维护一个list：hash function 为我们分配某一个List，然后我们在那个List身上执行元素的插入、搜寻、删除等操作。

hash table的桶子与节点

image-20221004193023321

1
2
3
4
5
6
//hash table的定义
template<class Value>
struct _hashtable_node{
	_hashtable_node*next;
	Value value;
}

image-20221004193140195

hashtable的迭代器

image-20221004193707144

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class V,class K,class HF,class ExK,class EqK,class A>
_hashtable_iterator<V,K,HF,ExK,EqK,A>&
_hashtable_iterator<V,K,HF,ExK,EqK,A>::operator++(){
	const node*old=cur;
	cur=cur->next;
	if(!cur){//当前桶子只有一个元素
		//根据元素值，定义出下一个bucket，其起头处就是我们的目的地
		size_type bucket=ht->bkt_num(old->val);
		while(!cur&&++bucket<ht->buckets.size())
			cur=ht->buckets[bucket];
	}
	return *this;
}

hashtable的数据结构

image-20221004194834846

image-20221004195404395

hashtable的构造与内存管理

image-20221004195613720

插入操作(insert)与表格重整(resize)

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
//插入元素，不允许重复
pair<iterator,bool>insert_unique(const value_type&obj){
	resize(num_elements+1);//判断是否需要重建表格，如需要就扩充
	return insert_unique_noresize(obj);
}

//以下函数判断是否需要重建表格,如果不需要，立刻回返，如果需要，就手动
template<class V,class K,class HF,class Ex,class Eq,class A>
void hashtable<V,K,HF,Ex,Eq,A>::resize(size_type num_elements_hint){
	//以下，“表格重建与否”的判断原则是拿元素个数(把新增元素计入后)和
	//bucket vector的大小来比，如果前者大于后者，就重建表格
	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*,A>temp(n,(node*)0);//设立新的buckets
			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);
					//令旧bucket指向其所应之串行的下一个节点
					buckets[bucket]=first->next;
					//将当前节点插入到新bucket内，成为其对应串行的第一个节点
					first->next=temp[new_bucket];
					temp[new_bucket]=first;
					//处理下一个节点
					first=buckets[bucket];
				}
			}
			bucket.swap(temp);
		}
	}
}

image-20221004202034325

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//不需重建表格的情况下插入新节点，键值不允许重复
template<class V,class K,class HF,class Ex,class Eq,class A>
pair<typename hashTable<V,K,HF,Ex,Eq,A>::iterator,bool>
hashtable<V,K,HF,Ex,Eq,A>::insert_unique_noresize(const value_type&obj){
	const size_type n=bkt_num(obj);
	node*first=buckets[n];//令first指向bucket对应之串行头部
	
	//如果buckets[n]已被占用，此时first将不为，于是进行以下循环
	//走过bucket所对应的链表
	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*temp=new_node(obj);//产生新节点
	temp->next=first;
	buckets[n]=temp;//令节点成为链表的第一节点
	++num_elements;
	return pair<iterator,bool>(iterator(temp,this),true);
}

image-20221004203111277

image-20221004203129755

判知元素的落脚处

image-20221004203249845

复制和整体删除

image-20221004203338447

image-20221004203628047

image-20221004203645314

image-20221004203707502

仿函数

仿函数是一个“行为类似函数”的对象

image-20221005154615702

image-20221005154647302

image-20221005154656216

可配接的关系

若仿函数要融入STL中，则需要有配接能力。

unary_function

unary_faction 用来呈现一元函数的参数型别和回返值型别 。

1
2
3
4
5
template<class Arg,class Result>
struct unary_function{
	typedef Arg argument_type;
	typedef Result result_type;
}

一旦某个仿函数继承了unary_function，其用户便可以取得这样的仿函数的参数型别，并以相同手法取得其回返值型别。

1
2
3
4
5
6
template<class T>
struct negate:public unary_function<T,T>{
	T operator()(const T&x)const{
		return -x;
	}
}

binary_function

binary_function用来呈现二元函数的第一参数型别、第二参数型别以及返回值型别。

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class Arg1,class Arg2,class Result>
struct binary_function{
	typedef Arg1 first_argument_type;
	typedef Arg2 second_argument_type;
	typedef Result result_type;
};

template<class T>
struct plus:public binary_function<T,T,T>{
	T operator()(const T&x,const T&y)const{
		return x+y;
	}
}

算术类仿函数

image-20221005155827733

image-20221005160216201

关系运算类仿函数

image-20221005160321422

逻辑类仿函数

image-20221005160412084