vector vs deque - Aeolus Zheng的专栏 - CSDN博客

来源:百度文库 编辑:神马文学网 时间:2024/04/28 17:53:26
STL Deque 容器翻译:JiangMiao 出处: www.sssdf.com 时间: 2005-08-08

注: 转载请保证文章完整性原作者:Nitron 绪言这篇文章深入的角度认识 STL deque 容器。这篇文章将讨论一些有关deque的情况,比如在何种情况下你可以用deque代替vector以取得更好的效果。读完这篇文章后,你应该能从容器膨胀,性能,内存分配方面解释 vector 与 deque 的不同。我们强烈推荐您读完这篇文章关于 怎样使用STL 容器vectorDeque 概述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: deuquevector有如此相似的函数,那哪个更优越内?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 #include #include #include  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 m_vData;          std::deque 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; xRunReadTestFile("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很好的表明了这一切。如果有大量释放操作,比起vectordeque将花费更多的时间.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 meanof 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 forstd. deviation is the Greek letter, sigma, BTW) from the mean, you willhave 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 have99.73% of the area and so forth until you get to 6 标准偏差, when you have99.99985% of the area (1.5 Defects per million, 6-Sigma).Final WordsI hope you have gained some insight into dequeand have found this article both interesting and enlightening. Anyquestions 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.