3.1 容器

前两章都是一些介绍过的概念，我们直接从第三章开始进行学习。

这里的容器指的主要就是STL容器，STL容器主要分为顺序式容器和关联式容器。

顺序式容器包括vector，list，deque，queue，prioritiy_queue，stack等：

vector：动态数组，即不定长数组，能从末尾进行快速的插入和删除(也仅能从末尾)，同时满足数组的特性——根据索引直接访问元素。

list：双链表

queue：队列，FIFO

deque：双端队列，比起传统队列，可以从前面或后面快速插入与删除，并且直接访问任何元素

prioritiy_queue：优先队列，最高优先级的元素第一个出列，但是无法(很难)遍历打印整个序列的元素，一般用于多次寻找当前优先级最高的元素一类的问题。

stack：栈，后进先出，最基本最常见的一类数据结构之一。

关联式容器包括set，multiset，map，multimap等：

set：集合，支持快速查找

multiset：这个在紫书中没有学到过，我查了一下资料说是允许重复的集合······

我个人感觉就是排序好的序列，一个使用上更优的优先队列······

map：一对一的映射，基于关键字的快速查找，不允许重复值

multimap：一对多的映射，基于关键字的快速查找，允许重复值。

我查了较多的博客，就是说multimap中的key值可以重复，至于怎么样一对多，如何重复，是按照集合还是简单序列，顺序又是什么样的都没有进行说明。事实上multimap和前面的multiset一样往往可以用其他的容器进行替代来实现相同的效果。

另外还有关联式容器中还有一类用的比较少的容器书上没有提及——无序关联类容器：

无序关联容器
unordered_map            用哈希函数组织的map，无序
unordered_set            用哈希函数组织的set，无序
unordered_multimap       哈希组织的map；关键字可以重复
unordered_multiset       哈希组织的set，关键字可以重复

实现的基础存储结构不同，其他规则都差不多，这里即不多作赘述(假的，万一什么看到哪本书恰好有详细地介绍，就又炒一遍冷饭了hhhh)

vector比起常规静态数组，优点就是比较省空间，作为一个模板类，vector可以存放任何类型的数据。

下面简单回顾一下常见的定义方式和操作：

//定义存放int类型的容器
vectora;//默认a为空
vectorb(a);//用a来定义b
vectora(100);//100表示a的空间长度,a有100个值为0的元素
vectora(100,6);//100表示a的空间长度,a有100个值为6的元素
//定义存放string类型的容器 
vectora(10,"hello");//10个值为hello的元素
vectorb(a.begin(),a.end());//b是a的复制
//基本操作
a.push_back(x);//尾部添加元素
a.size();//求a的长度
a.empty();//判空
a[id];//根据索引访问 
a.insert(a.begin()+i,k);//在某位置插入元素,复杂度高
a.pop_back();//删除末尾元素
a.erase(a.begin()+i);//删除某个元素,复杂度高
a.erase(a.begin()+i,a.begin()+j);//删除某段元素
a.resize();//调整大小为n,如果当前大小大于n则删除多余的元素,否则进行填补(填补的元素可以自己定义)
a.clear();//清空但不清内存
reverse(a.begin()+i,a.begin()+j);//翻转某段序列的顺序 

炒冷饭，不过冷饭还是挺香的hhhhh，而且要注意resize是个不常用但在某些清空下非常好用的函数，另外这里复制的方法也是第一次见。

看一看黑书stl容器这里的例题：

圆桌上围坐着2n个人，一半是好人，一半是坏人，从第一个人开始数，数到第m个人，立即赶走该人，然后从被赶走的人之后开始数，再将数到的第m个人赶走，直到剩下n个人。

我们现在需要一种对好人和坏人的排法保证赶走n个人之后圆桌边围坐的人都是好人，好人为G，坏人为B。

分析：这个问题呢，紫书好像没有，但我恰好做过他的原身也就是约瑟夫问题，黑书上提供的方法是以vector作为容器进行删除的模拟，emmmm反正不是最好的方法：

