容器的分类
STL容器分为顺序式容器和关联式容器。
顺序式容器：包括vector、list、deque、queue、priority_queue、stack等。
(1) vector: 动态数组，从末尾能快速插入与删除，直接访问任何元素。
(2) list: 双链表，从任何地方快速插入与删除。
(3) deque: 双向队列，从前面或后面快速插入与删除，直接访问任何元素。
(4) priority_queue: 优先队列，最高优先级元素总是第一个出列。
(5) stack: 栈，后进先出。
**关联式容器:**包括set、multiset、map、multimap等。
(1) set: 集合，快速查找，不允许重复值。
(2) multiset: 快速查找，允许重复值。
(3) map: 一对一映射，基于关键字快速查找，不允许重复值。
(4) multimap: 一对多映射，基于关键字快速查找，允许重复值。
vector
定义
数组是基本的数据结构，有静态数组和动态数组两种类型。在算法竞赛中，编码的惯例是：如果空间足够，能用静态数组就用静态数组，而不用指针管理动态数组，这样编程比较简单并且不会出错；如果空间紧张，可以用STL的vector建立动态数组，不仅节约空间，而且也不易出错。
vector是STL的动态数组，在运行时能根据需要改变数组大小。由于它以数组形式存储，也就是说它的内存空间是连续的，所以索引可以在常数时间内完成，但是在中间进行插入和删除操作会造成内存块的复制。另外，如果数组后面的内存空间不够，需要重新申请一块足够大的内存。这些都会影响vector的效率。
vector容器是一个模板类，能存放任何类型的对象。
// 定义int型数组
vector <int> a; //默认初始，a为空
vector <int> b(a); // 用a定义b
vector <int> a(100); // a有100个值为0的元素
vector <int> a(100,6); // 100个值为6的元素
// 定义string型数组
vector <string> a(10,"null"); // 10个值为"null"的元素
vector <string> vec(10,"hello"); // 10个值为"hello"的元素
vector <string> b(a.begin(), a.end()); // b是a的复制
// 定义结构型数组
struct point {int x,y;};
vector <point> a; // a用来存坐标
//定义二维数组
vector <int> a[MAXN]; // 它的第一维大小是固定的MAXN，第二维是动态的。用这个方式可以实现图的邻接表存储。
常用操作
// vector 常用操作
a.push_back(100); // 赋值,在尾部添加元素
int size = a.size(); // 元素个数
bool isEmpty = a.empty(); // 判断是否为空
cout << a[0] << endl; // 打印第一个元素
a.insert(a.begin()+i, k); // 中间插入：在第 i 个位置插入元素 k
a.push_back(8); // 尾部插入，在尾部插入值为8的元素
a.insert(a.end(),10,5); // 尾部插入.在尾部插入10个值为5的元素
a.pop_back(); // 删除尾部元素
a.erase(a.begin()+i,a.begin()+j); // 删除区间 [i,j) 的元素
a.erase(a.begin()+i); // 删除第 i 个元素
a.resize(n); // 数组大小变为n
a.clear(); // 清空数组
reverse(a.begin(), a.end()); // 用函数reverse() 翻转数组例子
圆桌问题
圆桌边围坐着2n个人。其中n个人是好人，另外n个人是坏人。从第一个人开始数，数到第m个人，立即赶走该人；然后从被赶走的人之后开始数，再将数到的第m个人赶走，依次方法不断赶走围坐在圆桌边的人。
预先应如何安排这些好人与坏人的座位，才能使得在赶走n个人之后圆桌边围坐的剩余的n个人全都是好人?
输入： 多组数据，每组数据输入：n,m<327467
输出： 对于每一组数据，输出2n个大写字母，“G”表示好人，“B”表示坏人，50个字母为一行，不允许出现空白字符。相邻数据间留有一个空行。
输入样例：
2 3
2 4
输出样例：
GBBG
BGGB
这个题目是约瑟夫问题。想要根据n和m来计算一开始的顺序很是困难，不如先假设桌子上的都是好人，然后按照规则踢人，把踢下的人都标记为坏人。
程序如下：
#include <bits/stdc++.h>
using namespace std;
int main(){
vector<int> table;
int n , m;
while(cin>>n>>m){
table.clear();
for(int i = 0; i<2*n; i++) table.push_back(i); //初始化
int pos = 0; //记录当前位置
for(int i = 0; i<n; i++){ //赶走n个人
pos = (pos + m -1) % table.size(); //计算下一个要赶走的人
table.erase(table.begin() + pos); //赶走这个人,table数减一
}
int j = 0;
for(int i = 0; i<2*n; i++){
if(!(i%50)&&i) cout<<endl; //每50个数换行
if(j < table.size() && i==table[j]){ //table 留下的都是好人
j++;
cout<< "G";
}else{
cout<< "B"; //赶走的都是坏人
}
}
cout<< endl<<endl; //留一个空行
}
return 0;
}
前面提到，vector插入或删除中间某一项时需要线性时间，即需要把这个元素后面的所有元素往后移或往前移，复杂度是O(n).如果频繁移动，则效率很低。上述代码中的erase()来删除中间元素就有这个问题。
栈stack
栈是基本的数据结构之一，特点是“先进后出”。例如乘坐电梯时，先进电梯的最后出去；一盒泡腾片，最先放进赫兹的药片位于最底层，最后被拿出来。
头文件：# include
栈的有关操作：
// 定义栈
stack <int> s;
stack <float> f;
stack <char> c;
s.push(item); // 将item放到栈顶
s.top(); // 返回栈顶元素，但不会删除
s.pop(); // 产出栈顶元素，但不会返回
s.size(); // 返回栈中元素个数
s.empty(); // 检查栈是否为空，如果为空，返回true，否则返回false例子
翻转字符串
翻转字符串。例如输入”olleh !dlrow”,输出”hello world!”。
用栈模拟，下面是程序:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
char ch;
scanf("%d", &n);
getchar();
while(n--){
stack <char> s;
while (true)
{
ch = getchar();
if(ch == ' ' || ch == '\n' || ch == EOF){
while (!s.empty())
{
printf("%c", s.top());
s.pop();
}
if(ch == '\n' || ch == EOF) break;
printf(" ");
}
else s.push(ch); // 入栈
}
printf("\n");
}
return 0;
}爆栈问题
栈需要用空间存储，如果深度太大，或者存进栈的数组太大，那么总数会超过系统为栈分配的空间，这样就会爆栈，即栈溢出。其解决方法有下面两种：
（1）在程序中调大系统的栈，这种方法依赖于系统和编译器。
（2）手工写栈。
队列queue
队列是基本的数据结构之一，特点是“先进先出”。例如排队，先进队列的先得到服务。
头文件是：# include
队列的有关操作：
// 定义队列
queue <int> q;
queue <float> f;
queue <char> c;
q.push(item); // 把item放到队尾
q.front(); // 返回队首元素，但不会删除元素
q.pop(); // 删除队首元素
q.back(); // 返回队尾元素
q.size(); // 返回元素个数
q.empty(); // 检车队列是否为空例子
模拟栈和队列，栈是FILO，队列是FIFO。
#include <bits/stdc++.h>
using namespace std;
int main(){
int t, n , temp;
cin >> t;
while (t--){
string str,str1;
queue<int> Q;
stack<int> S;
cin>>n>>str;
for(int i = 0; i<n; i++){
if(str=="FIFO"){ //队列
cin >> str1;
if(str1 == "IN"){
cin >> temp;
Q.push(temp);
}
if(str1 == "OUT"){
if(Q.empty()){
cout << "None" << endl;
} else {
cout << Q.front() << endl;
Q.pop();
}
}
}
else{ //栈
cin >> str1;
if(str1 == "IN"){
cin >> temp;
S.push(temp);
}
if(str1 == "OUT"){
if(S.empty()){
cout << "None" << endl;
} else {
cout << S.top() << endl;
S.pop();
}
}
}
}
}
return 0;
}优先队列priority_queue
优先队列，顾名思义就是优先级最高的先出队。它是队列和排序的完美结合，不仅可以存储数据，还可以将这些数据按照设定的规则进行排序。每次的push和pop操作，优先队列都会动态调整，把优先级最高的元素放在前面。
优先队列的有关操作如下：
// 定义优先队列
priority_queue<int> q;
priority_queue<float> f;
priority_queue<string> s;
q.top(); // 返回具有最高优先级的元素值，但不删除该元素
q.pop(); // 删除最高优先级元素
q.push(item); // 插入新元素 在STL中，优先队列是用二叉堆来实现的，在队列中push一个数或pop一个数，复杂度都是 $ O(log_{2}n) $ .
可以用优先队列对数据排序：设定数据小的优先级高，把所有数push进优先队列后一个个top出来，就得到了从小到大的排序。其总复杂度是 $ O(nlog_{2}n) $ .
图论的Dijkstra算法的程序实现用STL的优先队列能极大地简化代码。
链表list
STL的list是数据结构的双向链表，它的内存空间可以是不连续的，通过指针来进行数据的访问，它可以高效率地在任意地方删除和插入，插入和删除操作是常数时间的。
list和vector的优缺点正好相反，它们的应用场景不同。
(1) vector: 插入和删除操作少，随机访问元素频繁。
(2) list: 插入和删除频繁，随机访问较少。
例子
士兵队列训练问题
一队士兵报数：从头开始进行1至2报数，凡报到2的出列，剩下的向小序号方向靠拢，再从头开始进行1至3报数，凡报到3的出列，剩下的向小序号方向靠拢，以后从头开始轮流进行1至2报数、1至3报数，直到剩下的人数不超过3为止。
输入：士兵人数
输出：剩下士兵最初的编号。
#include <bits/stdc++.h>
using namespace std;
int main(){
int t,n;
cin >> t;
while (t--){
cin >> n; //输入n
int k = 2;
list<int> mylist; //定义
list<int>::iterator it;
for(int i = 1;i<=n;i++){
mylist.push_back(i); //将1到n的数放入链表
}
while(mylist.size()>3){
int num = 1;
for(it = mylist.begin();it!=mylist.end(); ){
if(num++%k==0)
it = mylist.erase(it); //删除第k个数
else
it++; //指向下一个元素
}
k==2?k=3:k=2; //1至2报数,1至3报数
}
for(it = mylist.begin();it!=mylist.end();it++){
if (it != mylist.begin()) cout << " ";
cout << *it; //输出剩下的数
}
cout << endl;
}
return 0;
}集合set
set就是集合。STL的set用二叉搜索树实现的，集合中的每个元素指出现一次，并且是排好序的。访问元素的时间复杂度是 $ O(log_{2}n) $ ,非常高效。
set的有关操作：
// 定义
set<int> A;
set<float> B;
set<string> C;
A.insert(item); //把item放进set
A.erase(item); //删除元素item
A.clear(); //清空set
A.empty(); //判断set是否为空
A.size(); //返回set元素个数
A.find(item); // 返回一个迭代器，指向键值k
A.lower_bound(item); // 返回一个迭代器，指向第一个大于等于item的元素
A.upper_bound(item); // 返回一个迭代器，指向第一个大于item的元素例子
产生冠军
有一群人打乒乓球比赛，两两捉对厮杀，每两个人之间最多打一场比赛。
球赛的规则如下：
如果A打败了B，B又打败了C，而A与C之间没有进行过比赛，那么就认定A一定能打败C.
如果A打败了B，B又打败了C，而且C又打败了A，那么A、B、C三者都不可能成为冠军。
根据这个规则，无须循环较量，或许就能确定冠军。本题的任务就是对于一群比赛选手，在经过了若干场厮杀之后，确定是否已经产生了冠军。
这一题的思路是定义集合A和B，把所有人放进集合A，把所有失败记录的放进集合B。如果A-B=1，则可以判断存在冠军，否则不能。
#include <bits/stdc++.h>
using namespace std;
int main(){
set<string> A,B;
string s1,s2;
int n;
while (cin>>n && n){
for(int i = 0; i<n; i++){
cin>>s1>>s2;
A.insert(s1); // 把所有人放进集合A
A.insert(s2); // 把所有人放进集合A
B.insert(s2); // 把失败者放进集合B
}
if(A.size() - B.size() == 1)
cout << "YES" << endl; // 如果集合A的大小比集合B大1，说明有一个人是赢家
else
cout << "NO" << endl; // 否则输出NO
A.clear();
B.clear();
}
return 0;
}图 map
这里有一个常见的问题：有n个学生，每人有姓名name和学号id，现在给定一个学生的name，要求查找他的id。
简单的做法是定义string name[n]和int id[n]（可以放在一个结构体中）存储信息，然后在name[]中查找这个学生，找到后输出他的id。这样做的缺点是需要搜索所有的name[]，复杂度是O(n)，效率很低。
利用STL中的map容器可以快速地实现这个查找，复杂度是 $ O(log_{2}n)s $ .
map是关联容器，它实现从键(key)到值(value)的映射。map效率高的原因是它用平衡二叉搜索树来存储和访问。
在上述例子中，map的具体操作如下：
(1) 定义：map<sting , int> student, 存储学生的name和id。
(2) 赋值：例如 student[“TOM”]=15。这里把“Tom”当成普通数组的下标来使用。
(3) 查找：在找学号时，可以直接用student[“TOM”]表示他的id，不用再去搜索所有的姓名。
map用起来很方便。对于它的插入、查找、访问等操作。下面是用map创建的一个实例。
map<string,int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // 输出10例子
女孩dandelion经常去购物，她特别喜欢一家叫”memory”的商店。由于春节快到了，所有商店的价格每天都在上涨。她想知道这家商店每天的价格排名。
输入：
第1行是数字n(n<10000),代表商店的数量。
后面n行，每行有一个字符串(长度小于31，只包含小写字母和大写字母)，表示商店的名称。
然后一行是数字 $ m( 1 \le m \le 50 ) $ ,表示天数。
后面有m部分，每部分有n行，每行是数字s和一个字符串p，表示商店p在这一天涨价s
输出：
包含m行，第i行显示第i天后店铺”memory”的排名。排名的定义为如果有t个商店的价格高于”memory”，那么它的排名是t+1.
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m, p;
map <string, int> shop;
while (cin>>n){
string s;
for(int i =1;i <=n;i++) cin >>s; // 输入商店名字，实际上用不着处理。
cin >> m; // 输入商品数量
while(m--){
for(int i=1; i<=n; i++){
cin >> p >> s;
shop[s] += p; // 累加每个商店的商品数量 用map可以直接操作商店，加上价格
}
int rank = 1; // 排名
map<string, int>::iterator it; //迭代器
for(it = shop.begin();it!=shop.end(); it++){
if(it->second>shop["memory"]) rank++; // 比较价格
}
cout << rank << endl; // 输出排名
}
shop.clear(); // 清空map，准备下一次输入
}
return 0;
}
