c++STL急急急

vector

頭文件

#include <vector>

vector是變長數(shù)組，支持隨機訪問，不支持在任意位置O(1)插入。為了保證效率，元素的增刪一般應該在末尾進行。

擴容過程

如果集合已滿，在新增數(shù)據(jù)的時候，就要分配一塊更大的內存，將原來的數(shù)據(jù)復制過來，釋放之前的內存，在插入新增的元素
所以對vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效了

用法：

#include <vector>      頭文件vector<int> a;              相當于一個長度動態(tài)變化的int數(shù)組
vector<int> b[233];     相當于第一維長233，第二位長度動態(tài)變化的int數(shù)組struct rec{…};
vector<rec> c;             自定義的結構體類型也可以保存在vector中

size/empty

size函數(shù)返回vector的實際長度（包含的元素個數(shù)），empty函數(shù)返回一個bool類型，表明vector是否為空。二者的時間復雜度都是O(1)。

所有的STL容器都支持這兩個方法，含義也相同，之后我們就不再重復給出。

clear

clear函數(shù)把vector清空。

迭代器

迭代器就像STL容器的“指針”，可以用星號“*”操作符解除引用。

一個保存int的vector的迭代器聲明方法為：

vector<int>::iterator it;

vector的迭代器是“隨機訪問迭代器”，可以把vector的迭代器與一個整數(shù)相加減，其行為和指針的移動類似?？梢园裿ector的兩個迭代器相減，其結果也和指針相減類似，得到兩個迭代器對應下標之間的距離。

begin/end

begin函數(shù)返回指向vector中第一個元素的迭代器。例如a是一個非空的vector，則*a.begin()與a[0]的作用相同。

所有的容器都可以視作一個“前閉后開”的結構，end函數(shù)返回vector的尾部，即第n個元素再往后的“邊界”。*a.end()與a[n]都是越界訪問，其中n=a.size()。

下面兩份代碼都遍歷了vectora，并輸出它的所有元素。

for (int I = 0; I < a.size(); I ++) cout << a[i] << endl;for (vector<int>::iterator it = a.begin(); it != a.end(); it ++) cout << *it << endl;

front/back

front函數(shù)返回vector的第一個元素，等價于*a.begin() 和 a[0]。

back函數(shù)返回vector的最后一個元素，等價于*==a.end() 和 a[a.size() – 1]。

push_back() 和 pop_back()

a.push_back(x) 把元素x插入到vector a的尾部。

b.pop_back() 刪除vector a的最后一個元素。

queue

頭文件

#include <queue>

頭文件queue主要包括循環(huán)隊列queue和優(yōu)先隊列priority_queue兩個容器。

?

用法

queue<int> q;struct rec{…}; queue<rec> q;      //結構體rec中必須定義小于號priority_queue<int> q;        // 大根堆priority_queue<int, vector<int>, greater<int> q;     // 小根堆
priority_queue<pair<int, int>>q;

循環(huán)隊列 queue

用法

? push 從隊尾插入

? pop 從隊頭彈出

? front 返回隊頭元素

? back 返回隊尾元素

優(yōu)先隊列 priority_queue

用法

? push 把元素插入堆

? pop 刪除堆頂元素

? top 查詢堆頂元素（最大值）

stack

頭文件

#include

頭文件stack包含棧。聲明和前面的容器類似。

push 向棧頂插入

pop 彈出棧頂元素

deque

頭文件

#include <deque>

雙端隊列deque是一個支持在兩端高效插入或刪除元素的連續(xù)線性存儲空間。它就像是vector和queue的結合。與vector相比，deque在頭部增刪元素僅需要O(1)的時間；與queue相比，deque像數(shù)組一樣支持隨機訪問。

由于deque需要處理內部跳轉，因此速度上沒有vector快

deque是?個雙端開?的連續(xù)線性空間，其內部為分段連續(xù)的空間組成，隨時可以增加?段
新的空間并鏈接

deque中控器：

deque是由?段?段的定量連續(xù)空間構成。?旦有必要在其頭端或者尾端增加新的空間，便
配置?段定量連續(xù)空間，串接在整個deque的頭端或者尾端

用法

[] 隨機訪問

begin/end，返回deque的頭/尾迭代器

front/back 隊頭/隊尾元素

push_back 從隊尾入隊

push_front 從隊頭入隊

pop_back 從隊尾出隊

pop_front 從隊頭出隊

clear 清空隊列

set

頭文件

#include <set>

