STL是提高C++編寫效率的一個利器

C++幫我們實(shí)現(xiàn)好了很多有用的函數(shù)，我們要避免重復(fù)造輪子

1.?#include <vector> // 允許比較運(yùn)算 字典序

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

1.1 聲明

1.2 size/empty

size函數(shù)返回vector的實(shí)際長度（包含的元素個數(shù)），empty函數(shù)返回一個bool類型，表明vector是否為空。二者的時間復(fù)雜度都是 O(1)所有的STL容器都支持這兩個方法，含義也相同，之后我們就不再重復(fù)給出。

1.3 clear

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

1.4 迭代器

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

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

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

1.5 begin/end

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

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

下面兩份代碼都遍歷了vector<int> a，并輸出它的所有元素。

1.6 front/back

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

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

1.7 push_back()和pop_back()

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

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

備注：vector是如何實(shí)現(xiàn)動態(tài)增長空間的呢？

是基于倍增的思想，數(shù)組不夠用的時候多開一半數(shù)組，把已有的拷貝下來再加新的，所以效率要慢一半，但（n/2 + n/4 + n/8...）< n ，所以vector在數(shù)組結(jié)尾插入刪除是O(1) 的，在數(shù)組開頭插入刪除是O(n) 的。

2. #include <queue>

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

2.1 聲明

2.2 循環(huán)隊列queue

2.3 優(yōu)先隊列priority_queue

備注：棧、隊列、優(yōu)先隊列無clear()函數(shù)，其他容器都有，想清空隊列重新初始化一下即可：

q = queue<int>();

3. #include <stack>

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

4. #include <deque>

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

5. #include <set>

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

5.1 聲明

5.2 size/empty/clear

5.3 迭代器

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

設(shè)it是一個迭代器，例如set<int>::iterator it;

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

5.4 begin/end

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

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

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

5.5 insert

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

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

5.6 find

s.find(x)在集合s中查找等于x的元素，并返回指向該元素的迭代器。若不存在，則返回s.end()。時間復(fù)雜度為 O(logn)? ?// if (a.find(x) == a.end()) 可以判斷x在a中是否存在

5.7 lower_bound/upper_bound // 支持二分

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

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

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

5.8 erase

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

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

5.9 count

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

備注：

6. #include <map>

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

6.1 聲明

6.2 size/empty/clear/begin/end

均與set類似。

6.3 insert/erase

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

6.4 find

h.find(x)在變量名為h的map中查找key為x的二元組。// a.find("wlc") == a.end()

6.5 []操作符

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

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

備注：

1. 位運(yùn)算

常用操作：

1. 求x的第k位數(shù)字 x >> k & 1

2. lowbit(x) = x & -x，返回x的最后一位1

-x 等價于 ~a+1 // 補(bǔ)碼

2. 常用庫函數(shù)? #include <algorithm>

2.1 reverse翻轉(zhuǎn) O(n)

翻轉(zhuǎn)一個vector：

翻轉(zhuǎn)一個數(shù)組，元素存放在下標(biāo)1 ~ n：

2.2 unique去重

返回去重（只去掉相鄰的相同元素）之后的尾迭代器（或指針），仍然為前閉后開，即這個迭代器是去重之后末尾元素的下一個位置。該函數(shù)常用于離散化，利用迭代器（或指針）的減法，可計算出去重后的元素個數(shù)。

把一個vector去重：

把一個數(shù)組去重，元素存放在下標(biāo)1 ~ n：

2.3 random_shuffle隨機(jī)打亂

用法與reverse相同。

2.4 sort

對兩個迭代器（或指針）指定的部分進(jìn)行快速排序?？梢栽诘谌齻€參數(shù)傳入定義大小比較的函數(shù)，或者重載“小于號”運(yùn)算符。

把一個int數(shù)組（元素存放在下標(biāo)1 ~ n）從大到小排序，傳入比較函數(shù)：

把自定義的結(jié)構(gòu)體vector排序，還可以在結(jié)構(gòu)體內(nèi)重載“小于號”運(yùn)算符：

2.5 lower_bound/upper_bound 二分

lower_bound的第三個參數(shù)傳入一個元素x，在兩個迭代器（指針）指定的部分上執(zhí)行二分查找，返回指向第一個大于等于x的元素的位置的迭代器（指針）。

upper_bound的用法和lower_bound大致相同，唯一的區(qū)別是查找第一個大于x的元素。當(dāng)然，兩個迭代器（指針）指定的部分應(yīng)該是提前排好序的。

在有序int數(shù)組（元素存放在下標(biāo)1 ~ n）中查找大于等于x的最小整數(shù)的下標(biāo)：

在有序vector<int>中查找小于等于x的最大整數(shù)（假設(shè)一定存在）：