私房STL之deque

一句话deque:deque是双端队列,它的空间构造并非一个vector式的长数组,而是“分段存储,整体维护”的方式;STL允许在deque中任意位置操作元素(删除添加)(这超出了deque的概念,最原始的deque将元素操作限定在队列两端),允许遍历,允许随机访问(这是假象);我们将看到,deque将是STL中stack和queue的幕后功臣,对deque做适当的修正,便可以实现stack和queue。

bug,deque_in_real

deque的迭代器

deque的迭代器与一般的迭代器不同,并不是vector或者list的普通指针式迭代器,有必要写下。

......
typedef T** map_pointer;
T* cur;//指向当前元素
T* first;//指向缓冲区头
T* last;//指向缓冲区尾巴
map_pointer node;//二级指针,指向缓冲区地址表中的位置
......

实现的复杂度可见一斑。正是因为deque复杂的空间结构,其迭代器也想跟着复杂晦涩。于是很容易令人产生异或!

为什么要用这么复杂的空间结构

同学A会疑问:“为什么不直接使用似vector抑或array一个长的数组?这样实现起来简单,而且迭代器也不会像”这个问题很容易被解决,想想:array就不用解释了,因为它是静态的空间,不支持拓展;另外,回想一下,vector在做空间拓展的时候,是如何劳神伤肺?!vector是依从“重新配置,复制,释放”规则,这样的代价是很划不来的。所以宁愿实现复杂的迭代器,来换取宝贵的计算机资源。

那么deque在做空间拓展的时候是如何做的呢?

如果缓冲区中还有备用的空间,那么直接使用备用的空间;否则,另外配置一个缓冲区,将其信息记录到缓冲区地址表里;更有甚者,如果缓冲区地址表都不够的时候,缓冲区地址表也要严格依从“重新配置,复制,释放”规则,但相比对“重新配置,复制,释放”规则宗教式追狂热的vector而言,效率高很多。

deque的创建与遍历

STL中deque有提供多种版本的构造函数,一把使用缺省构造函数。

......
deque<int> id;
......

同样,虽迭代器庞杂,但使用游刃有余,和其他的容器保持一致;并且,迭代器有重载“[]”运算符,所以支持“随机访问”(其实这是假象,详见上述内容)。

......
deque<int> id;

id.push_back(1);
id.push_back(2);
id.push_back(3);
id.push_back(4);
id.push_back(5);
id.push_back(6);

cout << id[2] << endl;	/*3*/
......

deque的查找

有迭代器在,查找可以用STL内部实现的find()。当然,有重载“[]”运算符,按普通的顺序查找也可行。这里只给出迭代器版本:

......
deque<int> id;

id.push_back(1);
id.push_back(2);
id.push_back(6);

deque<int>::iterator ite;

ite = find(id.begin(),id.end(),6);
cout << *ite << endl;	/*6*/
......

deque的排序

我们已经知道,deque实际不是连续的存储空间,它使用了“分段存储,整体维护”的空间模式,当然代价是庞杂的迭代器。所以STL的sort()函数在这里并不适用。侯杰老师推荐,将deque所有的元素倒腾到一个vector中,再用STL的sort()函数,再从vector中倒腾进deque中。这种折腾是必须的,直接在的deque内部进行排序,效率更低。

建议

deque在实际的应用当中使用的比较少,但正如文章开头指出的,它是容器stack和queue的幕后功臣,所以了解它的内部实现机制多多益善。

本文完 2012-10-17

捣乱小子 http://www.daoluan.net/

17 October 2012

disqus 可能被墙~