STL容器及適配器

STL容器

?

1.序列式容器

：?vector，deque，list。

每個元素都有固定的位置（取決于插入的時機和位置，與元素值無關）。

?

vector

特點：
將一個元素置于一個動態數組中加以管理，可以隨機存取元素。在數組尾部添加或刪除元素非常快速，但是在中部或頭部插入或刪除元素比較耗時。

deque

“double-ended queue” 雙端隊列，可以隨機存取。數組尾部或頭部添加或刪除元素非常快速，但在中部插入或刪除元素比較費時。實際上，deque 是對vector 和list 優缺點的結合，它是處于兩者之間的一種容器。

list

雙向鏈表，不提供隨機存取（按順序存儲），在任何位置插入或刪除動作都非常迅速。只能順序訪問（從前向后或者從后向前）。與前面兩種容器類有一個明顯的區別就是：它不支持隨機訪問。要訪問表中某個下標處的項需要從表頭或表尾處（接近該下標的一端）開始循環。而且缺少下標預算符：operator[]。

1?vector

向量 相當于一個數組
??? 在內存中分配一塊連續的內存空間進行存儲。支持不指定vector大小的存儲。STL內部實現時，首先分配一個非常大的內存空間預備進行存儲，即capacituy（）函數返回的大小，當超過此分配的空間時再整體重新放分配一塊內存存儲，這給人以vector可以不指定vector即一個連續內存的大小的感覺。通常此默認的內存分配能完成大部分情況下的存儲。
?? 優點：(1) 不指定一塊內存大小的數組的連續存儲，即可以像數組一樣操作，但可以對此數組
?????????????? 進行動態操作。通常體現在push_back() pop_back()
?????????????? (2) 隨機訪問方便，即支持[ ]操作符和vector.at()
?????????????? (3) 節省空間。
?? 缺點：(1) 在內部進行插入刪除操作效率低。
?????????????? (2) 只能在vector的最后進行push和pop，不能在vector的頭進行push和pop。
??????????????? (3)?當動態添加的數據超過vector默認分配的大小時要進行整體的重新分配、拷貝與釋放?。

操作：

1插入和刪除操作push_back，pop_back（只能在數組尾部進行），刪除特定位置元素erase；

2返回固定位置的元素at（int n）,支持【】操作，頭和尾元素front，back；

3返回頭或尾的指針用begin，end；

4其他：size,swap,empty;

2?list
??? 雙向鏈表
??? 每一個結點都包括一個信息快Info、一個前驅指針Pre、一個后驅指針Post。可以不分配必須的內存大小方便的進行添加和刪除操作。使用的是非連續的內存空間進行存儲。
?? 優點：(1) 不使用連續內存完成動態操作。
???????????????(2) 在內部方便的進行插入和刪除操作
?????????????? (3) 可在兩端進行push、pop
?? 缺點：(1)?不能進行內部的隨機訪問，即不支持[ ]操作符和vector.at()
?????????????? (2) 相對于verctor占用內存多

? 操作：

???????

函數名??? 說明

assign()??? 給list賦值back()?? 返回最后一個元素begin()??? 返回指向第一個元素的迭代器

clear()? empty()? erase() 刪除一個元素 remove()從list刪除元素

remove_if()???? 按指定條件刪除元素

front()???? 返回第一個元素? end()?????? 返回末尾的迭代器

insert()???? 插入一個元素到list中pop_back()?????? 刪除最后一個元素

pop_front()???? 刪除第一個元素push_back()?????? 在list的末尾添加一個元素

push_front()??? 在list的頭部添加一個元素

reverse()? 把list的元素倒轉

size()?????? 返回list中的元素個數

sort()?????? 給list排序

splice()???? 合并兩個list,源list的內容部分或全部元素刪除，拼插入到目的list

swap()???? 交換兩個list

unique()?? 刪除list中重復的元素

3?deque
???雙端隊列 double-end queue
???deque是在功能上合并了vector和list。
?? 優點：(1) 隨機訪問方便，即支持[ ]操作符和vector.at()
???????????????(2) 在內部方便的進行插入和刪除操作
?????????????? (3) 可在兩端進行push、pop
?? 缺點：(1) 占用內存多
? 操作：

pop_back() 刪除尾部的元素pop_front() 刪除頭部的元素

push_back() 在尾部加入一個元素push_front() 在頭部加入一個元素

其他vector有的他也有。（與vector區別就是他多一個頭部插入和刪除的功能）

?

?

使用區別：
???? 1 如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用vector?
???? 2 如果你需要大量的插入和刪除，而不關心隨即存取，則應使用list?
???? 3 如果你需要隨即存取，而且關心兩端數據的插入和刪除，則應使用deque

?

?

2.關聯式容器

：set，multiset, map, multimap

元素位置取決于特定的排序準則，與插入順序無關。

???

????

?

?

關聯容器和順序容器的本質區別：?