int n,m,pos=0; vectort; cin>>n>>m;//t用来模拟圆桌,pos表示 
t.clear(); for (int i=0;i 
这个肯定······不是这个问题最好的做法hhh。
 
 
3.1.2 栈和stack 
······难道不是一个意思么？基本操作如下：
 
stacks;//type表示类型
s.push(x);//将x压入栈顶
s.top();//返回栈顶元素
s.pop();//删除栈顶元素,俗称弹栈
s.empty();//判空 
s.size();//告诉你栈的大小
 
依旧是冷饭······例题不看了，因为过于简单，有兴趣的可以看这篇文章，里面栈的运用相对而言还多一点。
 
 
3.1.3 队列和queue 
相比栈，队列在bfs，单调队列以及后面的图论类问题里倒是比较常用。
 
queueq;//type表示类型
q.push(x);//将x放入队首 
q.front();//返回队首元素
q.pop();//删除队首元素
q.back();//返回队尾元素 
s.empty();//判空 
s.size();//告诉你队列的大小
 
例题······没有意义的傻逼题。
 
 
3.1.4 优先队列和priority_queue 
优先队列本质上即是队列和排序的结合：优先级最高的先出队，里面是用二叉堆来实现的，每次push和pop的操作的复杂度都是logn级别的。
 
书上的介绍就到这里了，但我要说一些关于优先队列实操的细节：
 
1.优先队列只能不断地top，pop打印整个队列，我还不知道有什么不破坏整个结构打印遍历的方法。
 
2.优先队列一般适用于多次取优先级最高元素的问题。
 
3.关于优先队列的cmp，对于同一种结构体类型，是可以写很多种的，就是说对于一种结构体类型可以有多种的优先队列。
 
4.请务必熟练掌握一种优先队列重写排序规则的方法。
 
习题的话，不知道为什么hdu进不去了······
 
 
3.1.5 链表和list 
双向链表即是，链表和数组的优缺点恰好互相相反：链表插入和删除比较快，数组访问与查找比较快。根据不同的需要选用不同的容器(事实上用到链表的题目相当之少)。
 
 
3.1.6 set 
set也就是集合，stl的set内部用二分搜索树实现，set内部的每个元素只能出现一次，并且已经排序好了(这个排序的方法好像也能自己重构)，基本操作如下：
 
seta;
a.insert(x);//将x放入集合a中
a.erase(x);//在集合a中删除元素x
a.clear();//清空
a.empty();//判空
a.size();//求长度
a.find(x);//返回指向x的迭代器
 
hdu 2094 “产生冠军” 
有一群人两两之间打了若干场比赛，比赛的规则如下：
 
如果A击败了B，B击败了C，A和C之间没有进行过比赛，那么确定A能够击败C。
 
如果A击败了B，B又击败了C，C又击败了A，那么这三个人都不能成为冠军，本题的任务就是根据若干场比赛确定是否能确定出一个冠军。
 
分析：黑书这里的例题非常的不好，我还是建议大家直接去看我紫书这里的内容，我当时写的非常的仔细和认真，黑书这里的例题事实上和set关系非常少，而是对数学直观的要求更高。
 
首先我们可以知道，能够成为冠军的人，一定不能输过，但是这道题有个坑：就是在于如果有多个没有输过的人，那依旧无法确定谁是冠军。于是下面的数学直观(我说是直观，就不给予证明)：
 
我们用a集合来存储所有人，b集合来存储失败过的人，a集合的大小减去b集合的大小为1代表能够确定出一个冠军。
 
int n; cin>>n; string s1,s2; seta,b;//a和b表示两个集合 
for (int i=0;i>s1>>s2;
	a.insert(s1); a.insert(s2); b.insert(s2)//两个参加过比赛的人和一个失败的人 
} cout<<(a.size()-b.size()==1)?"Yes":"No";//如果存在却恰好只存在一个没输过的人,那么这个人即为冠军 
 
说实话这个题真的不能让初学者更好的体会集合的用法。
 
 
3.1.7 map 
即是映射，可以建立类型a(key)到类型b(value)的映射，然后根据类型a快速地查找(也就是logn的复杂度)对应的类型b。map是用平衡二叉树来进行存储和访问。
 
黑书这里关于map操作的介绍·····就没了？？？算了stl容器大家还是好好去看紫书的第五章吧emmm。
 
hdu 2648 “Shopping” 
给出n个商店的名称，和每个商店m天中每天价格的变化。需要你求出m天，每天某个商店价格的排名(如果有t个商店价格高于该商店，它的排名为t+1)。
 
分析：如果做过紫书上图书馆还书的题目，这个题真的是小儿科中的小儿科，用一个店名到价格的映射就能够非常轻松的解决这个问题：
 
mapshop; string s; int n,m,p; cin>>n;//店名到价格的映射
for (int i=0;i>s; cin>>m;//这里对店名的输入其实没有任何意义,因为后面也会输入
for (int i=0;i>p>>s; shop[s]+=p;}//n个店的价格变化 
	int rank=1; map::iterator it;//遍历用的迭代器
	for (it=shop.begin();it!=shop.end();it++) if (it->second>shop["memory"]) rank++; 
	cout< 
 
总体来说，黑书的stl容器这部分讲的几乎没有任何难度，我没有资格评价stl容器的题目难一点简单一点对能力的影响，只能说见仁见智了。