微塵--KeepMoving

 

 

本文檔深入分析了std::deque，并提供了一個指導思想：當考慮到內存分配和執行性能的時候，使用std::deque要比std::vector好。

　　介紹

　　本文深入地研究了std::deque 容器。本文將討論在一些情況下使用deque> 比vector更好。讀完這篇文章后讀者應該能夠理解在容量增長的過程中deque 與vector在內存分配和性能的不同表現。由于deque> 和vector的用法很相似，讀者可以參考vector 文檔中介紹如何使用STL容器。

　　Deque總覽

　　deque和vector一樣都是標準模板庫中的內容，deque是雙端隊列，在接口上和vector非常相似，在許多操作的地方可以直接替換。假如讀者已經能夠有效地使用vector容器，下面提供deque的成員函數和操作，進行對比參考。

　　Deque成員函數

函數	描述
c.assign(beg,end) c.assign(n,elem)	將[beg; end)區間中的數據賦值給c。 將n個elem的拷貝賦值給c。
c.at(idx)	傳回索引idx所指的數據，如果idx越界，拋出out_of_range。
c.back()	傳回最后一個數據，不檢查這個數據是否存在。
c.begin()	傳回迭代器重的可一個數據。
c.clear()	移除容器中所有數據。
deque<Elem> c deque<Elem> c1(c2) Deque<Elem> c(n) Deque<Elem> c(n, elem) Deque<Elem> c(beg,end) c.~deque<Elem>()	創建一個空的deque。 復制一個deque。 創建一個deque，含有n個數據，數據均已缺省構造產生。 創建一個含有n個elem拷貝的deque。 創建一個以[beg;end)區間的deque。 銷毀所有數據，釋放內存。
c.empty()	判斷容器是否為空。
c.end()	指向迭代器中的最后一個數據地址。
c.erase(pos) c.erase(beg,end)	刪除pos位置的數據，傳回下一個數據的位置。 刪除[beg,end)區間的數據，傳回下一個數據的位置。
c.front()	傳回地一個數據。
get_allocator	使用構造函數返回一個拷貝。
c.insert(pos,elem) c.insert(pos,n,elem) c.insert(pos,beg,end)	在pos位置插入一個elem拷貝，傳回新數據位置。 在pos位置插入>n個elem數據。無返回值。 在pos位置插入在[beg,end)區間的數據。無返回值。
c.max_size()	返回容器中最大數據的數量。
c.pop_back()	刪除最后一個數據。
c.pop_front()	刪除頭部數據。
c.push_back(elem)	在尾部加入一個數據。
c.push_front(elem)	在頭部插入一個數據。
c.rbegin()	傳回一個逆向隊列的第一個數據。
c.rend()	傳回一個逆向隊列的最后一個數據的下一個位置。
c.resize(num)	重新指定隊列的長度。
c.size()	返回容器中實際數據的個數。
C1.swap(c2) Swap(c1,c2)	將c1和c2元素互換。 同上操作。

　　Deque操作

函數	描述
operator[]	返回容器中指定位置的一個引用。

　　上面這些特征和vector明顯相似，所以我們會提出下面的疑問。

　　問題：如果deque和vector可以提供相同功能的時候，我們使用哪一個更好呢？

　　回答：如果你要問的話，就使用vector吧。

　　或者你給個解釋？

　　非常高興你這樣問，的確，這并不是無中生有的，事實上，在C++標準里解釋了這個問題，下面有一個片斷：

　　vector在默認情況下是典型的使用序列的方法，對于deque，當使用插入刪除操作的時候是一個更好的選擇。

　　有趣的是，本文就是要非常徹底地理解這句話。

　　什么是新的？

　　細讀上面兩張表格，你會發現和vector比較這里增加了兩個函數。

　　1、c.push_front(elem) —— 在頭部插入一個數據。

　　2、c.pop_front() —— 刪除頭部數據。

　　調用方法和c.push_back(elem)和c.pop_back()相同，這些將來會告訴我們對于deque> 會非常有用，deque可以在前后加入數據。>

　　缺少了什么？

　　同時你也會發現相對于vector> 缺少了兩個函數，你將了解到deque> 不需要它們。

　　1、capacity()—— 返回vector當前的容量。

　　2、reserve() —— 給指定大小的vector> 分配空間。

　　這里是我們真正研究的開始，這里說明deque> 和vector它們在管理內部存儲的時候是完全不同的。deque是大塊大塊地分配內存，每次插入固定數量的數據。vector是就近分配內存（這可能不是一個壞的事情）。但我們應該關注是，vector每次增加的內存足夠大的時候，在當前的內存不夠的情況。下面的實驗來驗證deque不需要capacity()和reserve()> 是非常有道理的。

　　實驗一 —— 增長的容器

　　目的

　　目的是通過實驗來觀察deque和vector在容量增長的時候有什么不同。用圖形來說明它們在分配內存和執行效率上的不同。

　　描述

　　這個實驗的測試程序是從一個文件中讀取文本內容，每行作為一個數據使用push_back插入到deque> 和vector中，通過多次讀取文件來實現插入大量的數據，下面這個類就是為了測試這個內容：

#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; };

　　結果

　　測試程序運行的平臺和一些條件：

CPU	1.8 GHz Pentium 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。

 

實驗二—— vector::reserve()的資源

　　目的

