tkdsheep-STL
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
写这个页面主要是帮我的两只队友熟悉一下竞赛里常用的STL，欢迎各位学长补充编辑以及指出其中的错误和不足之处
直接切入主题，不废话了
=== queue ===
http://www.cplusplus.com/reference/stl/queue/
queue就是普通的队列，队列声明方式： queue <元素类型> 变量名
比如 queue <int> q; 表示你声明了一个队列q，队列里的元素是int类型的
queue用的最多的地方就是bfs，在我的代码习惯里，一个大致的bfs框架是这样写的：
queue <node> q; //node代表一个结构体，如果是简单的格子bfs题，那么node里面一般有表示位置的两个int变量x,y，以及走的步数step
while(!q.empty())//队列非空
{
node ss=q.front();//得到队首的元素
q.pop();//抛出队首的元素
/*进行更新操作得到新的状态tt*/
q.push(tt);//将新的状态压入队列中
}
从上面的例子可以看出queue应该是非常简单易用，front()函数得到队首元素，pop()和push()分别代表出队和入队
为什么要用queue？因为不容易出错，不用自己手动维护front、tail之类的指针，队列的空间也是动态分配的，不用担心数组开小了越界之类的问题
=== priority_queue ===
http://www.cplusplus.com/reference/stl/priority_queue/
priority_queue是优先队列，里面包含的函数跟queue基本一样，除了获得队首元素是top()不是front()
优先队列是我用得非常多的一个STL，它可以实现最大堆或者最小堆，只要我们手动定义好堆里面的元素比较的规则
priority_queue默认是最大堆，比如定义一个priority_queue <int> q，那么每次调用q.top()得到的都是队列里最大的一个int值
但如果优先队列里的元素是自定义的结构体，比如priority_queue <node> q; 那么必须重载运算符使编译器知道node元素是如何比较大小关系的
举个例子，假设我定义了这样的node
struct node
{
int x,y;
}
由于node里面有两个元素，x和y，所以编译器不知道到底怎样才能比较两个node的大小关系
假设我们希望优先队列抛出的队首元素是队列里x值最小的node，如果有多个最小x，则取y最小的
那么就要在node里写一个小于号运算符重载，如下所示
{{{
struct node
{
int x,y;
friend bool operator < (node n1,node n2)//重载小于号
{
if(n1.x != n2.x)//如果x不相等则按x比较大小
return n1.x > n2.x; //注意这里，我重载的是小于号，返回的却是大于号，因为优先队列默认是最大堆，而这里实际上是小的值优先，所以要“反”一下
else return n1.y > n2.y;//如果x相等则按y比较大小
}
}
}}}
summer2012题库里可以用queue以及priority_queue的题目比较多，比如第一轮的0013 Battle: Dojo 0024 Toy Blocks 以及后面的0046 LF2
=== vector ===
'''不会做题写点东西，肥羊学长见谅...请随意删改._.'''
就实际上来说，vector是竞赛中使用STL最多的一个部分，合理的使用vector可以极大地提高代码速度、减少编程复杂度及代码长度，是应当首先掌握的东西。
vector类似于一个动态的数组，它的各种用法与其他STL的用法都很相像，如果熟练掌握vector的用法对掌握其他STL的用法很有好处。
使用前记得在头文件上加入{{{ #include <vector> }}}。
vector的定义类似{{{ vector<ELEMENT TYPE> <NAME> }}}，例如定义一个名为gao的int的vector就是{{{ vector<int> gao }}}。
主要的用法有：
* push_back(<ELEMENT>)：将一个元素插入到vector的尾部。
* clear()：清空vector。'''非常重要，因为多组数据必须使用这个保证环境是干净的。'''
* begin(), end()：开头与末尾的iterator。iterator我建议肥羊学长专门再开个章节讲…… 相对应的还有反向迭代器rbegin(), rend()。
* size()：vector的大小，类似数组大小。'''非常常用，尤其在循环中。'''
例如存图，就经常使用这样的写法：
{{{
for(int i = 0; i < M; ++i){
scanf("%d%d%d", &x, &y, &w);
Gr[x].push_back(make_pair(y, w));
}
}}}
遍历时就可以：
{{{
for(int i = 0; i < N; ++i){
for(int j = 0; j < Gr[i].size(); ++j)
Dfs(Gr[i][j]);
}
}}}
相匹配的一些常用的算法操作：
* sort(gao.begin(), gao.end())：排序。
* lower_bound(gao.begin(), gao.end(), <ELEMENT>)：返回不小于<ELEMENT>的迭代器。这个是算法库导出来的，要保证vector有序才能够使用。
{{{
仰慕搞学长~写的挺详细了丫~我再补充一个就是vector可以像数组一样直接使用，比如vector <int> L
那么L[0]就是第1个元素，L[i]就是第i+1个元素，当然要保证i<L.size()，不然会段错误，总之vector是相当方便易用拉
}}}
=== set ===
set有两个非常重要也非常有用的性质：
1.set可以看做一个集合，集合里面的每一个元素都是唯一的，任意两个元素都不会相同
2.set里面的元素永远是有序的，因此可以实现log级别的查找、添加和删除操作
举个例子
set <int> st;//声明一个存放int类型元素的set，变量名叫st，
set的查找、添加、删除操作需要用到“迭代器”，迭代器有点类似指针吧
set <int> ::iterator it;//声明一个对应类型的迭代器，变量名叫it
插入操作： st.insert(5); 如果st里面已经有5了，那么这个操作不会对st产生任何改变
查找操作: it=st.find(5); 如果st里面没有元素5，则it==st.end()，如果有5，那么*it==5
删除操作: st.erase(it); 注意这里必须保证it!=st.end()
遍历整个set： for(it=st.begin();it!=st.end();it++) 每次取*it即为当前遍历到的元素，这样遍历出来的元素一定是从小到大的
lower_bound函数： it=st.lower_bound(5) 在st中找到【第一个大于等于】5的元素的迭代器位置，找不到则返回st.end()
upper_bound函数： it=st.upper_bound(5) 在st中找到【第一个大于】5的元素的迭代器位置，找不到则返回st.end()
clear()函数：清空整个set，这个在全局set每次初始化的时候不要忘记
size()函数：返回当前set里的元素个数
用到set()的例题可以参加搞学长的0105 Irotoridori no Sekai，基本上set的所有操作都用到了
=== map ===
=== string ===
=== sort ===写这个页面主要是帮我的两只队友熟悉一下竞赛里常用的STL，欢迎各位学长补充编辑以及指出其中的错误和不足之处
直接切入主题，不废话了
queue
http://www.cplusplus.com/reference/stl/queue/
queue就是普通的队列，队列声明方式： queue <元素类型> 变量名
比如 queue
queue用的最多的地方就是bfs，在我的代码习惯里，一个大致的bfs框架是这样写的：
queue
while(!q.empty())//队列非空
{
node ss=q.front();//得到队首的元素
q.pop();//抛出队首的元素
/*进行更新操作得到新的状态tt*/
q.push(tt);//将新的状态压入队列中
}
从上面的例子可以看出queue应该是非常简单易用，front()函数得到队首元素，pop()和push()分别代表出队和入队
为什么要用queue？因为不容易出错，不用自己手动维护front、tail之类的指针，队列的空间也是动态分配的，不用担心数组开小了越界之类的问题
priority_queue
http://www.cplusplus.com/reference/stl/priority_queue/
priority_queue是优先队列，里面包含的函数跟queue基本一样，除了获得队首元素是top()不是front()
优先队列是我用得非常多的一个STL，它可以实现最大堆或者最小堆，只要我们手动定义好堆里面的元素比较的规则
priority_queue默认是最大堆，比如定义一个priority_queue
但如果优先队列里的元素是自定义的结构体，比如priority_queue
举个例子，假设我定义了这样的node
struct node
{
int x,y;
}
由于node里面有两个元素，x和y，所以编译器不知道到底怎样才能比较两个node的大小关系
假设我们希望优先队列抛出的队首元素是队列里x值最小的node，如果有多个最小x，则取y最小的
那么就要在node里写一个小于号运算符重载，如下所示
struct node
{
int x,y;
friend bool operator < (node n1,node n2)//重载小于号
{
if(n1.x != n2.x)//如果x不相等则按x比较大小
return n1.x > n2.x; //注意这里，我重载的是小于号，返回的却是大于号，因为优先队列默认是最大堆，而这里实际上是小的值优先，所以要“反”一下
else return n1.y > n2.y;//如果x相等则按y比较大小
}
}
summer2012题库里可以用queue以及priority_queue的题目比较多，比如第一轮的0013 Battle: Dojo 0024 Toy Blocks 以及后面的0046 LF2
vector
不会做题写点东西，肥羊学长见谅...请随意删改._.
就实际上来说，vector是竞赛中使用STL最多的一个部分，合理的使用vector可以极大地提高代码速度、减少编程复杂度及代码长度，是应当首先掌握的东西。
vector类似于一个动态的数组，它的各种用法与其他STL的用法都很相像，如果熟练掌握vector的用法对掌握其他STL的用法很有好处。
使用前记得在头文件上加入 #include 。
vector的定义类似 vector，例如定义一个名为gao的int的vector就是 vector。
主要的用法有：
- push_back(
)：将一个元素插入到vector的尾部。 - clear()：清空vector。非常重要，因为多组数据必须使用这个保证环境是干净的。
- begin(), end()：开头与末尾的iterator。iterator我建议肥羊学长专门再开个章节讲…… 相对应的还有反向迭代器rbegin(), rend()。
- size()：vector的大小，类似数组大小。非常常用，尤其在循环中。
例如存图，就经常使用这样的写法：
for(int i = 0; i < M; ++i){
scanf("%d%d%d", &x, &y, &w);
Gr[x].push_back(make_pair(y, w));
}
遍历时就可以：
for(int i = 0; i < N; ++i){
for(int j = 0; j < Gr[i].size(); ++j)
Dfs(Gr[i][j]);
}
相匹配的一些常用的算法操作：
- sort(gao.begin(), gao.end())：排序。
- lower_bound(gao.begin(), gao.end(),
)：返回不小于 的迭代器。这个是算法库导出来的，要保证vector有序才能够使用。
仰慕搞学长~写的挺详细了丫~我再补充一个就是vector可以像数组一样直接使用，比如vector <int> L
那么L[0]就是第1个元素，L[i]就是第i+1个元素，当然要保证i<L.size()，不然会段错误，总之vector是相当方便易用拉
set
set有两个非常重要也非常有用的性质：
1.set可以看做一个集合，集合里面的每一个元素都是唯一的，任意两个元素都不会相同
2.set里面的元素永远是有序的，因此可以实现log级别的查找、添加和删除操作
举个例子
set
set的查找、添加、删除操作需要用到“迭代器”，迭代器有点类似指针吧
set
插入操作： st.insert(5); 如果st里面已经有5了，那么这个操作不会对st产生任何改变
查找操作: it=st.find(5); 如果st里面没有元素5，则it==st.end()，如果有5，那么*it==5
删除操作: st.erase(it); 注意这里必须保证it!=st.end()
遍历整个set： for(it=st.begin();it!=st.end();it++) 每次取*it即为当前遍历到的元素，这样遍历出来的元素一定是从小到大的
lower_bound函数： it=st.lower_bound(5) 在st中找到【第一个大于等于】5的元素的迭代器位置，找不到则返回st.end()
upper_bound函数： it=st.upper_bound(5) 在st中找到【第一个大于】5的元素的迭代器位置，找不到则返回st.end()
clear()函数：清空整个set，这个在全局set每次初始化的时候不要忘记
size()函数：返回当前set里的元素个数
用到set()的例题可以参加搞学长的0105 Irotoridori no Sekai，基本上set的所有操作都用到了