1.vector

1.1 定義

相當於是一維的變長陣列

vector<typename> name;

1.2 元素存取

• 下標存取 vi[index]
• 迭代器存取 vector<typename>::iterator it;

1.3 常用函數

• push_back(x)在vector後面新增一個元素x，時間複雜度O(1)
• pop_back()刪除vector尾元素，時間複雜度O(1)
• size()獲得vector中元素的個數，時間複雜度O(1)
• clear()清空vector中所有元素，時間複雜度O(N)，N爲元素個數
• insert(it,x)向vector的任意迭代器it處插入一個元素x，時間複雜度O(N)
• erase(it)刪除迭代器爲it處的元素，erase(first,last)刪除一個區間[first,last)內的所有元素，時間複雜度均爲O(N)

1.4 常見用途

1. 儲存數據：在元素個數不確定的場合可以很好地節省空間
2. 用鄰接表儲存圖

2.set

2.1 定義

集合，內部自動有序且不含重複元素的容器，內部使用紅黑樹實現，實現從小到大的排序功能

set<typename> name;

2.2 元素存取

只能通過迭代器存取，樹狀結構，有序

set<typename>::iterator it;

2.3 常用函數

• insert(x)將x插入set容器中，並自動遞增排序和去重，時間複雜度O(logN)
• find(value)返回set中對應值爲value的迭代器，時間複雜度爲O(logN)
• erase(it)刪除迭代器爲it處的元素，時間複雜度爲O(1)，erase(value)刪除值爲value的元素，時間複雜度爲O(logN)。erase(first,last)刪除一個區間[first,last)內的所有元素，時間複雜度均爲O(last-first)。
• size()獲得set內元素的個數，時間複雜度爲O(1)
• clear()清空set中的所有元素，時間複雜度爲O(N)

2.4 常見用途

自動去重並按升序排序

3.string

需新增#include<string>標頭檔案

3.1 定義

string str;

3.2 元素存取

• 下標存取 string型變數使用c_str()變爲字元陣列可用%s輸出
• 迭代器存取string::iterator it;

3.3 常用函數

• operator+=字串拼接
• 比較運算子比較大小，比較規則是字典序
• size()/length()返回string的長度，時間複雜度爲O(1)
• insert(pos,string)，在pos號位置插入字串string。insert(it,it2,it3)，表示待插字串[it2,it3)將被插在it的位置上。
• erase(it)刪除單個元素。erase(first,last)刪除一個區間內所有元素
• clear()清空string中的數據，時間複雜度一般爲O(1)
• substr(pos,len)返回從pos號位開始，長度爲len的子串，時間複雜度爲O(len)
• string::npos，是一個常數，本身值爲-1，但是是unsigned_int型別
• find(str)，當str是子串時，返回其在str中第一次出現的位置，如果不是，則返回string::npos。find(str2,pos)，從str的pos號位開始匹配str2，返回值與上相同。時間複雜度爲O(nm)，n和m分別爲兩個字串的長度。
• replace()，str.replace(pos,len,str2)，把str從pos號位開始、長度爲len的子串替換爲str2。str.replace(it1,it2,str2)，把str的迭代器[it1,it2)範圍的子串替換爲str2.

4.map

將任何基本型別對映到任何基本型別，內部使用紅黑樹實現，在建立對映的過程中會自動實現從小到大的排序功能。

unordered_map，以雜湊代替map內部的紅黑樹實現。

4.1 定義

map<typename1,typename2>mp;    //key是typename1，value是typename2

4.2 元素存取

• 下標存取，也就是鍵存取
• 迭代器存取map<typename1,typename2>::iterator it;使用it->first存取鍵，使用it->second存取值。

4.3 常用函數

• find(key)返回鍵爲key的對映的迭代器，時間複雜度爲O(logN)
• erase(it)，刪除迭代器爲it的元素，時間複雜度爲O(1)。erase(key)，刪除對映鍵爲key的元素，時間複雜度爲O(logN)。erase(first,last)刪除一個區間的所有元素。
• size()獲得map中對映的對數，時間複雜度爲O(1)。
• clear()清空map中的所有元素，複雜度爲O(N).

4.4 常見用途

1. 需要建立字元（或字串）與整數之間的對映
2. 判斷大整數或者其他型別數據是否存在
3. 字串和字串的對映

5.queue

先進先出的容器

5.1 定義

queue<typename> name;

5.2 元素存取

• 通過front()來存取隊首元素
• 通過back()來存取隊尾元素

5.3 常用函數

• push(x)將x入隊，時間複雜度爲O(1)
• front()、back()獲得隊首和隊尾元素，時間複雜度爲O(1)
• pop()令隊首元素出隊，時間複雜度爲O(1)
• empty()檢測queue是否爲空，返回true則空，返回false則非空，時間複雜度爲O(1)
• size()返回queue內元素的個數，時間複雜度爲O(1)

5.4 常見用途

1. 廣度優先搜尋

6.priority_queue

6.1 定義

優先佇列，底層是用堆來進行實現的，隊首元素一定是當前佇列中優先順序最高的一個。

