c++STL急急急

vector

頭文件

#include <vector>

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

擴(kuò)容過(guò)程

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

用法：

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

size/empty

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

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

clear

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

迭代器

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

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

vector<int>::iterator it;

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

begin/end

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

所有的容器都可以視作一個(gè)“前閉后開(kāi)”的結(jié)構(gòu)，end函數(shù)返回vector的尾部，即第n個(gè)元素再往后的“邊界”。*a.end()與a[n]都是越界訪問(wè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的第一個(gè)元素，等價(jià)于*a.begin() 和 a[0]。

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

push_back() 和 pop_back()

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

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

queue

頭文件

#include <queue>

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

?

用法

queue<int> q;struct rec{…}; queue<rec> q;      //結(jié)構(gòu)體rec中必須定義小于號(hào)priority_queue<int> q;        // 大根堆priority_queue<int, vector<int>, greater<int> q;     // 小根堆
priority_queue<pair<int, int>>q;

循環(huán)隊(duì)列 queue

用法

? push 從隊(duì)尾插入

? pop 從隊(duì)頭彈出

? front 返回隊(duì)頭元素

? back 返回隊(duì)尾元素

優(yōu)先隊(duì)列 priority_queue

用法

? push 把元素插入堆

? pop 刪除堆頂元素

? top 查詢(xún)堆頂元素（最大值）

stack

頭文件

#include

頭文件stack包含棧。聲明和前面的容器類(lèi)似。

push 向棧頂插入

pop 彈出棧頂元素

deque

頭文件

#include <deque>

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

由于deque需要處理內(nèi)部跳轉(zhuǎn)，因此速度上沒(méi)有vector快

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

deque中控器：

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

用法

[] 隨機(jī)訪問(wèn)

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

front/back 隊(duì)頭/隊(duì)尾元素

push_back 從隊(duì)尾入隊(duì)

push_front 從隊(duì)頭入隊(duì)

pop_back 從隊(duì)尾出隊(duì)

pop_front 從隊(duì)頭出隊(duì)

clear 清空隊(duì)列

set

頭文件

#include <set>

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

用法

set<int> s;struct rec{…}; 
set<rec> s;     // 結(jié)構(gòu)體rec中必須定義小于號(hào)multiset<double> s;size/empty/clear
與vector類(lèi)似

迭代器

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

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

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

begin/end

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

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

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

insert

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

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

find

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

lower_bound/upper_bound

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

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

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

erase

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

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

count

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

map

頭文件

? #include <map>

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

用法

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類(lèi)似。

Insert/erase

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

find

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

[]操作符

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

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

bitset

頭文件

#include<bitset>

用法

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

續(xù)表

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

array

頭文件

#include<array>

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

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