2017-03-17

编程语言►C++

STL在使用算法竞赛中的使用方法（教程+未完成）

前言：

本文面向已有 C 语言和部分算法基础的同学。
内容均是个人总结，由于还没有系统的学习过 C++ 的面向对象，也没有翻过 STL 的代码，均以实用的角度来讲，可能不严谨些。
接下来介绍的将是一些 C++ STL 容器的使用，特性及一些常用函数。然后还有部分好用的函数。都会以介绍加代码样例的方式写出。

STL:

Vector：

简介：

Vector 可以看做是一个不定长数组，可以对其进行插入元素，删除元素，按下标访问等基本操作。

重要的一点 Vector 是一个数组而不是一个链表，例如对 Vector 进行插入操作，是基于元素的移位进行的，是 O（n）的复杂度而不是链表的 O（1），但是在其尾部添加元素时是 O（1），应该是内部可以自动优化。

vector 包含在 <vector> 头文件中。

基本操作：

首先创建一个装着 int 类型元素的 vector。
ps：<int>这里其实是使用了模板，具体看概念中的模板部分。

1	vector<int> data;

接下来给 vector 添加元素，这里先向尾部添加元素，也是最常用的添加元素方式。
ps：这里添加是O（1）

1
2
3

data.push_back(1);
data.push_back(2);
data.push_back(3);

接下来可以用下标访问 vector 里面的元素，和数组类似，输出之前插入的1,2,3

1
2
3

cout << data[0] << endl;
cout << data[1] << endl;
cout << data[2] << endl;

接下来是插入元素和删除元素。下面的插入是把 t 插入到下标为 i 的位置上，原来 i 位置及其后面的元素，都往后移一位。删除是删除掉下标为 i 的元素，后面的元素全部前移一位。
ps：时间复杂度O（n）

1 2	data.insert(data.begin() + i, t); data.erase(data.begin() + i);

定义 vector 数组时和普通类型一样使用即可

1 2	vector<int> example[112345]; example[233].push_back(666);

接下来是是一些常用的函数，将直接给出代码，代码中加入注释。

//返回 data 的大小，有 n 个元素即返回 n
data.size();

//清空 data，恢复 data 的初始状态
data.clear();

//重新设置 data 的长度，可用来直接截短
data.resize(len);

进阶技巧：

了解 vector 使用了模板后，其实 vector 可以用来存 vector 的，例如：

1
2
3

vector<vector<int> > example;
   example.push_back(vector<int>());
   example[0].push_back(1);

这里定义时 >> 用空格分开是编译器可能会把这里当成其他的关键字。
vector<int>() 表示定义一个空的储存 int 类型的 vector。
这里可能和 vector 数组有点类似，概念上是不同的，使用方法上也有差异。
同理 vector 也可以储存本文将要介绍的其他 STL 容器。

Map：

简介：

map容器常用来做映射，map的实现是用了数据结构的红黑树，通常来说是O（logn）比 hash 慢些，在一些时间限制不太紧的题中还是够用。
map 实现的是一种映射关系，详细见概念部分。

map 包含在头文件 `<map>` 中。

基本使用：

首先创建一个map，这里需要给定两个类型，一个是用来当做访问下标（暂且这样将）的，另一个是储存的数据类型。

部分概念：

本部分内容较啰嗦仅供读者更好的理解后面的 STL 如何工作，只希望了解 STL 用法可以直接略过。

模板：

关于模板这个概念。举个例子，大概意思是，如果要定义一个求两个函数和的函数，需要两个参数 a 和 b，然后返回他们的和。通常来讲我定义函数时如果参数设为 int，那么我这个函数就不可以为 double 类型求和。这时候我需要再为 double 定义一个求和函数。但是你会发现，无不需要关什么 int double 类型，只要输入进来的两个变量，只要定义了他们类型之间的加法应该是什么样子就可以了。

比如说输入两个整型和浮点型，直接返回他们的和就可以了。有了模板这个概念后，我甚至可以给这两个函数输入两个矩阵 a = [1,2,3,4], b = [2,2,3,4]，求这两个矩阵的和，只要我定义好两个矩阵相加应该是什么样的规则就好了。

这样以后更深入的话，就可以知道，这样可以实现类的多态。
意思是给我两个你自己定义的结构体/对象我要求他的和，你只要定义好这个数据类型相加应该是什么样的就好了，不用再去定义一个函数。

接下来的 STL 容器都用了模板的概念，大概是 [容器名]<类型名> 这样的形式，然后类型那里可以随便填了（前提是有），int 也好，自己定义的结构体也好，运用上面的概念，STL 容器不关心他存的是上面类型，只要这个类型定义了某些运算应该符合什么样的规则就可以了。

迭代器：

这里可以当做指针对待，不再作详细介绍，[容器名].begin() 返回指向某容器首部的迭代器。

映射：

这里用数学里面的概念好了，意思是给定一个 x，对应一个唯一的 y。

亦可把 map 理解成一个下标为任意类型的数组，比如我可以用一个字符串当下标来储存一个整数。

这里用一下 Python 字典的概念好了，map 大概也是这个东西，map 中储存的是无数个 key：value 这样的键值对，不可存在同样的 key，访问 value，通过输入他的 key 来访问。

前言：