英文原文：http://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container
绪言
这篇文章深入的角度认 识 STL deque 容器。这篇文章将讨论一些有关deque的情况，比如在何种情况下你可以用deque代替vector以取 得更好的效果。读完这篇文章后，你应该能从容器膨胀，性能，内存分配方面解释 vector 与 deque 的不同。我们强烈推荐您读完这篇文章 关于 怎样使用STL 容器vector
Deque 概述
deque,与 vector, 都是 Standard Template Library 的一部分。 deque, 或者称之为 双向队列容器, 表面上与 vector 非常相似。甚至能在许多实现中直接替换 vector。 我们假设读者已经知道了怎样有效的使用vector容器 我已经在下面列出一张deque成员函数的表格。方便于参考与比较。
Deque Member Functions1
| Function | Description |
| assign | Erases elements from a deque and copies a new set of elements to the targetdeque. |
| at | Returns a reference to the element at a specified location in the deque. |
| back | Returns a reference to the last element of the deque. |
| begin | Returns an iterator addressing the first element in the deque. |
| clear | Erases all the elements of a deque. |
| deque | Constructs a deque of a specific size or with elements of a specific value or with a specific allocator or as a copy of all or part of some other deque. |
| empty | Tests if a deque is empty. |
| end | Returns an iterator that addresses the location succeeding the last element in adeque. |
| erase | Removes an element or a range of elements in a deque from specified positions. |
| front | Returns a reference to the first element in a deque. |
| get_allocator | Returns a copy of the allocator object used to construct the deque. |
| insert | Inserts an element or a number of elements or a range of elements into thedeque at a specified position. |
| max_size | Returns the maximum length of the deque. |
| pop_back | Deletes the element at the end of the deque. |
| pop_front | Deletes the element at the beginning of the deque. |
| push_back | Adds an element to the end of the deque. |
| push_front | Adds an element to the beginning of the deque. |
| rbegin | Returns an iterator to the first element in a reversed deque. |
| rend | Returns an iterator that points just beyond the last element in a reverseddeque. |
| resize | Specifies a new size for a deque. |
| size | Returns the number of elements in the deque. |
| swap | Exchanges the elements of two deques. |
Deque Operators1
| Function | Description |
| operator[] | Returns a reference to the deque element at a specified position. |
对于与vector如此惊人的相似，我们提出了如下问题:
Q: deuque和vector有如此相似的函数，那哪个更优越内?
A: 如果你非要我回答的话.....是vector.
好，能稍微解释一下吗?
很乐意回答你的问题，我当然不是凭空捏造的，这个答案来自于 C++ Standard2 itself. Section 23.1.1 中的如下声明:
vector 是一个你因该默认选择的容器. ... 而 deque仅仅优先选择于大量的首或尾删除操作.
非常有趣，这篇文章的目的就是为了完全阐明上句话的含义.
What's New
我们刚刚比较了deque与vector两者的成员函数，发现deque较vector多了如下两个函数.
- push_front() - Adds elements to the front of a deque.
pop_front() - Removes elements from the front of a deque.
他们从语法结构上来看与 push_back() and pop_back()一样。 这里产生了第一条使用 deque的理由，曰：你需要从首或尾双向追加元素。
What's Missing
我们又可以发现下面两个元素是vector特有的
- capacity() - Returns the current capacity of a vector.
reserve() - Allocates room for a specified number of elements in a vector.
这里真正的翻开了本次学习的第一页. 他告诉了我们 vector与 deque内部数据管理的根本不同。 deque分配内存是一块块的，每当它插入固定数量的数据. 然而vector分配就近原则 (这并不是什么坏事). 但有趣的是当 vector意识到当前的内部缓冲不够在大时，就加大每个allocation，以满足当前的需要。 在后面实验当中，我们能很好的证明 deque为什么不需要capacity()和 reserve() .
实验 1 - 容器膨胀
目的
这个实验用来观测vector与 deque膨胀时的区别. 实验结果以插图形式从物理内存分配与程序性能两分面说明。
描述
这个测试用小程序从文件中读入数据，以行为单位push_back()到 vector与 deque中. 目的是产成大量的插入动作，文件可能读不止一次。本次的小程序如下:
#include <deque>
#include <fstream>
#include <string>
#include <vector>
static enum modes
{
FM_INVALID = 0,
FM_VECTOR,
FM_DEQUE
};
class CVectorDequeTest
{
public:
CVectorDequeTest();
void ReadTestFile(const char* szFile, int iMode)
{
char buff[0xFFFF] = {0};
std::ifstream inFile;
inFile.open(szFile);
while(!inFile.eof())
{
inFile.getline(buff, sizeof(buff));
if(iMode == FM_VECTOR)
m_vData.push_back(buff);
else if(iMode == FM_DEQUE)
m_dData.push_back(buff);
}
inFile.close();
}
virtual ~CVectorDequeTest();
protected:
std::vector<std::string> m_vData;
std::deque<std::string> m_dData;
};
结果
本次测试的物理环境:
| Processor | 1.8 GHz Pentium 4 |
| Memory | 1.50 GB |
| OS | W2K-SP4 |
| No. of Lines in File | 9874 |
| Avg. Chars per Line | 1755.85 |
| No. of Times File Read | 45 |
| Total Elements Inserted | 444330 |
系统的性能由windows自带的Task Manager表明，程序的耗时由 Laurent Guinnard's CDuration class 实现. 实验结果如下:
我们注意到，在vector重新分配时会有一个峰，为何峰值越来越大在vector分配内部缓冲存储。而deque却没有这种行为,随着数据插入成线性增长。 当 deque释 放时，内存回收成曲线下降，是我们最初没有预料到的。我们起先预测内存释放因该看到去与vector很相似。看来我们南非要更多的一些测试。我们能够建立 一些假设： deque内存并不是邻近的，那么回收起来会更加复杂。我们稍后验证这个假设，先来分析一下本次实验的性能分析结果。
内存分配花了多长时间?
显而易见，当vector在扩容时没有任何新的元素插入。
每个容器的push_back()花费了多长时间也是比较有趣的. 如下所示。记住，每个例子追加了9874个元素，平均长度1755.85。
测试 2 - vector::reserve()效果
目的
本次实验的目的是观察在大量元素追加前调用vector的reserve()函数的变化情况， 从内存分配与性能上比较与deque区别,
描述
本次实验和一基本相同，只不过多了下面一句话。
m_vData.reserve(1000000);
结果
测试环境地s:
| Processor | 1.8 GHz Pentium 4 |
| Memory | 1.50 GB |
| OS | W2K-SP4 |
| No. of Lines in File | 9874 |
| Avg. Chars per Line | 1755.85 |
| No. of Times File Read | 70 |
| Total Elements Inserted | 691180 |
系统的性能由windows自带的Task Manager表明，程序的耗时由 Laurent Guinnard's CDuration class 实现. 实验结果如下:
很有趣！vector不再需要分配更多的内部缓冲存储。reserve()使得vector有足够的空间一次性容下我们所有的测试数据，691180个！.对与deque的释放猜想, 观察到内存释放时间较上一次实验大幅度增长.在我们下一个实验来搞定这个问题.
内存分配性能有多大提升?
下面张图描述了元素追加所花的时间:
正如你所看到了，vector和deque在在追加元素的性能性能上不分伯仲，然而, vector在插入给定的元素的时间上有一些轻微的离散参考的图:
总体变化 vector vs. deque, 以他花费入9874 个 平均度有 1755.85 长的元素,如下表所示:
| Vector | Deque | ||||||||||||||||||||
|
|
实验 3 - 内存回收
目的
本次实验的目的是分析内存和试着证实我们的猜测：deque内存的因为非邻近的关系而释放内存有点困难。
描述
这个测试类来自实验1， 调用函数专为分配测试类的增长大小而设计，并记入数据。，具体实现好下:
for(xRun=0; xRun<NUMBER_OF_XRUNS; xRun++)
{
df = new CVectorDequeTest;
elapsed_time = 0;
for(i=0; i<NUMBER_OF_RUNS*xRun; i++)
{
cout << "Deque - Run " << i << " of " << NUMBER_OF_RUNS*xRun << "... ";
df->ReadTestFile("F:\\huge.csv",DF_DEQUE);
deque_data.push_back(datapoint());
deque_data.back().time_to_read = df->GetProcessTime();
elapsed_time += deque_data.back().time_to_read;
deque_data.back().elapsed_time = elapsed_time;
cout << deque_data.back().time_to_read << " seconds\n";
}
vnElements.push_back(df->GetDequeSize());
cout << "\n\nDeleting... ";
del_deque.Start();
delete df;
del_deque.Stop();
cout << del_deque.GetDuration()/1000000.0 << " seconds.\n\n";
vTimeToDelete.push_back(del_deque.GetDuration()/1000000.0);
}
结果
主次实验的平台与上两次的一样。除了内存分配的数量不同从，用70次增长从9874 到 691180。下图指出deque内存回收时间依deque里的元素个数deque由平均长度为1755.85字节的字符串填冲。
尽管用几个真实的时间数据和拟合线有较大出入。但总体来说拟合线从使精确度控制在 R2=95.15%. 下表给出的数据都背离了拟合线。
| deque Results | |
| Mean | 0.007089269 sec |
| Maximum | 11.02838496 sec |
| Minimum | -15.25901667 sec |
| Std. Dev | 3.3803636 sec |
| 6-Sigma | 20.2821816 sec |
用同样的放式测能vector，见下图:
这次数据的精确度 R2=81.12%. 这可以通过更多的测试进一步题高.但是, 数据已经能很好的说明了结果, 下表结出的数据都和拟合线有较大出入。
| vector Results | |
| Mean | -0.007122715 sec |
| Maximum | 0.283452127 sec |
| Minimum | -0.26724459 sec |
| Std. Dev | 0.144572356 sec |
| 6-Sigma | 0.867434136 sec |
实验 4 - vector::insert() vs. deque::insert()的性能特性。
目的
deque以保证等时间插入insert()出了名 他能与vector::insert()对抗吗? 本次实验的目的是 (不必惊讶)观查vector::insert()与 deque::insert()之间的性能特性。
描述
也许有几次发现从容后面插入并不能达到你的目标，这种情况下，你多半会祭出insert()来解决当前困难。本次的实验程序和实验1的一样，仅仅是把push_back由insert()代替。
结果
从下面的图中看到，比起vector来 deque的常量时间差能力令人瞠目皆舌，强！
时间轴差别醒目, (61810元素).
实验 5 - 容器读取性能
目的
这个实验比较vector::at(), vector::operator[], deque::at()与 deque::operator[]之间的性能差. 想得到operator[]快于at()，因为operator[]没有边界检测能力。自然，还有vector与deque的私人恩怨.
描述
本次测试将插入1000000长度为1024字符的字串到每个容器。并且通过at()和opearator[]读出。测试50次，结果以统计表形式给出。
解果
也许有点惊讶，vector和deque访问元素能力之间的区别非常小。还有几乎可以忽略的at与operator[]之间的差别，结果如下。
|
|
||||||||||||||||||||||||
|
|
||||||||||||||||||||||||
结论
这种篇文章中，我们覆盖了几个不同的情况，关于vector和deque的取舍，请参考以下几点。
当有大量数据要push_back时，记得要vector::reserve().
在实验1中，我们研究了vector和deque的增长行为，在这次场景中，我们看到因为deque的特性而有一个固定的增长率。vector使我们考虑使用reserve()，实验2很好的表明了这一切。
如果有大量释放操作，比起vector，deque将花费更多的时间.
In Experiment 3, we explored the differences between reclaiming the contiguous and non-contiguous memory blocks ofvector and deque, respectively. The results proved that vector reclaims memory in linear proportion to the number of elements whereas deque is exponential. Also, vector is several orders of magnitude than deque in reclaiming memory. As a side note, if you are performing your calls to push_back() within a tight loop or sequence, there is a significant possibility that most of the memory deque obtains, will be contiguous. I have tested this situation for fun and have found the deallocation time to be close to vector in these cases.
如果你打算用insert或者有pop_front()的需要，使用deque.
Well, ok, vector doesn't have pop_front(), but based on the results of Experiment 4, it might as well not have insert()either. The results of Experiment 4 speak volumes about the need for deque and why it is part of the STL as a separate container class.
对于元素访问vector::at()明显胜了，(JiangMiao:不是因为他快，而是他的的不慢且安全).
After summing up the statistics of Experiment 5, I would have to say that although all the methods were close,vector::at() is the winner. This is because of the best balance between the raw mean of the access times as well as the lowest 6-sigma value.
What's all this 6-Sigma stuff?
Although a popular buzzword in industry today, 6-Sigma 在 统计学中有着举足轻重的地位. 如果你要生成高斯分部（正态分部) 为你的样本程序, 你能看到一些数据误差很大 (the symbol for std. deviation is the Greek letter, sigma, BTW) from the mean, you will have 68.27% of the area under the curve covered. At 2 标准偏差, 2-Sigma, you have 95.45% of the area under the curve, at 3 标准偏差, you will have 99.73% of the area and so forth until you get to 6 标准偏差, when you have 99.99985% of the area (1.5 Defects per million, 6-Sigma).
Final Words
I hope you have gained some insight into deque and have found this article both interesting and enlightening. Any questions or comments are certainly welcome and any discussion on vector or deque is encouraged.
References
- Plauger, P.J. Standard C++ Library Reference. February, 2003. MSDN.
ISO/IEC 14882:1998(E). Programming Languages - C++. ISO and ANSI C++ Standard.
Schildt, Herbert. C++ from the Ground Up, Second Edition. Berkeley: 1998.
Sutter, Herb. More Exceptional C++. Indianapolis: 2002.
deque从逻辑上来看是连续的内存，本质上是由一段段固定大小 的连续空间组成。deque采用类似索引的结构管理内存，如下：
采用一小块连续的内存索引缓存结点，每一个缓存结点也是一段连续的空间，可以存储多个数据。当索引内存空间满载，需要申请一块更大的内存做索引。
4. 为什么deque没有capacity和reserve
vector有capacity和reserve函数，deque和list一样，没有capacity和reserve函数。之所以这样，主要是因为list和deque两者都没有必要保留这两个函数,list是以1为增量动态增加内存，deque则是分段动态增加内存 。capacity返回当前所分配的内存块大小，vector在调用函数reserve(n)之后，其capacity将至少为N=n，reserve函数的作用是当现有内存空间小于N时重新分配内存。如果事先知道要插入N个元素，则与不断分配内存相比，预先调用reserve可以加快程序的运行速度。
底层：
http://blog.csdn.net/mdl13412/article/details/6647409