關聯容器是通過鍵存取和讀取元素、順序容器通過元素在容器中的位置順序存儲和訪問元素。因此，關聯容器不提供front、push_front、pop_front、back、push_back以及pop_back，此外對于關聯容器不能通過容器大小來定義，因為這樣的話將無法知道鍵所對應的值什么。

?

都支持find、count、insert、erase操作。

?

Sets/Multisets：
內部的元素依據其值自動排序，Set內的相同數值的元素只能出現一次，Multisets內可包含多個數值相同的元素，內部由二叉樹實現（實際上基于紅黑樹(RB-tree）實現），便于查找；

? 操作：

???????

?

Maps/Multimaps：

Map的元素是成對的鍵值/實值，內部的元素依據其值自動排序，Map內的相同數值的元素只能出現一次，Multimaps內可包含多個數值相同的元素，內部由二叉樹實現（實際上基于紅黑樹(RB-tree）實現），便于查找；

map就是一個容器，里面裝的就是若干個pair。每個pair的第一個元素，稱為鍵（注意鍵的類型必須支持小于(<)操作），第二個元素，稱為值。對于普通的map，每個鍵都對應一個值。這樣的看起來，鍵類似于數組的下標，而值類似于數組的值。

?

?

?

STL容器適配器

：棧stack 、隊列queue 和優先級priority_queue 。

?

適配器是容器的接口，它本身不能直接保存元素，它保存元素的機制是調用

另一種順序容器去實現，即可以把適配器看作“它保存一個容器，這個容器再保
存所有元素”。(不能由迭代器訪問元素或者數組下表訪問元素)
*STL 中提供的三種適配器可以由某一種順序容器去實現。默認下stack 和queue 基于deque 容器實現，priority_queue 則基于vector 容器實現。由于適配器的特點，一個適配器不是可以由任一個順序容器都可以實現的。棧stack 的特點是后進先出，所以它關聯的基本容器可以是任意一種順序容器，因為這些容器類型結構都可以提供棧的操作有求，它們都提供了push_back 、pop_back 和back 操作。隊列queue 的特點是先進先出，適配器要求其關聯的基礎容器必須提供pop_front 操作，因此其不能建立在vector 容器上。

?

//插入和刪除push,pop（注意區分不同數據結構此操作區別）無insert操作。

//均有清空及返回數據個數的操作，無erase操作；

//返回頂或頭、尾,用top，（front，back）》》不能由迭代器訪問元素或者數組下標訪問元素

?

（1） Stacks（堆棧）
C++ Stack（堆棧）是一個容器類的改編，為程序員提供了堆棧的全部功能，—
—也就是說實現了一個先進后出（FILO）的數據結構。
1.empty() 堆棧為空則返回真
2.pop() 移除棧頂元素
3.push() 在棧頂增加元素
4.size() 返回棧中元素數目
5.top() 返回棧頂元素
（2）?C++ Queues(隊列)
C++隊列是一種容器適配器，它給予程序員一種先進先出(FIFO)的數據結構。
1.back() 返回一個引用，指向最后一個元素
2.empty() 如果隊列空則返回真
3.front() 返回第一個元素
4.pop() 刪除第一個元素
5.push() 在末尾加入一個元素
6.size() 返回隊列中元素的個數
（3）?Priority Queues(優先隊列)
C++優先隊列類似隊列，但是在這個數據結構中的元素按照一定的斷言排列有
序。（http://www.cnblogs.com/heqinghui/archive/2013/07/30/3225407.html）
1.empty() 如果優先隊列為空，則返回真
2.pop() 刪除第一個元素

3.push() 加入一個元素
4.size() 返回優先隊列中擁有的元素的個數
5.top() 返回優先隊列中有最高優先級的元素

?

#include<queue>?

#include<vector>?

//定義結構，使用運算符重載,自定義優先級1? 

struct cmp1{? 

????bool operator ()(int &a,int &b){? 

????????return a>b;//最小值優先? 

????}? 

};? 

struct cmp2{? 

????bool operator ()(int &a,int &b){? 

????????return a<b;//最大值優先? 

????}? 

};? 

//定義結構，使用運算符重載,自定義優先級2? 

struct number1{? 

????int x;? 

????bool operator < (const number1 &a) const {? 

????????return x>a.x;//最小值優先? 

????} ?

};? 

struct number2{? 

????int x;? 

????bool operator < (const number2 &a) const {? 

????????return x<a.x;//最大值優先? 

????}? 

};? 

    priority_queue<int>que;//采用默認優先級構造隊列? 

??

????priority_queue<int,vector<int>,cmp1>que1;//最小值優先? 

????priority_queue<int,vector<int>,cmp2>que2;//最大值優先? 

????priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”會被認為錯誤，? 

??????????????????????????????????????????????????????//這是右移運算符，所以這里用空格號隔開? 

????priority_queue<int,vector<int>,less<int> >que4;最大值優先? 

?