STL Deque 容器的深度研究
4.98/5 (152投票s)
2003年11月12日
14分钟阅读
489956
本文对std::deque进行了深入的分析，并考虑到内存分配和容器性能，就何时倾向于使用它而非std::vector提供了指导。
引言
本文对STL的deque容器进行了深入的探讨。本文将讨论deque的优点以及在什么情况下您会选择使用它而不是vector。阅读本文后，读者应该能够解释vector和deque在容器增长、性能和内存分配方面的基本区别。由于deque在用法和语法上与vector非常相似，因此建议读者参考这篇关于vector的文章[^]，以获取有关实现和使用此STL容器的信息。
Deque概述
deque，与vector一样，也属于标准模板库，即STL。deque，或称为“双端队列”，表面上与vector非常相似，并且在许多实现中可以作为直接替代品。由于假设读者已经知道如何有效地使用STL vector容器，因此我将在下表中提供deque成员函数和运算符的对比和参考。
Deque成员函数1
| 函数 | 描述 |
赋值 |
从deque中擦除元素，并将一组新元素复制到目标deque。 |
at |
返回deque中指定位置元素的引用。 |
back |
返回deque最后一个元素的引用。 |
begin |
返回指向deque中第一个元素的迭代器。 |
clear |
擦除deque中的所有元素。 |
双端队列 |
构造一个具有特定大小、特定值的元素、特定分配器或作为其他deque全部或部分副本的deque。 |
empty |
测试deque是否为空。 |
end |
返回指向deque中最后一个元素之后位置的迭代器。 |
erase |
从指定位置移除deque中的一个元素或一个元素范围。 |
front |
返回deque中第一个元素的引用。 |
get_allocator |
返回用于构造deque的分配器对象的副本。 |
插入 |
在指定位置向deque插入一个或多个元素或一个元素范围。 |
max_size |
返回deque的最大长度。 |
pop_back |
删除deque末尾的元素。 |
pop_front |
删除deque开头的元素。 |
push_back |
向deque末尾添加一个元素。 |
push_front |
向deque开头添加一个元素。 |
rbegin |
返回反向deque中第一个元素的迭代器。 |
rend |
返回指向反向deque中最后一个元素之后的迭代器。 |
resize |
指定deque的新大小。 |
size |
返回deque中的元素数量。 |
swap |
交换两个deque的元素。 |
Deque运算符1
| 函数 | 描述 |
operator[] |
返回deque中指定位置元素的引用。 |
这种与vector惊人的相似性引出了以下问题：
问：如果deque和vector提供如此相似的功能，那么何时倾向于使用其中一个而不是另一个？
答：如果您需要询问，请使用vector。
嗯，好吧……能稍微解释一下吗？
当然，很高兴您问了！我并非凭空给出这个答案，事实上，这个答案来自C++标准2本身。第23.1.1节指出：
vector是应默认使用的序列类型……deque是在序列的开头或结尾进行大部分插入和删除时的数据结构首选。
有趣的是，本文几乎致力于完全理解这句话。
有什么新内容
在仔细阅读了上面的表格并与vector进行比较后，您会注意到两个新的成员函数。
push_front()- 向deque的开头添加元素。pop_front()- 从deque的开头删除元素。
这些函数的使用语法与push_back()和pop_back()相同。这便是可能值得使用deque的第一个特性，即需要向序列的开头和结尾都添加元素。
缺失的部分
您还会注意到vector中有两个成员函数在deque中未实现，而且如您所见，deque并不需要它们。
capacity()- 返回vector的当前容量。reserve()- 为vector中指定数量的元素分配空间。
这便是我们研究的真正开端。事实证明，deque和vector在底层管理其内部存储方面存在着显著差异。deque在增长时按块分配内存，每块包含固定数量的元素。然而，vector将内存分配为连续的块（这并非一定是坏事）。但关于vector的有趣之处在于，在vector意识到当前缓冲区不够大后，每次分配时内部缓冲区的增长幅度都会越来越大。下面的实验旨在证明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 奔腾 4 |
| 内存 | 1.50 GB |
| 操作系统 | W2K-SP4 |
| 文件行数 | 9874 |
| 平均每行字符数 | 1755.85 |
| 文件读取次数 | 45 |
| 总插入元素数 | 444330 |
系统性能通过Windows任务管理器记录，程序使用Laurent Guinnard的CDuration类进行计时。系统性能图如下所示：
请注意vector分配内存期间的内存使用峰值，以及随着vector分配的内部缓冲区存储不断增加而增大的峰值。还请注意deque没有出现此行为，并且缓冲区随元素插入呈线性增长。deque反分配期间内核时间的跳跃以及内存被回收时的曲线形状最初是一个意料之外的结果。我本以为反分配会与vector相似。在进一步研究和进行更多测试后，我提出了一个假设：由于deque的内存不是连续的，因此查找和回收难度更大。我们将在稍后检验这个假设，但首先让我们分析一下本实验的性能方面。
那些内存分配到底需要多长时间？
请注意下图，在vector寻找更多内存期间没有添加任何元素。
另外，也值得注意的是每次push_back()操作需要多长时间。下图说明了这一点。请记住，每个样本包含9874个字符串，平均长度为1755.85。
实验2 - vector::reserve()的影响
目标
本实验的目的是观察在向vector添加大量元素之前调用reserve()的好处，并与deque在内存分配和性能方面进行比较。
描述
本实验的测试描述与实验1相同，但测试类构造函数中添加了以下代码：
m_vData.reserve(1000000);
结果
测试在以下条件下进行：
| Processor | 1.8 GHz 奔腾 4 |
| 内存 | 1.50 GB |
| 操作系统 | W2K-SP4 |
| 文件行数 | 9874 |
| 平均每行字符数 | 1755.85 |
| 文件读取次数 | 70 |
| 总插入元素数 | 691180 |
系统性能通过Windows任务管理器记录，程序使用Laurent Guinnard的CDuration类进行计时。系统性能图如下所示：
值得注意的是，vector不再需要分配额外的内部缓冲区存储。reserve()调用一步就分配了足够多的空间，足以满足我们测试平台691180个元素的需求。至于deque反分配假设，请观察与前一个测试相比，内存反分配时间急剧增长。我们将在下一个实验中量化这一点。
内存分配性能是如何改善的？
下图说明了容器随时间添加的元素数量：
正如您所见，在向容器添加元素方面，vector的性能现在非常接近deque。但是，vector在插入给定元素集所需的时间方面往往更加零散。下图说明了这一点：
下表总结了vector与deque在插入9874个平均长度为1755.85的元素所需时间上的变异性统计分析：
向量 |
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); }
结果
本实验与前两个实验在同一平台进行，但分配的数量从9874增加到691180，共有70个增量。下图说明了回收deque内存所需的时间与deque中元素数量的关系。deque填充了平均长度为1755.85个字符的字符串。
尽管实际时间在几个实例中与趋势线有显著差异，但趋势线仍然准确，R2=95.15%。任何给定数据点与趋势线的实际偏差总结在下表中：
| Deque结果 | |
| 平均 | 0.007089269 秒 |
| 最大 | 11.02838496 秒 |
| 最低 | -15.25901667 秒 |
| 标准差 | 3.3803636 秒 |
| 6西格玛 | 20.2821816 秒 |
与同一场景下vector的结果相比，这相当显著。下图显示了vector在与上面deque相同的负载下的反分配时间：
此测试中的数据R2=81.12%。通过对每个数据点进行更多迭代并平均运行结果，可能可以进一步提高。尽管如此，数据足以标示出问题点，并且任何给定数据点与趋势线的偏差总结在以下统计参数中：
| Vector结果 | |
| 平均 | -0.007122715 秒 |
| 最大 | 0.283452127 秒 |
| 最低 | -0.26724459 秒 |
| 标准差 | 0.144572356 秒 |
| 6西格玛 | 0.867434136 秒 |
实验4 - vector::insert() 与 deque::insert() 的性能特征
目标
deque的“招牌菜”就是所谓的常数时间insert()。这与vector::insert()相比如何？（毫不奇怪）本实验的目的就是观察vector::insert()与deque::insert()的性能特征。
描述
有时，向容器后端添加元素可能不符合您的需求。在这种情况下，您可能需要使用insert()。本实验的形式也与实验1相同，但它使用的是insert()而不是push_back()。
结果
正如您在下图中所看到的，与vector相比，deque提供的常数时间插入的好处是惊人的。
请注意时间尺度的差异，因为向这些容器添加了61810个元素。
实验5 - 容器检索性能
目标
本实验将测试vector::at()、vector::operator[]、deque::at()和deque::operator[]的性能。有人认为operator[]比at()快，因为它没有边界检查，并且还要求比较vector与deque在这方面。
描述
本测试将在每个容器中插入1000000个std::string类型的元素，长度为1024个字符，并测量通过at()和operator[]访问所有元素所需的时间。每个场景将进行50次测试，结果将以统计摘要的形式呈现。
结果
嗯，或许令人惊讶的是，在访问容器中的元素方面，vector和deque之间的性能差异非常小。operator[]和at()之间的差异也微乎其微。这些结果总结如下：
|
| ||||||||||||||||||||||||
|
| ||||||||||||||||||||||||
结论
在本文中，我们讨论了几种可能需要选择vector和deque的情况。让我们总结一下结果，看看我们的结论是否与标准一致。
在执行大量push_back()调用时，请记住调用vector::reserve()。
在实验1中，我们研究了vector和deque之间的容器增长行为。在此场景中，我们看到由于deque按预定大小的块分配其内部存储，因此deque可以以恒定速率增长。然后，本实验中vector的性能促使我们考虑调用vector::reserve()。这是实验2的前提，我们执行了相同的实验，只是我们在vector上调用了reserve()。因此，这成为坚持使用vector作为我们默认选择的理由。
如果您执行大量反分配操作，请记住deque回收内存比vector花费的时间更长。
在实验3中，我们探讨了vector的连续内存块和deque的非连续内存块回收之间的差异。结果表明，vector回收内存与元素数量成线性比例，而deque是指数级增长。此外，在回收内存方面，vector比deque快几个数量级。顺便说一句，如果您在紧密的循环或序列中执行push_back()调用，deque获得的内存很可能大部分是连续的。我曾出于好奇测试过这种情况，发现这些情况下的反分配时间接近vector。
如果您计划使用insert()，或者需要pop_front()，请使用deque。
好吧，vector没有pop_front()，但根据实验4的结果，它最好也没有insert()。实验4的结果充分说明了deque的必要性以及它为何作为独立的容器类存在于STL中。
对于元素访问，vector::at()险胜。
在总结了实验5的统计数据后，我不得不说，尽管所有方法都很接近，但vector::at()是赢家。这是因为它在原始平均访问时间和最低的6西格玛值之间取得了最佳平衡。
这6西格玛是怎么回事？
虽然6西格玛如今是行业内一个流行的时髦词，但它实际上起源于统计学。如果您为样本数据生成高斯分布（或钟形曲线），那么您可以显示，在均值的一个标准差（顺便说一句，标准差的符号是希腊字母sigma）处，您将覆盖曲线下的68.27%区域。在2个标准差（2-Sigma）处，您覆盖95.45%的区域，在3个标准差处，您覆盖99.73%的区域，依此类推，直到6个标准差，这时您覆盖99.99985%的区域（每百万个缺陷1.5个，即6-Sigma）。
结束语
希望您对deque有了一些了解，并觉得本文既有趣又有启发。如果您有任何疑问或意见，欢迎随时提出，并鼓励对vector或deque进行任何讨论。
参考文献
- 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.