天天看點

順序容器vector、list、deque的差別

說明:這篇文章主要通過查閱網上資料整理而成,并非原創。

順序容器

三種容器均支援resieze()操作,重新劃定容器大小,且此函數有重載。

vector

vector和built-in數組類似,是一個在堆上建立的一維數組,它擁有一段連續的記憶體空間,并且起始位址不變,是以 它能非常好的支援随即存取,即[]操作符。vector因為存儲在堆上,是以支援erase( ), resieze()(重新劃分容器容量)等操作; vector不用擔心越界當空間不夠用的時候,系統會自動按照一定的比例(對capacity( )大小)進行擴充。在vector序列末尾添加(push_back( ))或者删除(pop_back( ))對象效率高,在中間進行插入或删除效率很低,主要是要進行元素的移動和記憶體的拷貝,原因就在于當記憶體不夠用的時候要執行重新配置設定記憶體,拷貝對象到新存儲區,銷毀old對象,釋放記憶體等操 作,如果對象很多的話,這種操作代價是相當高的。為了減少這種代價,使用vector最理想的情況就是事先知道所要裝入的對象數目,用成員函式 reserve( )預定下來;vector最大的優點莫過于是檢索(用operator[ ])速度在這三個容器中是最快的,

list

list的本質是一個雙向連結清單(根據sgi stl源代碼),記憶體空間不連續,通過指針進行操作。說道連結清單,它的高效率首先表現是插入,删除元素,進行排序等等需要移動大量元素的操作。顯然連結清單沒有檢索操作operator[ ], 也就是說不能對連結清單進行随機通路,而隻能從頭至尾地周遊,這是它的一個缺陷。list有不同于前兩者的某些成員方法,如合并list的方法splice( ), 排序sort( ),交換list 的方法swap( )等等。

deque

deque是一個double-ended queue是由多個連續記憶體塊構成,deque是list和vector的相容,分為多個塊,每一個塊大小是512位元組,塊通過map塊管理,map塊裡儲存每個塊得首位址。是以該容器也有索引操作operator[ ],效率沒vector高。另外,deque比vector多了push_front( ) & pop_front( )操作。在兩端進行此操作時與list的效率 差不多

下面是選擇順序容器類型的一些準則

1.如果我們需要随機通路一個容器則vector要比list好得多 。

2.如果我們已知要存儲元素的個數則vector 又是一個比list好的選擇。

3.如果我們需要的不隻是在容器兩端插入和删除元素則list顯然要比vector好

4.除非我們需要在容器首部插入和删除元素否則vector要比deque好。

5.如果隻在容易的首部和尾部插入資料元素,則選擇deque.

6.如果隻需要在讀取輸入時在容器的中間位置插入元素,然後需要随機通路元素,則可考慮輸入時将元素讀入到一個List容器,接着對此容器重新排序,使其适合順序通路,然後将排序後的list容器複制到一個vector容器中

繼續閱讀