STL(一)-stl中的vector，list，deque,map,set的差別



在STL中基本容器有: string、vector、list、deque、set、map

set 和map都是無序的儲存元素,隻能通過它提供的接口對裡面的元素進行通路

set:集合, 用來判斷某一個元素是不是在一個組裡面,使用的比較少

map:映射,相當于字典,把一個值映射成另一個值,如果想建立字典的話使用它好了

底層采用的是樹型結構,多數使用平衡二叉樹實作,查找某一值是常數時間,周遊起來效果也不錯, 隻是每次插入值的時候,會重新構成底層的平衡二叉樹,效率有一定影響.

string、vector、list、deque是有序容器

1.string

string 是basic_string 的實作,在記憶體中是連續存放的.為了提高效率,都會有保留記憶體,如string s= "abcd",這時s使用的空間可能就是255, 當string再次往s裡面添加内容時不會再次配置設定記憶體.直到内容>255時才會再次申請記憶體,是以提高了它的性能.

當内容>255時,string會先配置設定一個新記憶體,然後再把内容複制過去,再複制先前的内容.

對string的操作,如果是添加到最後時,一般不需要配置設定記憶體,是以性能最快;

如果是對中間或是開始部分操作,如往那裡添加元素或是删除元素,或是代替元素,這時需要進行記憶體複制,性能會降低.

如果删除元素,string一般不會釋放它已經配置設定的記憶體,為了是下次使用時可以更高效.

由于string會有預保留記憶體,是以如果大量使用的話,會有記憶體浪費,這點需要考慮.還有就是删除元素時不釋放過多的記憶體,這也要考慮.

string中記憶體是在堆中配置設定的,是以串的長度可以很大,而char[]是在棧中配置設定的,長度受到可使用的最大棧長度限制.

如果對知道要使用的字元串的最大長度,那麼可以使用普通的char[],實作而不必使用string.

string用在串長度不可知的情況或是變化很大的情況.

如果string已經經曆了多次添加删除,現在的尺寸比最大的尺寸要小很多,想減少string使用的大小,可以使用:

string s = "abcdefg";

string y(s); // 因為再次配置設定記憶體時,y隻會配置設定與s中内容大一點的記憶體,是以浪費不會很大

s.swap(y); // 減少s使用的記憶體

如果記憶體夠多的話就不用考慮這個了

capacity是檢視現在使用記憶體的函數

大家可以試試看string配置設定一個一串後的capacity傳回值,還有其它操作後的傳回值

2.vector

vector就是動态數組.它也是在堆中配置設定記憶體,元素連續存放,有保留記憶體,如果減少大小後記憶體也不會釋放.如果新值>目前大小時才會再配置設定記憶體.

它擁有一段連續的記憶體空間，并且起始位址不變，是以它能非常好的支援随即存取，即[]操作符，但由于它的記憶體空間是連續的，是以在中間進行插入和删除會造成記憶體塊的拷貝，另外，當該數組後的記憶體空間不夠時，需要重新申請一塊足夠大的記憶體并進行記憶體的拷貝。這些都大大影響了vector的效率。

對最後元素操作最快(在後面添加删除最快 ), 此時一般不需要移動記憶體,隻有保留記憶體不夠時才需要

對中間和開始處進行添加删除元素操作需要移動記憶體,如果你的元素是結構或是類,那麼移動的同時還會進行構造和析構操作，是以性能不高（最好将結構或類的指針放入vector中，而不是結構或類本身，這樣可以避免移動時的構造與析構)。

通路方面,對任何元素的通路都是O(1),也就是是常數的,是以vector常用來儲存需要經常進行随機通路的内容,并且不需要經常對中間元素進行添加删除操作.

相比較可以看到vector的屬性與string差不多,同樣可以使用capacity看目前保留的記憶體,使用swap來減少它使用的記憶體.

總結

需要經常随機通路請用vector

3.list

list就是雙向連結清單,元素也是在堆中存放,每個元素都是放在一塊記憶體中,它的記憶體空間可以是不連續的，通過指針來進行資料的通路，這個特點使得它的随即存取變的非常沒有效率，是以它沒有提供[]操作符的重載。但由于連結清單的特點，它可以以很好的效率支援任意地方的删除和插入。

list沒有空間預留習慣,是以每配置設定一個元素都會從記憶體中配置設定,每删除一個元素都會釋放它占用的記憶體.

list在哪裡添加删除元素性能都很高,不需要移動記憶體,當然也不需要對每個元素都進行構造與析構了,是以常用來做随機操作容器.

但是通路list裡面的元素時就開始和最後通路最快

通路其它元素都是O(n) ,是以如果需要經常随機通路的話,還是使用其它的好

總結

如果你喜歡經常添加删除大對象的話,那麼請使用list

要儲存的對象不大,構造與析構操作不複雜,那麼可以使用vector代替

list<指針>完全是性能最低的做法,這種情況下還是使用vector<指針>好,因為指針沒有構造與析構,也不占用很大記憶體

4.deque

deque是一個雙端隊列(double-ended queue)，也是在堆中儲存内容的.它的儲存形式如下:

[堆1]

...

[堆2]

...

[堆3]

每個堆儲存好幾個元素,然後堆和堆之間有指針指向,看起來像是list和vector的結合品,不過确實也是如此

deque可以讓你在前面快速地添加删除元素,或是在後面快速地添加删除元素,然後還可以有比較高的随機通路速度

它支援[]操作符，也就是支援随即存取，可以讓你在前面快速地添加删除元素,或是在後面快速地添加删除元素,然後還可以有比較高的随機通路速度,和vector的效率相差無幾，它支援在兩端的操作：push_back,push_front,pop_back,pop_front等，并且在兩端操作上與list的效率也差不多。

在标準庫中vector和deque提供幾乎相同的接口,在結構上它們的差別主要在于這兩種容器在組織記憶體上不一樣,deque是按頁或塊來配置設定存儲器的,每頁包含固定數目的元素.相反vector配置設定一段連續的記憶體,vector隻是在序列的尾段插入元素時才有效率,而deque的分頁組織方式即使在容器的前端也可以提供常數時間的insert和erase操作,而且在體積增長方面也比vector更具有效率

總結：

vector是可以快速地在最後添加删除元素,并可以快速地通路任意元素

list是可以快速地在所有地方添加删除元素,但是隻能快速地通路最開始與最後的元素

deque在開始和最後添加元素都一樣快,并提供了随機通路方法,像vector一樣使用[]通路任意元素,但是随機通路速度比不上vector快,因為它要内部處理堆跳轉

deque也有保留白間.另外,由于deque不要求連續空間,是以可以儲存的元素比vector更大,這點也要注意一下.還有就是在前面和後面添加元素時都不需要移動其它塊的元素,是以性能也很高。

是以在實際使用時，如何選擇這三個容器中哪一個，應根據你的需要而定，一般應遵循下面

的原則：

1、如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector

2、如果你需要大量的插入和删除，而不關心随即存取，則應使用list

3、如果你需要随即存取，而且關心兩端資料的插入和删除，則應使用deque。