deque

时间：2010-08-26 来源：snailshen

STL Deque 容器
翻译：JiangMiao 出处: www.sssdf.com 时间: 2005-08-08

注：　转载请保证文章完整性
原作者：Nitron
绪言
这篇文章深入的角度认识 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 target deque.
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 a deque.
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 the deque 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 reversed deque.
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多了如下两个函数.

1. push_front() - Adds elements to the front of a deque.
2. pop_front() - Removes elements from the front of a deque.

他们从语法结构上来看与 push_back() and pop_back()一样。这里产生了第一条使用 deque的理由，曰：你需要从首或尾双向追加元素。
What's Missing
我们又可以发现下面两个元素是vector特有的

1. capacity() - Returns the current capacity of a vector.
2. 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
Mean

0.603724814 sec
Maximum

0.738313000 sec
Minimum

0.559959000 sec
Std. Dev

0.037795736 sec
6-Sigma

0.226774416 sec

Mean

0.588021114 sec
Maximum

0.615617000 sec
Minimum

0.567503000 sec
Std. Dev

0.009907800 sec
6-Sigma

0.059446800 sec
实验 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::at()
Mean

1.177088125 sec
Maximum

1.189580000 sec
Minimum

1.168340000 sec
Std. Dev

0.006495193 sec
6-Sigma

0.038971158 sec

deque::at()
Mean

1.182364375 sec
Maximum

1.226860000 sec
Minimum

1.161270000 sec
Std. Dev

0.016362148 sec
6-Sigma

0.098172888 sec
vector::operator[]
Mean

1.164221042 sec
Maximum

1.192550000 sec
Minimum

1.155690000 sec
Std. Dev

0.007698520 sec
6-Sigma

0.046191120 sec

deque::operator[]
Mean

1.181507292 sec
Maximum

1.218540000 sec
Minimum

1.162710000 sec
Std. Dev

0.010275712 sec
6-Sigma

0.061654272 sec
结论
这种篇文章中，我们覆盖了几个不同的情况，关于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 of vector 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

   1. Plauger, P.J. Standard C++ Library Reference. February, 2003. MSDN.
   2. ISO/IEC 14882:1998(E). Programming Languages - C++. ISO and ANSI C++ Standard.
   3. Schildt, Herbert. C++ from the Ground Up, Second Edition. Berkeley: 1998.

Sutter, Herb. More Exceptional C++. Indianapolis: 2002.