天天看點

vector和list的聯系和差別

STL提供了三個最基本的容器:vector,list,deque。

最大的差別是,list是雙向的,而vector是單向的。

一、關于vector

vector和built-in數組類似:

(1) 擁有一段連續的記憶體空間,并且起始位址不變,是以它能非常好的支援随即存取,即[]操作符

(2) 但由于它的記憶體空間是連續的,是以在中間進行插入和删除會造成記憶體塊的拷貝

(3) 當該數組後的記憶體空間不夠時,需要重新申請一塊足夠大的記憶體并進行記憶體的拷貝。

注:(2)(3)影響了vector的效率。

如果vector中存儲的對象很大,或者構造函數複雜,則在對現有元素進行拷貝時開銷較大,因為拷貝對象要調用拷貝構造函數。

對于簡單的小對象,vector的效率優于list。vector在每次擴張容量的時候,将容量擴充2倍,這樣對于小對象來說,效率是很高的。

二、關于list

list就是資料結構中的雙向連結清單:

(1) 記憶體空間可以是不連續的,通過指針來進行資料的通路,這個特點使得它的随機存取變t得非常沒有效率

(2) 由于連結清單的特點,它可以以很好的效率支援任意地方的删除和插入。

注:

list中的對象是離散存儲的,随機通路某個元素需要周遊list。在list中插入元素,尤其是在首尾插入元素,效率很高,隻需要改變元素的指針。

三、關于deque

deque是一個double-ended queue,它具有以下兩個特點:

(1) 它支援[]操作符,也就是支援随即存取,并且和vector的效率相差無幾,

(2) 它支援在兩端的操作:push_back,push_front,pop_back,pop_front等,并且在兩端操作上與list的效率也差不多。

(3) 通過兩級數組結構來實作,一級表示實際的容器,第二級指向容器的首和尾   

四、實際使用時,如何選擇這三個容器:

  1、vector:針對 對象數量變化少,簡單對象,随機通路元素頻繁,而不在乎插入和删除的效率

  2、list: 針對 對象數量變化大,對象複雜,插入和删除頻

  3、deque:需要随即存取,而且關心兩端資料的插入和删除   

繼續閱讀