【轉貼】vector vs deque

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  deque s.

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.