priority_queue<typename> name;

6.2 元素存取

• 只能通過top()來存取隊首元素（堆頂元素），也就是優先順序最高的元素

6.3 常用函數

• push(x)令x入隊，時間複雜度爲O(logN)
• top()獲得隊首元素（即堆頂元素），時間複雜度爲O(1)
• pop()令隊首元素（即堆頂元素）出隊，時間複雜度爲O(logN)
• empty()檢測優先佇列是否爲空，返回true則空，返回false則非空，時間複雜度爲O(1)
• size()返回優先佇列內元素的個數，時間複雜度爲O(1)

6.4 常見用途

解決一些貪心問題，也可以對Dijkstra演算法進行優化

7.stack

後進先出的容器

7.1 定義

stack<typename> name

7.2 元素存取

通過top()存取棧頂元素

7.3 常用函數

• push(x)將x入棧，時間複雜度爲O(1)
• top()獲得棧頂元素，時間複雜度爲O(1)
• pop()彈出棧頂元素，時間複雜度爲O(1)
• empty()檢測stack內是否爲空，時間複雜度爲O(1)
• size()返回stack內元素的個數，時間複雜度爲O(1)

7.4 常見用途

模擬遞回演算法

8.pair

將兩個元素綁在一起作爲一個合成元素，可以看作一個內部有兩個元素的結構體，且這兩個元素的型別是可以指定的

struct pair{
    typeName1 first;
    typeName2 second;
};

8.1 定義

需要新增標頭檔案#include<utility>

pair<typeName1,typeName2> name;    //初始化
pair<string,int> p("haha",5);      //定義時初始化

//在程式碼中臨時構建一個pair
pair<string,int>("haha",5);    //方式一
make_pair("haha",5);           //方式二，使用自帶的make_pair函數     

8.2 元素存取

pair中只有兩個元素，分別是first和second，只需要按正常結構體的方式去存取即可。

#include<iostream>
#include<utility>
#include<string>
using namespace std;
int main(){
	pair<string,int> p;
	p.first="haha";
	p.second=5;
	cout<<p.first<<" "<<p.second<<endl;
	p=make_pair("xixi",55);
	cout<<p.first<<" "<<p.second<<endl;
	p=pair<string,int>("nene",555);
	cout<<p.first<<" "<<p.second<<endl;
	return 0;
} 

8.3 常用函數

• 使用比較運算子比較大小，比較規則是先以first大小作爲標準，只有當first相等時纔去判斷second的大小

8.4 常見用途

1. 用來代替二元結構體及其建構函式，節省編碼時間
2. 作爲map的鍵值對來進行插入

map<string,int> mp;
mp.insert(make_pair("nene",5));
mp.insert(pair<string,int>("haha",9));
for(auto it=mp.begin();it!=mp.end();it++)
	cout<<it->first<<" "<<it->second<<endl;

9.algorithm標頭檔案下常用函數

1. max(x,y)、min(x,y)返回x和y中的最大值和最小值，如果要返回三個數的最大值，可使用max(x,max(y,z))
2. abs(x)返回整數x的絕對值，浮點型的絕對值用math標頭檔案下的fabs
3. swap(x,y)交換x和y的值
4. reverse(it,it2)將陣列指針在[it,it2)之間的元素或容器的迭代器在[it,it2)範圍內的元素進行反轉
5. next_permutation()給出一個序列在全排列中的下一個序列
6. fill(起始位置，終止位置的下一個位置，值)把陣列或容器的某一段區間賦爲某個相同的值，和memset不同，這裏的賦值可以是任意值
7. lower_bound()和upper_bound()需要用在一個有序陣列或容器中；lower_bound(first,last,val)用來尋找[first,last)範圍內第一個大於等於val元素的位置，如果是陣列則返回指針，如果是容器則返回迭代器；upper_bound(first,last,val)用來尋找第一個值大於val的元素的位置。
8. sort(首元素地址，尾元素的下一個地址，比較函數)，預設按遞增排序，整型浮點型char型陣列都可

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

struct node{
	int x,y;
	node(){}
	node(int _x,int _y){
		x=_x;
		y=_y;
	}
}ssd[10];

bool cmp(node a,node b){
	if(a.x!=b.x) return a.x>b.x;
	else return a.y>b.y;
}

bool cmp2(int a,int b){
	return a>b;
}

int main(){
	//結構體排序 
	ssd[0]=node(2,2);
	ssd[1]=node(1,3);
	ssd[2]=node(2,1);
	sort(ssd,ssd+3,cmp);
	for(int i=0;i<3;i++){
		printf("%d %d\n",ssd[i].x,ssd[i].y);
	}
	
	//容器的排序，只有vector、string、deque是可以使用sort的
	//因爲set、map這種容器底層是用紅黑樹實現的，元素本身有序，不允許使用sort排序
	vector<int> vi{1,9,1,0};
	vi.push_back(3);
	vi.push_back(8);
	vi.push_back(6);
	sort(vi.begin(),vi.end(),cmp2);
	for(int i=0;i<vi.size();i++)
		printf("%d ",vi[i]); 
	return 0;
}