STL在OI的应用

前言

在OI的学习中,STL可以给予我们很多的方便与快捷,也是减少代码常数的不二之选。同时,也可以帮助我们降低代码的书写难度。

简介

STL中最重要的概念就是容器、算法和迭代器。

  • 容器(Containers) : 容器是用来管理某一类对象的集合。
  • 算法(Algorithms) : 算法作用于容器。
  • 迭代器(Iterators) : 迭代器用于遍历对象集合的元素。

迭代器

迭代器是访问STL容器数据的最普遍和简单的方式。

下面给出一个例子 :

1
2
3
4
5
6
7
// traversing a vector
vector<int> vec;
for ( vector<int> :: iterator itor = vec.begin(); itor != vec.end(); ++ itor )
{
// do some thing, like ...
cout << (*itor) << endl;
}

但是,C++11给了我们更好的一种方式,对于上面的例子我们可以这样写 :

1
2
3
4
5
6
7
// traversing a vector
vector<int> vec;
for ( auto &itor : vec )
{
// do some thing, like ...
cout << itor << endl;
}

显然,这种新的遍历方式更加的简洁,但是NOI系列比赛均不支持C++11,所以没什么用…
同时,这个好像慢一点…

容器

vector

vector其实相当于一个数组,其中vector最重要的就是连续内存,可以极大地加速代码

接下来给出vector的一些操作 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 新建vector容器
vector<int> vec; // 其中int可以修改成数据类型

// 判断vector是否为空
vec.empty() // 返回true或false

// 清空vector
vec.clear();

// 获取vector大小
int size = vec.size(); // 注意 : vector的下标从0开始,即vec[size - 1]为最后一个元素

// 向尾部添加元素
int x; cin >> x;
vec.push_back(x); // 注意 : 添加的元素的数据类型应与vector数据类型相符合

// 从尾部删除元素
vec.pop_back(x); // 同上

// 删除元素
vec.erase(x); // 删除位置为x的元素,同时指向x下一位的元素
vec.erase(l, r); // 删除区间为[l,r)的元素

// 改变vector大小
// 有时,你需要将你不需要使用的元素删除以达到减少空间复杂度的目的
vec.resize(20); // 即从vec[20]和以后的元素都会被删除

queue

queue相当于一个队列,只可以从头部读入删除元素,从尾部添加元素,一般来说,队列是在BFS操作的时候使用,使用方式与vector相似。
但queue的插入和删除操作有一些不同 :

1
2
3
4
queue<int> que;

que.push(x); // 向尾部添加元素
que.pop(x); // 向开头删除元素

deque

deque相当于收尾都可以添加和删除元素的队列,deque拥有vector拥有的所有操作并且添加了两个操作 :

1
2
3
4
deque<int> deq;

deq.push_front(x); // 向开头添加元素
deq.pop_front(x); // 从开头删除元素

键值对(pair)

键值对(pair)是一种很方便的东西,一般来说,pair就是一个元素对,标准情况如下 :

1
2
3
4
5
6
template<typename T1, typename T2> struct pair 
{
T1 first;
T2 second;
} ;
pair<int, int> a; // 定义一个键值对(上面的使用时不需要写,c++内置)

键值对的最大有点就是会有内置函数来比较pair的对象,例如sort时就会优先比较first。

map

map我们一般作为Hash表来使用,下面给出map的一些操作 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
map<string, int> Map; // 新建一个map

// 插入操作
Map.insert(pair<string, int> ("21233", x)); // 其中x为权值

// 获取map大小
int size = Map.size();

// 遍历map
for ( map<string, int> :: iterator itor = Map.begin(); itor != Map.end(); ++ itor )
{
// ...
}
for ( int i = 1; i <= size; ++ i ) // 注意map下标从1开始
{
// ...
}

// 查询一个字符串的权值
string s;
map<string, int> :: iterator itor = Map.find(s); // 查找string s,返回一个迭代器

// 删除操作与vector相同

尾记

差不多就是这些,如果你喜欢我的文章的话,可以通过戳我来支持我的文章更新哦!