set 和map都是無序的保存元素,只能通過它提供的接口對裏面的元素進行訪問
set:集合,
用來判斷某壹個元素是不是在壹個組裏面,使用的比較少
map:映射,相當於字典,把壹個值映射成另壹個值,如果想創建字典的話使用它好了
底層采用的是樹型結構,多數使用平衡二叉樹實現,查找某壹值是常數時間,遍歷起來效果也不錯,
只是每次插入值的時候,會重新構成底層的平衡二叉樹,效率有壹定影響.
string、vector、list、deque、set 是有序容器
1.string
string 是basic_string<char> 的實現,在內存中是連續存放的.為了提高效率,都會有保留內存,如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。