頭文件set主要包括set和multiset兩個容器，分別是“有序集合”和“有序多重集合”，即前者的元素不能重復，而后者可以包含若干個相等的元素。set和multiset的內部實現(xiàn)是一棵紅黑樹，它們支持的函數(shù)基本相同。

用法

set<int> s;struct rec{…}; 
set<rec> s;     // 結構體rec中必須定義小于號multiset<double> s;size/empty/clear
與vector類似

迭代器

set和multiset的迭代器稱為“雙向訪問迭代器”，不支持“隨機訪問”，支持星號(*)解除引用，僅支持”++”和–“兩個與算術相關的操作。

設it是一個迭代器，例如set::iterator it;

若把it++，則it會指向“下一個”元素。這里的“下一個”元素是指在元素從小到大排序的結果中，排在it下一名的元素。同理，若把it–，則it將會指向排在“上一個”的元素。

begin/end

返回集合的首、尾迭代器，時間復雜度均為O(1)。

? s.begin() 是指向集合中最小元素的迭代器。

s.end() 是指向集合中最大元素的下一個位置的迭代器。換言之，就像vector一樣，是一個“前閉后開”的形式。因此–s.end()是指向集合中最大元素的迭代器。

insert

? s.insert(x)把一個元素x插入到集合s中，時間復雜度為O(logn)。

? 在set中，若元素已存在，則不會重復插入該元素，對集合的狀態(tài)無影響。

find

s.find(x) 在集合s中查找等于x的元素，并返回指向該元素的迭代器。若不存在，則返回s.end()。時間復雜度為O(logn)。

lower_bound/upper_bound

? 這兩個函數(shù)的用法與find類似，但查找的條件略有不同，時間復雜度為 O(logn)。

s.lower_bound(x) 查找大于等于x的元素中最小的一個，并返回指向該元素的迭代器。

s.upper_bound(x) 查找大于x的元素中最小的一個，并返回指向該元素的迭代器。

erase

設it是一個迭代器，s.erase(it) 從s中刪除迭代器it指向的元素，時間復雜度為O(logn)

設x是一個元素，s.erase(x) 從s中刪除所有等于x的元素，時間復雜度為O(k+logn)，其中k是被刪除的元素個數(shù)。

count

? s.count(x) 返回集合s中等于x的元素個數(shù)，時間復雜度為 O(k +logn)，其中k為元素x的個數(shù)。

map

頭文件

? #include <map>

map容器是一個鍵值對key-value的映射，其內部實現(xiàn)是一棵以key為關鍵碼的紅黑樹。Map的key和value可以是任意類型，其中key必須定義小于號運算符。

用法

map<key_type, value_type> name;

? 例如：

? map<long, long, bool> vis;

? map<string, int> hash;

? map<pair<int, int>, vector> test;

? size/empty/clear/begin/end均與set類似。

Insert/erase

? 與set類似，但其參數(shù)均是pair<key_type, value_type>。

find

? h.find(x) 在變量名為h的map中查找key為x的二元組。

[]操作符

? h[key] 返回key映射的value的引用，時間復雜度為O(logn)。

[]操作符是map最吸引人的地方。我們可以很方便地通過h[key]來得到key對應的value，還可以對h[key]進行賦值操作，改變key對應的value。

bitset

頭文件

#include<bitset>

用法

代碼	含義
bitset < n >a;	a有n位，每位都為0
bitset < n >a(b);	a是unsigned long型u的一個副本
bitset < n >a(s);	a是string對象s中含有的位串的副本
bitset < n >a(s,pos,n);	a是s中從位置pos開始的n個位的副本
b.any()	b中是否存在置為1的二進制位，有 返回true
b.none()	b中是否沒有1，沒有 返回true
b.count()	b中為1的個數(shù)
b.size()	b中二進制位的個數(shù)

續(xù)表

代碼	含義
b.test(pos)	測試b在pos位置是否為1，是 返回true
b[pos]	返回b在pos處的二進制位
b.set()	把b中所有位都置為1
b.set(pos)	把b中pos位置置為1
b.reset()	把b中所有位都置為0
b.reset(pos)	把b中pos位置置為0
b.flip()	把b中所有二進制位取反
b.flip(pos)	把b中pos位置取反
b.to_ulong()	用b中同樣的二進制位返回一個unsigned long值

array

頭文件

#include<array>

array是C++11新增的容器，效率與普通數(shù)據(jù)相差無幾，比vector效率要高，自身添加了一些成員函數(shù)。

和其它容器不同，array 容器的大小是固定的，無法動態(tài)的擴展或收縮，只允許訪問或者替換存儲的元素。