　　這個實驗的目的是vector在加入大量數據之前調用reserve()，和deque進行比較，看它們的內存分配和執行效率怎么樣？

　　描述

　　本實驗中的測試基本上和實驗一相同，除了在測試類的構造函數中加入下面這行代碼:

m_vData.reserve(1000000);

　　結果

　　測試程序運行的平臺和一些條件：


　　使用Windows任務管理器來記錄執行效率，本程序中使用了>Laurent Guinnard 的CDuration類。消耗系統資源如下圖：


　　我們注意到vector不在需要分配花費多余的時間分配內存了，這是由于我們使用了reserve()對于所測試的>691180個數據為我們每一次插入大量數據的時候保留了足夠的內存空間，對于deque存儲分配的假設，觀察這個測試中的內存分配圖形和上一個圖形，我們需要進一步量化這個測試。

　　怎樣改良內存分配的性能呢？

　　下面這個圖例說明隨著數據的增加，容量在增加：


　　當增加數據的時候對容量的增加在vector和deque執行效率基本一樣，然而，vector在插入數據的時候有一些零星的時間消耗，看下面的圖例：


　　通過統計分析vector和deque在插入平均為>1755.85長度的>9874個數據所花費的時間，下面是總結的表格：

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

　　實驗三——內存回收

　　目的

　　本實驗是對假設deque分配的內存不是臨近的，而且很難回收進行量化測試分析。

　　描述

　　在本實驗中再次用到了實驗一中的代碼，在調用函數中加入記錄增加數據執行的效率具體入下面操作：

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里插入了平均每個長度為>1755.85的字符串。>


　　盡管從幾個曲線圖中看到的實際消耗時間不同，但些曲線圖都精確到了>R2=95.15%。所給的數據點都實際背離了下表中統計的曲線圖數據:

　　在相同的情況下比較vector的結果是非常有意義的。下面圖就是將vector和deque在相同的情況下分配內存消耗的時間比較圖：


　　這些數據在這個測試中是>R2=82.12%。這或許可以經過每個點反復運行得到更加優化，在這個問題中這些數據適當地標注了這些點，所給的數據點都實際背離了下表中統計的曲線圖數據:

實驗四—— vector::insert() 和 deque::insert() 執行特點比較

　　目的

　　deque主張使用參數為常量的insert()。但怎么樣能和vector::insert()比較一下呢？本實驗的目的就是比較一下vector::insert()> 和 deque::insert()的工作特點。

　　描述

　　在容器的容器多次插入數據，在這里可能不符合你的需求，既然這樣你可以使用insert()，試驗代碼也和實驗一基本一樣，使用insert()代替push_back()，使用insert(>)來測試。

　　結果

　　當插入常量給deque的時候，從下圖可以看出和vector的對比來。


　　注意兩張圖片中時間軸的不同，這是將>61810個數據插入到容器中。


　　實驗五——讀取容器的性能

　　目的

　　這個實驗將測試vector::at(),vector::operator[],deque::at()和deque::operator[]的性能。首先應該是operator[]比at（）效率要高，因為它不進行邊界檢查，同時也比較vector和deque。

　　描述

　　這個實驗將測試中的容器有1000000個類型為std::string，每個字符串長度為1024的數據，分別使用at()和operator[]這兩個操作來訪問容器容器的數據，測試它們運行的時間，這個測試執行50次，統計每次執行的結果。

　　結果

　　我們看到使用vector和deque訪問容器中的數據，他們執行的性能差別很小，使用operator[]和at()訪問數據的性能差別幾乎可以忽略不計，下面是統計的結果：

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

　　結論

　　在這篇文章中我們覆蓋了多種不同的情況來選擇我們到底是該使用vector還是deque。讓我們總結一下測試的結果看下面幾個結論。

　　當執行大數據量的調用push_back()的時候，記住要調用vector::reserve()。

　　在實驗一中我們研究了vector和deque在插入數據的情況。通過這些假設，我們可以看出deque分配的空間是預先分配好的，deque維持一個固定增長率，在vector實驗中我們考慮到應該調用vecor::reserve()>.然后在下面這個例子驗證了我們的假設，在使用vector的時候調用reserve()能夠膀子我們預先分配空間，這將是vector一個默認選擇的操作。

　　當你分配很多內存單元的時候，記住使用deque回收內存要比vector消耗時間多。

　　在實驗三中我們探討了vector和deque在回收非鄰接內存塊上的不同，分別證明了vector在分配內存的時候是線性增長，而deque是指數增長，同樣，vector要回收的內存比deque多的多，如果你循環調用了push_back()，那么deque將獲取大量的內存，而且是臨近的。我們通過測試發現在分配內存單元消耗的時間和vector的時間接近。

　　如果你計劃使用insert()，或者需要pop_front()，那就使用deque。

　　由于vector沒有提供pop_front()函數，但在實驗四的結果中可以看出沒有insert()是非常好的，同時也告訴我們為什么deque在STL類中要作為單獨的一個類劃分出來。

　　對于訪問數據，vector::at()效率最高。

　　在實驗五中統計的數據表示，所有訪問數據方法的效率是非常接近的，但是vector::at()效率最高。這是因為最優的平衡圖訪問時間為最低的六個西格瑪值。

　　最后

　　我希望本文能夠帶你認識deque，而且對它感興趣或者一個啟發，歡迎繼續討論關于vector和deque任何問題和內容。