快考CSP了，C/C++玩家的福利來了

首先介紹下，什么是STL，STL，Standard Template Library的縮寫，標準模版庫的意思，STL是一些“容器”的集合，這些容器包括list、 vector、set、queue等，

PS:這里說明下，文中出現的DataType指資料型別，DataName指變數名，cmp指一個回傳型別為bool的比較函式

iterator 迭代器：

要訪問順序容器和關聯容器中的元素，需要通過“迭代器（iterator）”進行，迭代器是一個變數，相當于容器和操縱容器的演算法之間的中介，迭代器可以指向容器中的某個元素，通過迭代器就可以讀寫它指向的元素，從這一點上看，迭代器和指標類似，

迭代器按照定義方式分成以下四種，

1. 正向迭代器，定義方法如下：
   容器類名::iterator 迭代器名;

2. 常量正向迭代器，定義方法如下：
   容器類名::const_iterator 迭代器名;

3. 反向迭代器，定義方法如下：
   容器類名::reverse_iterator 迭代器名;

4. 常量反向迭代器，定義方法如下：
   容器類名::const_reverse_iterator 迭代器名;

迭代器用法示例會在后邊不同容器示例中展示，

vector 動態陣列

所謂動態陣列，就是不定長陣列，

頭檔案：#include<vector>

宣告：vector<DataType> DataName;

基本操作：

• push_back();，在最后面插入一個新元素
• size()，回傳vector的長度
• clear()，清空vector
• 可以像陣列一樣使用，

例子：

vector<int> vec;	//空的
vec.push_back(0);	//有0
vec.push_back(1);	//有0，1
vec.push_back(2);	//有0，1，2
//兩種遍歷方法
for(int i=0; i<vec.size(); i++){
	printf("%d\n",vec[i]);
}
for(vector<int>::iterator it=vec.begin(); it!=vec.end(); it++){
	printf("%d\n",*it);//迭代器訪問
}

vec[1]=3;	//變成0，3，3
vec[2]=2;	//變成0，3，2

vec.clear();//清空

stack 堆疊

先進后出的資料結構（FILO）

頭檔案：#include<stack>

宣告：stack<DataType> DataName;

基本操作：

• push()，入堆疊
• pop()，出堆疊
• top()，訪問堆疊頂元素
• empty()，判斷堆疊空
• size()，回傳堆疊中元素個數

例子：

s.push(1);	//{1}
s.push(233);	//{233,1}
s.push(666);	//{666,233,1}
cout<<s.top()<<endl;	//輸出堆疊頂666
cout<<s.size()<<endl;	//輸出堆疊中元素個數3
s.pop();	//{233,1}
s.push(2);	//{2,233,1} 

queue 單向佇列

先進先出的資料結構（FIFO）

頭檔案：#include<queue>

宣告：queue<DataType> DataName;

基本操作：

• push()，入隊
• pop()，出隊
• front()，訪問隊首元素
• back()，訪問隊尾元素
• empty()，判斷隊空
• size()，回傳佇列元素個數

例子：

int e,m,n;
queue<int> q1;
for(int i=0;i<10;i++)
	q.push(i);	//入隊 
//[0,1,2,3,4,5,6,7,8,9]
if(!q1.empty())
	cout<<"no empty\n";
n=q1.size();	//n=10
m=q1.back();	//m=9
for(int i=0;i<n;i++){
	e=q1.front();	//取隊首元素
	cout<<e<<" ";
	q1.pop();	//出隊 
}
cout<<endl;
if(q1.empty())
	cout<<"queue is empty"; 

set 集合

集合中不會存在重復元素，支持高效的插入、洗掉和查詢操作，復雜度均是O(logn)（對比使用陣列來實作，雖然插入的時間復雜度O(1)，但是洗掉和查詢的時間復雜度卻是O(n)），

頭檔案：#include<set>

宣告：set<DataType> DataName;

基本操作：

• begin()，回傳set第一個元素（型別為迭代器，或者說指標）
• end()，回傳set最后一個元素（同上）
• clear()，清空set中的元素
• empty()，判斷set是否為空
• insert()，插入一個元素
• erase()，洗掉一個元素
• find()，查找一個元素，回傳為迭代器
• size()，回傳set的元素個數

例子：

set<int> s;
set<int>::iterator it;

s.insert(1);	//{1}
s.insert(2);	//{1,2}
s.insert(3);	//{1,2,3}
s.insert(1);	//{1,2,3}
s.erase(1);		//{2,3}

it=s.find(2);	//查找元素2，若未找到，回傳s.end() 

map 映射

從一個元素映射到另一個元素的資料結構，hash是他的一種，

頭檔案：#include<map>

宣告：map<DataTypeA,DataTypeB> DataName;從DataTypeA映射到DataTypeB

基本操作：

• 可以像陣列一樣使用
• 迭代器有兩個屬性，first代表key，second代表value
• count()，判斷是否存在映射
• clear()，清空map

例子：

map<string,int> dict;	//{}
dict["Tom"]=1;	//{"Tom":1}
dict["Jone"]=2;	//{"Tom":1,"Jone":2}
dict.insert(map<string,int>::value_type("Mary",1));
// //{"Tom":1,"Jone":2,"Mary":1}
if(dict.count("Mary")){
	printf("Mary存在");
} else{
	printf("Mary不存在");
}
//迭代器訪問 
for(map<string,int>::iterator it=dict.begin(); it!=dict.end(); it++){
	cout<<it->first<<":"<<it->second<<endl;
}

priority_queue 優先佇列

實質就是二叉堆，使用該模版可以快速實作小根堆、大根堆，插入、洗掉、查詢的時間復雜度均是O(logn)，

頭檔案：#include<priority_queue>

宣告： 默認小根堆，priority_queue<DataType> DataName;

自定義比較函式，priority_queue<DataType，vector<DataType>,cmp> DataName;

基本操作：

• push()，隊尾插入元素
• pop()，取出隊首元素
• top()，訪問隊首元素
• size()，獲取佇列長度
• clear()，清空佇列

例子：

struct cmp{
	bool operator() (const int &a,const int &b){//&參考 
		return a>b;	//最大堆 
	} 
};

priority_queue<int,vector<int>,cmp> q;//[]
q.push(2); //[2]
q.push(1); //[2,1]
q.push(3); //[3,2,1]

for(int i=0;i<q.size();i++){
	printf("%d\n",q.top());//逐個輸出隊首
	q.pop();//出隊 
}

sort 快排函式

頭檔案：#include<algorithm>

sort(begin,end,cmp);//begin為序列開始地址，end序列結束地址，cmp比較函式,cmp可以不填，默認升序

陣列排序：

int a[4]={2,4,3,1};
int n=4;
sort(a,a+n);

vector排序：

sort(vec.begin(),vec.end());

結構體排序：

struct Point{
	int x,y;
}p[4]={{1,2},{1,0},{2,1},{0,1}}; 

bool cmp(Point a,Point b){
	//比較函式，x為主關鍵字升序，y為次關鍵字升序 
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

int main(){
	sort(p,p+4,cmp);
	return 0;
}