算法笔记：C++ STL（二）
内容来源：刘汝佳《算法竞赛入门经典（第2版）》
一、基础知识
1. 排序与检索
内容略，注意待排序/查找的元素可以放在数组里，也可以放在vector里。
2. 不定长数组Vector
（1） vector是一个模板类，
声明：vector<数据类型>不定长数组名 ---- 相当于一维数组
vector<数据类型> 不定长数组名 ---- 相当于二维数组
例如：vector<int>a相当于inta[]; vector<string> a相当于stringa[];
看上去像“一等公民”，因为它们可以直接赋值，还可以作为函数参数或返回值，而无需像传递数组那样用另外一个变量指定元素个数。
（2） 常用操作（这里假设a是一个vector）：
① a.size() 读取不定长数组大小
② a.resize() 改变不定长数组大小
③ a.push_back() 向不定长数组尾部添加元素
④ a.pop_back() 删除不定长数组的最后一个元素
⑤ a.clear() 清空不定长数组
3. 集合（Set）、映射（Map）
内容略
4. 栈（Stack）、队列（Queue）与优先队列（PriorityQueue）
（1） 栈：
1°定义：符合“后进先出”（LIFO）的数据结构。注意包含<stack>头文件。
2°声明：stack<T>s; 声明一个元素类型为T的栈。
3°常用操作（这里假设s是一个栈）：
① s.push(x) 将元素x入栈
② s.pop() 将栈顶元素出栈
③ s.top() 取栈顶元素（但不删除），可用于输出
④ s.empty() 判断栈s是否为空，返回true或false
⑤ s.size() 返回栈s中的元素个数
例：
#include <iostream> #include <stack> using namespace std; stack<int> s; int main() { int i; for(i=1;i<=10;i++) //1-10入栈s s.push(i); cout<<s.size()<<endl; if(!s.empty()) //当前栈s不为空 cout<<"Not empty!"<<endl; else cout<<"Empty"<<endl; while(!s.empty()) //取栈顶元素并清空栈 { cout<<s.top()<<endl; s.pop(); } if(!s.empty()) //当前栈s为空 cout<<"Not empty!"<<endl; else cout<<"Empty!"<<endl; return 0; }（2） 队列：
1°定义：符合“先进先出”（FIFO）的数据结构。注意包含<queue>头文件。
2°声明：queue<T>s; 声明一个元素类型为T的队列。
3°常用操作（这里假设s是一个队列）：
① s.push(x) 在队尾加入一个元素
② s.pop() 从队头删除一个元素
③ s.front() 返回队首（第一个）元素，可用于输出
④ s.back() 返回队尾（最后一个）元素，可用于输出
⑤ s.empty() 判断队列s是否为空，返回true或false
⑥ s.size() 返回队列s中的元素个数
例1：
#include <iostream> #include <queue> using namespace std; queue<int> q; int main() { int i; for(i=1;i<=10;i++) //1-10入队列q q.push(i); cout<<q.size()<<endl; while(!q.empty()) //取队首元素并清空栈 { cout<<q.front()<<endl; q.pop(); } if(!q.empty()) //当前队列q为空 cout<<"Not empty!"<<endl; else cout<<"Empty!"<<endl; return 0; } 例2： #include <iostream> #include <cstring> #include <queue> using namespace std; int main() { queue<string> q; q.push("red"); //4个字符串依次进队 q.push("yellow"); q.push("yellow"); q.push("blue"); cout<<q.front()<<endl; //输出当前队首元素red q.pop(); //并将其出队 cout<<q.front()<<endl; //输出当前队首元素yellow q.pop(); //并将其出队 cout<<q.front()<<endl; //输出当前队首元素yellow q.pop(); //并将其出队 q.push("green"); //字符串green进队 cout<<q.front()<<endl; //输出当前队首元素blue q.pop(); //并将其出队 cout<<q.front()<<endl; //输出当前队首元素green return 0; }（3） 优先队列
1°定义：是一种抽象数据类型ADT，行为有些像队列，但先出队列的元素不是先进队列的元素，而是队列中优先级最高的元素。（这样就可以允许类似于“急诊病人插队”这样的事情发生）注意包含<queue>头文件。
2°声明：priority_queue<T>pq; 声明一个元素类型为T的优先队列。
当T为int型时，这个pq是一个“越小的整数优先级越低的优先队列”。
由于出队的元素并不是最先进队的元素，出队的方法由queue的front()变为top()。
3°常用操作（这里假设s是一个队列）：
① pq.push(x) 在队尾加入一个元素
② pq.pop() 删除优先队列中的第一个元素
③ pq.top() 返回一个引用，指向优先队列中有最高优先级的元素（但不删除）。
④ pq.empty() 判断优先队列pq是否为空，返回true或false
⑤ pq.size() 返回优先队列pq中的元素个数
4°自定义类型priority_queue：
也可以组成优先队列，不过要为每个元素定义一个优先级。这个优先级并不需要一个确定的数字，只需要能比较大小即可。
例如：1°°越小的整数优先级越大的优先队列：
priority_queue<int, vector<int>,greater<int> > pq;
2°°个位数大的整数优先级反而小的优先队列：
priority_queue<int, vector<int>,cmp> pq;
其中cmp定义如下：
struct cmp { bool operator(const int a,const int b)const { return (a>b); } };
二、典例
1. 大理石在哪儿
现有N个大理石，每个大理石上写了一个非负整数。首先把各数从小到大排序，然后回答Q个问题。每个问题问是否有一个大理石写着某个整数x，如果是，还要回答哪个大理石上写着x。排序后的大理石从左到右编号为1~N。(在样例中，为了节约篇幅，所有大理石的数合并到一行，所有问题也合并到一行。)
样例输入：
4 1
2 3 5 1
5
5 2
1 3 3 3 1
2 3
样例输出：
CASE# 1：
5 found at 4
CASE# 2：
2 not found
3 found at 3
【分析】先排序，后（二分）查找。可使用STL sort+lower_bound函数完成。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int N,Q,x; int marble[100005]; int main() { int i,ncase=1; int index; while(scanf("%d %d",&N,&Q)!=EOF) { for(i=0;i<N;i++) scanf("%d",&marble[i]); sort(marble,marble+N); printf("CASE# %d:\n",ncase++); for(i=0;i<Q;i++) { scanf("%d",&x); index=lower_bound(marble,marble+N,x)-marble; //在已排序数组中寻找x，返回>=x的第一个元素的位置 if(marble[index]==x) printf("%d found at %d\n",x,index+1); else printf("%d not found\n",x); } } return 0; }