【STL】Deque – TK-Xiong`s Blog

一个双向开口的逻辑上连续线性空间。

Vector 和 Deque 一般是可以放一起讨论的，但是实际上 Deque 的实现复杂比 Vector 难了…额不以万里计…

Deque 在头部和尾部都可以做到常数时间的插入和删除操作。

当然 Vector 也可以在头部进行插入和删除操作，但是这个速度嘛…自己体会。

Deque 相对于 Vector 来说，是没有容量(capacity)的概念的，因为它是由个数动态增长的分段空间组合而成的（这些空间在逻辑上是连续的），所以不会像Vector一样需要进行配置复制释放来完成增长。

Deque也提供了 Random Access Iterator(随机存取迭代器)，但是它的迭代器并不是普通指针，其复杂度相比Vector来说，简直上天~恩…上天。

因此，除非必要的操作，我们应尽可能选用 Vector 而不是 Deque。

如果我们要对 Deque 进行排序操作，就先将 Deque 复制到一个 Vector 中，对 Vector 进行排序后，再复制回 Deque.

Deque的中控器：

Deque 在逻辑上来看是一段连续线性空间，实际上(物理上)则是由一段段的定量连续空间构成。

如果有必要在Deque的首部或者尾部增加一段新的空间的话，那就配置一段定量连续空间，然后串接在 Deque 的首部或者尾部即可。

Deque 采用了一小块所谓的map(这里指的并不是STL的容器，而是一个二级指针)作为主控，这里的map是一小块线性连续空间，每一个元素也都是一个指针，指向另一段连续线性空间的头部，我们称这段空间为缓冲区。这些缓冲区就是Deque的存储空间主体。

STL一般是允许指定缓冲区的大小的，默认0则表示用512byte大小的缓冲区。

template <class T, class Alloc = alloc , size_t BufSiz = 0>
class deque
{
public:
	typedef T value_type;
	typedef T* pointer;
	//...
protected:
	typedef pointer* map_pointer;	//一个指向元素的指针的指针
	
protected:
	map_pointer map;	//指向实际map，其内每个元素都是一个指针，指向一块缓冲区，所以map是二级指针
	size_type map_size;	//map内可容纳指针数量 
	//... 
	 
}

template <class T, class Alloc = alloc , size_t BufSiz = 0>

class deque

{

public:

typedef T value_type;

typedef T* pointer;

//...

protected:

typedef pointer* map_pointer; //一个指向元素的指针的指针

protected:

map_pointer map; //指向实际map，其内每个元素都是一个指针，指向一块缓冲区，所以map是二级指针

size_type map_size; //map内可容纳指针数量

//...

}

样子嘛，还是上图把，这样比较明显：

Deque-map

Deque的大致情况我们了解了，接来下我们来我们来看看迭代器的设计。

Deque的迭代器：

我们知道，Deque是一个分段的逻辑连续空间，那么如何让这个空间看起来是连续的呢，就得靠与外界的接口迭代器来实现了。

所以其真正的任务是 operator++ 与 operator– 的设计。

那么Deque的迭代器应该具备什么能力呢，首先它要指出分段连续空间的位置(即缓冲区的位置)，然后要能判断自己是否位于缓冲区的边缘，然后又要能够正确跳到下一个或者上一个缓冲区，于是必须掌控map。

采用了下面的实现方法：

template <class T, class Ref, class Ptr, size_t BufSiz>
struct __deque_iteraotr
{
	typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
	typedef __deque_iteraotr<T, const T&, const T*, BufSiz> const_iteraotr;
	
	static size_t buffer_size()
	{
		return __deque_buf_size(BufSiz, 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* first;		//缓冲区头部 
	T* last;		//缓冲区尾部 
	map_pointer node; 	//管控中心 

	//...
};

inline size_t __deque_buf_size(size_t n, siez_t sz)
{
	return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));
}

template <class T, class Ref, class Ptr, size_t BufSiz>

struct __deque_iteraotr

{

typedef __deque_iterator<T, T&, T*, BufSiz> iterator;

typedef __deque_iteraotr<T, const T&, const T*, BufSiz> const_iteraotr;

static size_t buffer_size()

{

return __deque_buf_size(BufSiz, 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* first; //缓冲区头部

T* last; //缓冲区尾部

map_pointer node; //管控中心

//...

};

inline size_t __deque_buf_size(size_t n, siez_t sz)

{

return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));

}

下图可以很好地表示deque的中控器，迭代器，缓冲区之间的关系：

Deque-Iterator

下面是 Deque 迭代器的几个关键行为。由于迭代器内对各种指针的运算都进行了重载操作，所以各种指针运算如加、减、前进、后退都不能直观视之。

其中重点是：当行进到迭代器边缘时，要调用 set_node函数跳一个缓冲区。

void set_node(map_pointer new_node)
{
	node = new_node;
	first = *new_node;
	last = first + difference_type(buffer_size());
}

void set_node(map_pointer new_node)

{

node = new_node;

first = *new_node;

last = first + difference_type(buffer_size());

}

以下各个运算子的重载，则是Deque Iterator 成功运作的关键：

reference operator*() const
{
	return *cur;
}

pointer operator->() const
{
	return &(operator*());
}

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;					//1.跳至下一个元素 
	if(cur == last)			//2.如果到了尾端 
	{
		set_node(node + 1);	//3.切换下一缓冲区 
		cur = first;		//4.切换为第一个元素 
	}
	return *this;
}

self operator++(int)
{
	self tmp = *this;
	++*this;
	return tmp;
}

self& operator--()
{
	if(cur == first)		//1.如果在缓冲区头部 
	{
		set_node(node -1);	//2.切换上一缓冲区 
		cur = last;			//3.切换到缓冲区尾端 
	}
	--cur;					//4.跳至上一元素，即最后一个元素 
	return *this;
} 

self operator--(int)
{
	self tmp = *this;
	--*this;
	return tmp;
}

//实现随机存取。迭代器可以直接跳跃n个距离 
self& operator+=(difference_type n)
{
	difference_type offset = n + (cur - first);
	if(offset >= 0 && offset < difference_type(buffer_size())) 
	{	//如果在同一缓冲区内 
		cur += n;
	}
	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;
}

self operator+(difference_type n) const
{
	self tmp = *this;
	return tmp += n;
}

self& operator -=(difference_type n)
{	//精妙！ 
	return *this += -n;
}

self operator- (difference_type n) const
{
	self tmp = *this;
	return tmp -= n;
}

//实现随机存取，迭代器可以直接跳跃n个距离  
reference operator[](difference_type n) const
{
	return *(*this + n);
}

bool operator==(const self& x) const
{
	return cur == x.cur;
}

bool operator!=(const self& x) const
{
	return !(*this == x);
}

bool operator<(const self& x) const
{
	return (node == x.node) ? cur < x.cur : node < x.node;
}

100

101

102

103

104

105

106

107

108

109

110

111

reference operator*() const

{

return *cur;

}

pointer operator->() const

{

return &(operator*());

}

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; //1.跳至下一个元素

if(cur == last) //2.如果到了尾端

{

set_node(node + 1); //3.切换下一缓冲区

cur = first; //4.切换为第一个元素

}

return *this;

}

self operator++(int)

{

self tmp = *this;

++*this;

return tmp;

}

self& operator--()

{

if(cur == first) //1.如果在缓冲区头部

{

set_node(node -1); //2.切换上一缓冲区

cur = last; //3.切换到缓冲区尾端

}

--cur; //4.跳至上一元素，即最后一个元素

return *this;

}

self operator--(int)

{

self tmp = *this;

--*this;

return tmp;

}

//实现随机存取。迭代器可以直接跳跃n个距离

self& operator+=(difference_type n)

{

difference_type offset = n + (cur - first);

if(offset >= 0 && offset < difference_type(buffer_size()))

{ //如果在同一缓冲区内

cur += n;

}

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;

}

self operator+(difference_type n) const

{

self tmp = *this;

return tmp += n;

}

self& operator -=(difference_type n)

{ //精妙！

return *this += -n;

}

self operator- (difference_type n) const

{

self tmp = *this;

return tmp -= n;

}

//实现随机存取，迭代器可以直接跳跃n个距离

reference operator[](difference_type n) const

{

return *(*this + n);

}

bool operator==(const self& x) const

{

return cur == x.cur;

}

bool operator!=(const self& x) const

{

return !(*this == x);

}

bool operator<(const self& x) const

{

return (node == x.node) ? cur < x.cur : node < x.node;

}

Deque的数据结构：

除了要维护map之外，也维护 start，finish两个迭代器，分别指向缓冲区第一个元素和最后一个元素的下一位置。

除此之外，还要知道map的大小。（一旦map大小不足则需要重新配置）

template <class T, class Alloc = alloc, size_t BufSiz = 0>
class deque
{
public:
	typedef T value_type;
	typedef value_type* pointer;
	typedef size_t size_type; 
	//...
public:
	typedef __deque_iterator<T, T&, T*, BufSiz> iterator;

protected:
	typedef pointer* map_pointer;	//二级指针
	
protected:
	iterator start;		//第一个节点 
	iterator finish;	//最后一个结点 
	map_pointer map;	//指向实际map，其内每个元素都是一个指针，指向一块缓冲区
	size_type map_size;	//map内可容纳指针数量 
	//... 
}

template <class T, class Alloc = alloc, size_t BufSiz = 0>

class deque

{

public:

typedef T value_type;

typedef value_type* pointer;

typedef size_t size_type;

//...

public:

typedef __deque_iterator<T, T&, T*, BufSiz> iterator;

protected:

typedef pointer* map_pointer; //二级指针

protected:

iterator start; //第一个节点

iterator finish; //最后一个结点

map_pointer map; //指向实际map，其内每个元素都是一个指针，指向一块缓冲区

size_type map_size; //map内可容纳指针数量

//...

}

这样，有了上述结构，以下机能便能轻易完成：

public:
	iterator begin()
	{
		return start;
	} 
	iterator end()
	{
		return finish;
	}
	
	reference operator[](size_type n)
	{//调用 __deque_iterator<>::operator[]
		return start[difference_type(n)];	 
	}
	
	reference front()
	{
		return *start; 
	}
	
	reference back()
	{
		iterator tmp = finish;
		-- tmp;
		return *tmp;
	}
	
	size_type size() const
	{
		return finish - start;
	}
	
	size_type max_size() const
	{
		return size_type(-1);
	}
	
	bool empty() const
	{
		return finish == start;
	}

public:

iterator begin()

{

return start;

}

iterator end()

{

return finish;

}

reference operator[](size_type n)

{//调用 __deque_iterator<>::operator[]

return start[difference_type(n)];

}

reference front()

{

return *start;

}

reference back()

{

iterator tmp = finish;

-- tmp;

return *tmp;

}

size_type size() const

{

return finish - start;

}

size_type max_size() const

{

return size_type(-1);

}

bool empty() const

{

return finish == start;

}

deque的构造与内存管理：

来来来，看代码…反正每次侯捷大神都这样…

#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	deque<int> ideq(20,9);
	//Size = 20 
	cout << "Size = " << ideq.size() << endl;
	
	for(int i=0;i<ideq.size();i++)
		ideq[i] = i;
	
	//0 1 2 3 4 5 ... 19
	for(int i=0;i<ideq.size();i++)
		cout << ideq[i] << " ";
	cout << endl;
	
	for(int i=0;i<3;i++)
		ideq.push_back(i);
	
	//0 1 2 3 ... 19 0 1 2 
	for(int i=0;i<ideq.size();i++)
		cout << ideq[i] << " ";
	cout << endl;
	//Size = 23
	cout << "Size = " << ideq.size() << endl;
	
	ideq.push_back(3);
	//0 1 2 3 ... 19 0 1 2 3 
	for(int i=0;i<ideq.size();i++)
		cout << ideq[i] << " ";
	cout << endl;
	//Size = 24
	cout << "Size = " << ideq.size() << endl;
	
	ideq.push_front(99);
	//99 0 1 2 3 ... 19 0 1 2 3 
	for(int i=0;i<ideq.size();i++)
		cout << ideq[i] << " ";
	cout << endl;
	//Size = 25
	cout << "Size = " << ideq.size() << endl;
	
	ideq.push_front(98);
	ideq.push_front(97);
	//97 98 99 0 1 2 3 ... 19 0 1 2 3 
	for(int i=0;i<ideq.size();i++)
		cout << ideq[i] << " ";
	cout << endl;
	//Size = 27
	cout << "Size = " << ideq.size() << endl;
	
	deque<int>::iterator ite;
	ite = find(ideq.begin(),ideq.end(),99);
	if(ite!=ideq.end())
	{
		//99
		cout << *ite << endl;
		//cout << *(ite.cur) << endl;
		//99
		cout << *(ite._M_cur) << endl;
	}
}

#include <deque>

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{

deque<int> ideq(20,9);

//Size = 20

cout << "Size = " << ideq.size() << endl;

for(int i=0;i<ideq.size();i++)

ideq[i] = i;

//0 1 2 3 4 5 ... 19

for(int i=0;i<ideq.size();i++)

cout << ideq[i] << " ";

cout << endl;

for(int i=0;i<3;i++)

ideq.push_back(i);

//0 1 2 3 ... 19 0 1 2

for(int i=0;i<ideq.size();i++)

cout << ideq[i] << " ";

cout << endl;

//Size = 23

cout << "Size = " << ideq.size() << endl;

ideq.push_back(3);

//0 1 2 3 ... 19 0 1 2 3

for(int i=0;i<ideq.size();i++)

cout << ideq[i] << " ";

cout << endl;

//Size = 24

cout << "Size = " << ideq.size() << endl;

ideq.push_front(99);

//99 0 1 2 3 ... 19 0 1 2 3

for(int i=0;i<ideq.size();i++)

cout << ideq[i] << " ";

cout << endl;

//Size = 25

cout << "Size = " << ideq.size() << endl;

ideq.push_front(98);

ideq.push_front(97);

//97 98 99 0 1 2 3 ... 19 0 1 2 3

for(int i=0;i<ideq.size();i++)

cout << ideq[i] << " ";

cout << endl;

//Size = 27

cout << "Size = " << ideq.size() << endl;

deque<int>::iterator ite;

ite = find(ideq.begin(),ideq.end(),99);

if(ite!=ideq.end())

{

//99

cout << *ite << endl;

//cout << *(ite.cur) << endl;

//99

cout << *(ite._M_cur) << endl;

}

哔~…太复杂了…恩不爆粗…2016.7.19 记于此…留待后观。

【STL】Deque

Tagged on: STL