竞赛用STL整理

最近刷了好几道关于STL的竞赛题，许多知识点还是不熟练，在继续学习之前，还是来好好整理一下一些常见的STL和容器吧。紫书上介绍的有以下几种：

线性：vector,list,string
关联：map,set
特殊：stack,queue,priority_queue
算法：sort,lower_bound,find

# vector

vector可以理解为可以自由变换长度的数组(不定长数组)，个人感觉使用频率还是很高的。vector是连续的，意味着可以使用[]或at()。

声明： vector<int> a

# 常用函数

push_back：在尾部添加一个数据
pop_back：删除尾部的一个数据
size：当前的大小（就是有多少元素）
erase：删除指针指向的数据项
clear：清空
empty：判断是否为空

# deque

deque可以看作是双向队列，是连续存储结构。vector有的功能它都有，还支持高效的首/尾端插入/删除操作。

# 新增函数

push_front：在头部添加一个数据
pop_front：在头部删除一个数据

# list

list可以看作是双链表，是非连续存储结构。可在两端进行push、pop，同时在内部可以很方便的进行插入和删除操作。不过我没怎么用到这个容器。等我做到相关的题目再来补充一些信息吧。

# string

string就是字符串。相比char[]那可是方便不少，c++的cin/cout就只支持string类型而不支持char型数组。string还支持+、=、+=等运算符。

# 常用函数

append：在字符串后添加（相当于+=）
substr(n,m)：返回string的子串，从n处开始，取m个。当m省略或超过了字符串的长度，则一直取到字符串结束。

查找相关函数：

如果没有查到，返回string::npos。

find：从前往后查找子串或字符出现的位置。
rfind：从后往前查找子串或字符出现的位置。
find_first_of：从前往后查找何处出现另一个字符串中包含的字符。例如：
s1.find_first_of(“abc”); //查找s1中第一次出现"abc"中任一字符的位置
find_last_of：从后往前查找何处出现另一个字符串中包含的字符。
find_first_not_of：从前往后查找何处出现另一个字符串中没有包含的字符。
find_last_not_of：从后往前查找何处出现另一个字符串中没有包含的字符。

# 流处理

可以通过<sstream>，将string对象作为一个流。例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main(){
    string line;
    while(getline(cin,line)){
        stringstream ss(line);
        while(ss>>x){...}
    }
}

# set

set就是数学中的集合，每个元素只能出现一次，set中的元素已经从小到大排好了。

# 常用函数

insert：插入一个元素
erase：删除，可以传入定位器，也可直接传入值
count：统计元素出现的个数，因为只有0/1个，所以一般用来判断元素是否存在
find：查找

对于自己定义的结构体，需要重载<运算符。

# 常用算法

在<algorithm>中提供了关于set的两种算法（目前只知道两种）

set_union：取两个集合的并集，例如：

1
2
3


#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
set_union(ALL(x1),ALL(x2),INS(x)); //将x1和x2的内容取并集后放入x中

set_intersection：取两个集合的交集，例如：

1

set_intersection(ALL(x1),ALL(x2),INS(x)); //将x1和x2的内容取交集放入x中

# map

map是映射，支持[]运算符，还是非常实用的。

map的函数和set基本一致，这里就不重复写了。

# stack

stack就是数据结构中的栈，数据是“后进先出”。

# 基本函数

push：入栈
pop：出栈
top：取栈顶元素

要注意的是，使用pop()出栈并不会返回被删除的元素值，如果想要需要先top()一下

# queue

queue就是数据结构里的队列，数据符合“先进先出”的规则。

# 基本函数

push：入队
pop：出队
front：取队首

# priority_queue

优先队列，将按照优先级来排序，取队首的front()的函数将换为top()。该容器也定义在头文件<queue>里。

对于自定义数据类型的队列，需要定义<运算。对于已经定义过的数据类型，我们可以通过定义一个结构体，在其中重载()运算符来看起来像一个函数，例如：

1
2
3
4
5
6
7
8


struct cmp
{
    bool operator()(const int a, const int b) const
    {
        return abs(a) < abs(b);
    }
};
priority_queue<int, vector<int>, cmp> p_queue;

这样就定义了一个绝对值大小优先的队列