本文檔深入分析了std::deque，并提供了一個(gè)指導(dǎo)思想：當(dāng)考慮到內(nèi)存分配和執(zhí)行性能的時(shí)候，使用std::deque要比std::vector好。
介紹
本文深入地研究了std::deque 容器。本文將討論在一些情況下使用deque> 比vector更好。讀完這篇文章后讀者應(yīng)該能夠理解在容量增長(zhǎng)的過程中deque 與vector在內(nèi)存分配和性能的不同表現(xiàn)。由于deque> 和vector的用法很相似，讀者可以參考vector 文檔中介紹如何使用STL容器。
Deque總覽
deque和vector一樣都是標(biāo)準(zhǔn)模板庫中的內(nèi)容，deque是雙端隊(duì)列，在接口上和vector非常相似，在許多操作的地方可以直接替換。假如讀者已經(jīng)能夠有效地使用vector容器，下面提供deque的成員函數(shù)和操作，進(jìn)行對(duì)比參考。
Deque成員函數(shù)
函數(shù)
|
描述 |
c.assign(beg,end)
c.assign(n,elem)
|
將[beg; end)區(qū)間中的數(shù)據(jù)賦值給c。
將n個(gè)elem的拷貝賦值給c。 |
c.at(idx)
|
傳回索引idx所指的數(shù)據(jù)，如果idx越界，拋出out_of_range。 |
c.back()
|
傳回最后一個(gè)數(shù)據(jù)，不檢查這個(gè)數(shù)據(jù)是否存在。 |
c.begin()
|
傳回迭代器重的可一個(gè)數(shù)據(jù)。 |
c.clear()
|
移除容器中所有數(shù)據(jù)。 |
deque<Elem> c
deque<Elem> c1(c2)
Deque<Elem> c(n)
Deque<Elem> c(n, elem)
Deque<Elem> c(beg,end)
c.~deque<Elem>()
|
創(chuàng)建一個(gè)空的deque。
復(fù)制一個(gè)deque。
創(chuàng)建一個(gè)deque，含有n個(gè)數(shù)據(jù)，數(shù)據(jù)均已缺省構(gòu)造產(chǎn)生。
創(chuàng)建一個(gè)含有n個(gè)elem拷貝的deque。
創(chuàng)建一個(gè)以[beg;end)區(qū)間的deque。
銷毀所有數(shù)據(jù)，釋放內(nèi)存。 |
c.empty()
|
判斷容器是否為空。 |
c.end()
|
指向迭代器中的最后一個(gè)數(shù)據(jù)地址。 |
c.erase(pos)
c.erase(beg,end)
|
刪除pos位置的數(shù)據(jù)，傳回下一個(gè)數(shù)據(jù)的位置。
刪除[beg,end)區(qū)間的數(shù)據(jù)，傳回下一個(gè)數(shù)據(jù)的位置。 |
c.front()
|
傳回地一個(gè)數(shù)據(jù)。 |
get_allocator
|
使用構(gòu)造函數(shù)返回一個(gè)拷貝。 |
c.insert(pos,elem)
c.insert(pos,n,elem)
c.insert(pos,beg,end)
|
在pos位置插入一個(gè)elem拷貝，傳回新數(shù)據(jù)位置。
在pos位置插入>n個(gè)elem數(shù)據(jù)。無返回值。
在pos位置插入在[beg,end)區(qū)間的數(shù)據(jù)。無返回值。 |
c.max_size()
|
返回容器中最大數(shù)據(jù)的數(shù)量。 |
c.pop_back()
|
刪除最后一個(gè)數(shù)據(jù)。 |
c.pop_front()
|
刪除頭部數(shù)據(jù)。 |
c.push_back(elem)
|
在尾部加入一個(gè)數(shù)據(jù)。 |
c.push_front(elem)
|
在頭部插入一個(gè)數(shù)據(jù)。 |
c.rbegin()
|
傳回一個(gè)逆向隊(duì)列的第一個(gè)數(shù)據(jù)。 |
c.rend()
|
傳回一個(gè)逆向隊(duì)列的最后一個(gè)數(shù)據(jù)的下一個(gè)位置。 |
c.resize(num)
|
重新指定隊(duì)列的長(zhǎng)度。 |
c.size()
|
返回容器中實(shí)際數(shù)據(jù)的個(gè)數(shù)。 |
C1.swap(c2)
Swap(c1,c2)
|
將c1和c2元素互換。
同上操作。 |
Deque操作
函數(shù)
|
描述 |
operator[]
|
返回容器中指定位置的一個(gè)引用。 |
上面這些特征和vector明顯相似，所以我們會(huì)提出下面的疑問。
問題：如果deque和vector可以提供相同功能的時(shí)候，我們使用哪一個(gè)更好呢？
回答：如果你要問的話，就使用vector吧。
或者你給個(gè)解釋？
非常高興你這樣問，的確，這并不是無中生有的，事實(shí)上，在C++標(biāo)準(zhǔn)里解釋了這個(gè)問題，下面有一個(gè)片斷：
vector在默認(rèn)情況下是典型的使用序列的方法，對(duì)于deque，當(dāng)使用插入刪除操作的時(shí)候是一個(gè)更好的選擇。
有趣的是，本文就是要非常徹底地理解這句話。
什么是新的？
細(xì)讀上面兩張表格，你會(huì)發(fā)現(xiàn)和vector比較這里增加了兩個(gè)函數(shù)。
1、c.push_front(elem) —— 在頭部插入一個(gè)數(shù)據(jù)。
2、c.pop_front() —— 刪除頭部數(shù)據(jù)。
調(diào)用方法和c.push_back(elem)和c.pop_back()相同，這些將來會(huì)告訴我們對(duì)于deque> 會(huì)非常有用，deque可以在前后加入數(shù)據(jù)。>
缺少了什么？
同時(shí)你也會(huì)發(fā)現(xiàn)相對(duì)于vector> 缺少了兩個(gè)函數(shù)，你將了解到deque> 不需要它們。
1、capacity()—— 返回vector當(dāng)前的容量。
2、reserve() —— 給指定大小的vector> 分配空間。
這里是我們真正研究的開始，這里說明deque> 和vector它們?cè)诠芾韮?nèi)部存儲(chǔ)的時(shí)候是完全不同的。deque是大塊大塊地分配內(nèi)存，每次插入固定數(shù)量的數(shù)據(jù)。vector是就近分配內(nèi)存（這可能不是一個(gè)壞的事情）。但我們應(yīng)該關(guān)注是，vector每次增加的內(nèi)存足夠大的時(shí)候，在當(dāng)前的內(nèi)存不夠的情況。下面的實(shí)驗(yàn)來驗(yàn)證deque不需要capacity()和reserve()> 是非常有道理的。
實(shí)驗(yàn)一 —— 增長(zhǎng)的容器
目的
目的是通過實(shí)驗(yàn)來觀察deque和vector在容量增長(zhǎng)的時(shí)候有什么不同。用圖形來說明它們?cè)诜峙鋬?nèi)存和執(zhí)行效率上的不同。
描述
這個(gè)實(shí)驗(yàn)的測(cè)試程序是從一個(gè)文件中讀取文本內(nèi)容，每行作為一個(gè)數(shù)據(jù)使用push_back插入到deque> 和vector中，通過多次讀取文件來實(shí)現(xiàn)插入大量的數(shù)據(jù)，下面這個(gè)類就是為了測(cè)試這個(gè)內(nèi)容：
#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;
}; |
結(jié)果
測(cè)試程序運(yùn)行的平臺(tái)和一些條件：
| CPU |
1.8 GHz Pentium 4 |
| 內(nèi)存 |
1.50 GB |
| 操作系統(tǒng) |
W2K-SP4 |
| 文件中的行數(shù) |
9874 |
平均每行字母?jìng)€(gè)數(shù)
|
1755.85 |
讀文件的次數(shù)
|
45 |
| 總共插入的數(shù)據(jù)個(gè)數(shù) |
444330 |
使用Windows任務(wù)管理器來記錄執(zhí)行效率，本程序中使用了Laurent Guinnard 的CDuration類。消耗系統(tǒng)資源如下圖：
注意在vector分配內(nèi)存的最高峰，vector在分配內(nèi)存的時(shí)候是怎樣達(dá)到最高值，deque就是這樣的，它在插入數(shù)據(jù)的同時(shí)，內(nèi)存直線增長(zhǎng)，首先deque的這種內(nèi)存分配單元進(jìn)行回收的話，存在意想不到的后果，我們希望它的分配內(nèi)存看上去和vector一樣，通過上面的測(cè)試我們需要進(jìn)一步的測(cè)試，現(xiàn)提出一個(gè)假設(shè)：假設(shè)deque分配的內(nèi)存不是連續(xù)的，一定需要釋放和收回內(nèi)存，我們將這些假設(shè)加入后面的測(cè)試中，但是首先讓我們從執(zhí)行的性能外表分析一下這個(gè)實(shí)驗(yàn)。
究竟分配內(nèi)存需要消耗多久？
注意看下面這張圖片，vector在不插入數(shù)據(jù)的時(shí)候在進(jìn)行尋求分配更多內(nèi)存。
同時(shí)我們也注意到使用push_back插入一組數(shù)據(jù)消耗的時(shí)間，注意，在這里每插入一組數(shù)據(jù)代表著9874個(gè)串，平均每個(gè)串的長(zhǎng)度是1755.85。
實(shí)驗(yàn)二—— vector::reserve()的資源 目的
這個(gè)實(shí)驗(yàn)的目的是vector在加入大量數(shù)據(jù)之前調(diào)用reserve()，和deque進(jìn)行比較，看它們的內(nèi)存分配和執(zhí)行效率怎么樣？
描述
本實(shí)驗(yàn)中的測(cè)試基本上和實(shí)驗(yàn)一相同，除了在測(cè)試類的構(gòu)造函數(shù)中加入下面這行代碼:
| m_vData.reserve(1000000); |
結(jié)果
測(cè)試程序運(yùn)行的平臺(tái)和一些條件：
CPU
|
1.8 GHz Pentium 4 |
內(nèi)存
|
1.50 GB |
操作系統(tǒng)
|
W2K-SP4 |
文件中的行數(shù)
|
9874 |
平均每行字母?jìng)€(gè)數(shù)
|
1755.85 |
讀文件的次數(shù)
|
70 |
總共插入的數(shù)據(jù)個(gè)數(shù)
|
691180 |
使用
Windows任務(wù)管理器來記錄執(zhí)行效率，本程序中使用了>Laurent Guinnard 的CDuration類。消耗系統(tǒng)資源如下圖：
我們注意到vector不在需要分配花費(fèi)多余的時(shí)間分配內(nèi)存了，這是由于我們使用了reserve()對(duì)于所測(cè)試的>691180個(gè)數(shù)據(jù)為我們每一次插入大量數(shù)據(jù)的時(shí)候保留了足夠的內(nèi)存空間，對(duì)于deque存儲(chǔ)分配的假設(shè)，觀察這個(gè)測(cè)試中的內(nèi)存分配圖形和上一個(gè)圖形，我們需要進(jìn)一步量化這個(gè)測(cè)試。
怎樣改良內(nèi)存分配的性能呢？
下面這個(gè)圖例說明隨著數(shù)據(jù)的增加，容量在增加：
當(dāng)增加數(shù)據(jù)的時(shí)候?qū)θ萘康脑黾釉趘ector和deque執(zhí)行效率基本一樣，然而，vector在插入數(shù)據(jù)的時(shí)候有一些零星的時(shí)間消耗，看下面的圖例：
通過統(tǒng)計(jì)分析vector和deque在插入平均為>1755.85長(zhǎng)度的>9874個(gè)數(shù)據(jù)所花費(fèi)的時(shí)間，下面是總結(jié)的表格：
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
|
|
實(shí)驗(yàn)三——內(nèi)存回收 目的
本實(shí)驗(yàn)是對(duì)假設(shè)deque分配的內(nèi)存不是臨近的，而且很難回收進(jìn)行量化測(cè)試分析。
描述
在本實(shí)驗(yàn)中再次用到了實(shí)驗(yàn)一中的代碼，在調(diào)用函數(shù)中加入記錄增加數(shù)據(jù)執(zhí)行的效率具體入下面操作：
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);
}
|
結(jié)果
本測(cè)試和上面兩個(gè)實(shí)驗(yàn)在相同的平臺(tái)上運(yùn)行，除了插入的數(shù)據(jù)由>9874到>691180，需要插入>70次，下面圖例顯示了>deque在插入數(shù)據(jù)的時(shí)候分配內(nèi)存的情況，在deque里插入了平均每個(gè)長(zhǎng)度為>1755.85的字符串。>
盡管從幾個(gè)曲線圖中看到的實(shí)際消耗時(shí)間不同，但些曲線圖都精確到了>R2=95.15%。所給的數(shù)據(jù)點(diǎn)都實(shí)際背離了下表中統(tǒng)計(jì)的曲線圖數(shù)據(jù):
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的結(jié)果是非常有意義的。下面圖就是將vector和deque在相同的情況下分配內(nèi)存消耗的時(shí)間比較圖：
這些數(shù)據(jù)在這個(gè)測(cè)試中是>R2=82.12%。這或許可以經(jīng)過每個(gè)點(diǎn)反復(fù)運(yùn)行得到更加優(yōu)化，在這個(gè)問題中這些數(shù)據(jù)適當(dāng)?shù)貥?biāo)注了這些點(diǎn)，所給的數(shù)據(jù)點(diǎn)都實(shí)際背離了下表中統(tǒng)計(jì)的曲線圖數(shù)據(jù):
vector Results
|
Mean
|
-0.007122715sec
|
Maximum
|
0.283452127 sec
|
Minimum
|
-0.26724459sec
|
Std. Dev
|
0.144572356sec
|
6-Sigma
|
0.867434136sec |
實(shí)驗(yàn)四—— vector::insert() 和 deque::insert() 執(zhí)行特點(diǎn)比較
目的
deque主張使用參數(shù)為常量的insert()。但怎么樣能和vector::insert()比較一下呢？本實(shí)驗(yàn)的目的就是比較一下vector::insert()> 和 deque::insert()的工作特點(diǎn)。
描述
在容器的容器多次插入數(shù)據(jù)，在這里可能不符合你的需求，既然這樣你可以使用insert()，試驗(yàn)代碼也和實(shí)驗(yàn)一基本一樣，使用insert()代替push_back()，使用insert(>)來測(cè)試。
結(jié)果
當(dāng)插入常量給deque的時(shí)候，從下圖可以看出和vector的對(duì)比來。
注意兩張圖片中時(shí)間軸的不同，這是將>61810個(gè)數(shù)據(jù)插入到容器中。
實(shí)驗(yàn)五——讀取容器的性能 目的
這個(gè)實(shí)驗(yàn)將測(cè)試vector::at(),vector::operator[],deque::at()和deque::operator[]的性能。首先應(yīng)該是operator[]比at（）效率要高，因?yàn)樗贿M(jìn)行邊界檢查，同時(shí)也比較vector和deque。
描述
這個(gè)實(shí)驗(yàn)將測(cè)試中的容器有1000000個(gè)類型為std::string，每個(gè)字符串長(zhǎng)度為1024的數(shù)據(jù)，分別使用at()和operator[]這兩個(gè)操作來訪問容器容器的數(shù)據(jù)，測(cè)試它們運(yùn)行的時(shí)間，這個(gè)測(cè)試執(zhí)行50次，統(tǒng)計(jì)每次執(zhí)行的結(jié)果。
結(jié)果
我們看到使用vector和deque訪問容器中的數(shù)據(jù)，他們執(zhí)行的性能差別很小，使用operator[]和at()訪問數(shù)據(jù)的性能差別幾乎可以忽略不計(jì)，下面是統(tǒng)計(jì)的結(jié)果：
vector::at()
|
Mean
|
1.177088125sec
|
Maximum
|
1.189580000sec
|
Minimum
|
1.168340000sec
|
Std. Dev
|
0.006495193sec
|
6-Sigma
|
0.038971158sec
|
|
deque::at()
|
Mean
|
1.182364375sec
|
Maximum
|
1.226860000sec
|
Minimum
|
1.161270000sec
|
Std. Dev
|
0.016362148sec
|
6-Sigma
|
0.098172888sec
|
|
vector::operator[]
|
Mean
|
1.164221042sec
|
Maximum
|
1.192550000sec
|
Minimum
|
1.155690000sec
|
Std. Dev
|
0.007698520sec
|
6-Sigma
|
0.046191120sec
|
|
deque::operator[]
|
Mean
|
1.181507292sec
|
Maximum
|
1.218540000 sec
|
Minimum
|
1.162710000sec
|
Std. Dev
|
0.010275712sec
|
6-Sigma
|
0.061654272sec
|
|
結(jié)論 在這篇文章中我們覆蓋了多種不同的情況來選擇我們到底是該使用vector還是deque。讓我們總結(jié)一下測(cè)試的結(jié)果看下面幾個(gè)結(jié)論。
當(dāng)執(zhí)行大數(shù)據(jù)量的調(diào)用push_back()的時(shí)候，記住要調(diào)用vector::reserve()。
在實(shí)驗(yàn)一中我們研究了vector和deque在插入數(shù)據(jù)的情況。通過這些假設(shè)，我們可以看出deque分配的空間是預(yù)先分配好的，deque維持一個(gè)固定增長(zhǎng)率，在vector實(shí)驗(yàn)中我們考慮到應(yīng)該調(diào)用vecor::reserve()>.然后在下面這個(gè)例子驗(yàn)證了我們的假設(shè)，在使用vector的時(shí)候調(diào)用reserve()能夠膀子我們預(yù)先分配空間，這將是vector一個(gè)默認(rèn)選擇的操作。
當(dāng)你分配很多內(nèi)存單元的時(shí)候，記住使用deque回收內(nèi)存要比vector消耗時(shí)間多。
在實(shí)驗(yàn)三中我們探討了vector和deque在回收非鄰接內(nèi)存塊上的不同，分別證明了vector在分配內(nèi)存的時(shí)候是線性增長(zhǎng)，而deque是指數(shù)增長(zhǎng)，同樣，vector要回收的內(nèi)存比deque多的多，如果你循環(huán)調(diào)用了push_back()，那么deque將獲取大量的內(nèi)存，而且是臨近的。我們通過測(cè)試發(fā)現(xiàn)在分配內(nèi)存單元消耗的時(shí)間和vector的時(shí)間接近。
如果你計(jì)劃使用insert()，或者需要pop_front()，那就使用deque。
由于vector沒有提供pop_front()函數(shù)，但在實(shí)驗(yàn)四的結(jié)果中可以看出沒有insert()是非常好的，同時(shí)也告訴我們?yōu)槭裁磀eque在STL類中要作為單獨(dú)的一個(gè)類劃分出來。
對(duì)于訪問數(shù)據(jù)，vector::at()效率最高。
在實(shí)驗(yàn)五中統(tǒng)計(jì)的數(shù)據(jù)表示，所有訪問數(shù)據(jù)方法的效率是非常接近的，但是vector::at()效率最高。這是因?yàn)樽顑?yōu)的平衡圖訪問時(shí)間為最低的六個(gè)西格瑪值。
最后 我希望本文能夠帶你認(rèn)識(shí)deque，而且對(duì)它感興趣或者一個(gè)啟發(fā)，歡迎繼續(xù)討論關(guān)于vector和deque任何問題和內(nèi)容。