C++ STL
这是我学习标准模板整理的一些知识点
vector常见用法
vector 翻译为向量，是一种可以容纳同类型元素的容器，也可以理解为“长度根据需要而自动改变的数组”。要使用 vector ，需要添加以下两行：
#include
using namespace std;
1. vector定义
vector name;
2. vector容器内元素的访问
通过下标访问
对于一个定义为 vector vi 的 vector 容器来说，使用 vi[index] 访问即可，下标是从 0 到 vi.size()-1
通过迭代器访问
迭代器可以理解为一种 复杂的指针，定义是 vector::iterator it;，可以通过 *it 来访问 vector 里的元素
vi[i] 和 *(vi.begin()+i) 是等价的，所以可以通过以下这种方式访问容器内的元素
C++
vector::iterator it = vi.begin();
printf("%d", *(it + i));
迭代器还实现了两种自加操作：++it 和 it++ （自减操作同理），于是有另一种遍历vector中元素的写法，注意 end() 并不是取vi的尾元素地址，而是取尾元素地址的下一个地址
C++
//vector的迭代器不支持it < vi.end()的写法，因此循环条件只能用it != vi.end()
for(vector::iterator it = vi.begin(); it != vi.end(); it++)
{
printf("%d ", *it);
}
注意，在常用 STL 容器中，只有在 vector 和 string 中，才允许使用 vi.begin() + 3 这种迭代器加上整数的写法
3. vector常用函数解析
push_back()
push_back(x) 即在 vector 后面添加一个元素 x，时间复杂度 O(1) ，如 vi.push_back(x)
pop_back()
用以删除 vector 的尾元素，时间复杂度 O(1)
size()
用来获得 vector 中元素的个数，时间复杂度 O(1) 。size() 返回的是 unsigned 类型，一般来说用 %d 不会有很大问题，比如 printf("%d\n", vi.size());
clear()
用来清空 vector 中所有元素，时间复杂度 O(N)
insert()
insert(it, x) 用来向 vector 的任意迭代器 it 处插入一个元素 x ，时间复杂度 O(N)
erase()
erase(it) 即删除迭代器为 it 处的元素
erase(first, last) 即删除 [first, last) 内的所有元素
4. vector的常见用途
本身可以作为数组使用，在一些元素个数不确定的场合可以很好节省空间
在需要按一定格式输出数量不确定的数据时
实现邻接表储存图
set常见用法
set翻译为集合，是一个 内部自动有序 （递增排序） 且 不含重复元素 的容器。要使用 set ，需要添加以下两行：
#include
using namespace std;
1. set定义
set name;
2. set容器内元素的访问
set 只能通过迭代器访问
set::iterator it;
由于除开 vector 和 string 之外的 STL 容器都不支持 *(it + i) 的访问方式，因此只能如下枚举：
C++
for(set::iterator it = st.begin(); it ！= st.end(); it++)
{
printf("%d ", *it);
}
3. set常用函数解析
insert()
insert(x) 可将 x 插入 set 容器中，并自动递增排序和去重，时间复杂度 O(logN)
find()
find(value) 返回 set 中对应值为 value 的迭代器，时间复杂度 O(logN) ，如
set::iterator it = st.find(2);
erase()
erase(it) 删除迭代器为 it 处的元素
erase(value) 删除值为 value 的元素
erase(first, last) 删除 [first, last) 内的所有元素
size()
size() 用来获得 set 内元素的个数， 时间复杂度 O(1)
clear()
clear() 用来清空 set 中的所有元素，复杂度 O(N)
4. set常见用途
set 最主要的作用是自动去重并按升序排列，因此遇到需要去重但不方便直接开数组的情况，可以尝试用 set 解决
- set 中元素是唯一的，需要处理不为一的情况，需要使用 multiset 。另外，C++ 11 标准中还增加了 unordered_set ，以散列代替 set 内的红黑树，可以用来处理只去重不排序的需求，速度比 set 快得多
string常见用法
string对字符串常用的功能进行了封装，要使用 string ，需要添加以下两行：
#include
using namespace std;
1. string定义
与基本数据类型相同，在 string 后跟上变量名即可：
string str;
初始化可直接对变量赋值
string str = "abcd";
2. string中内容的访问
通过下标访问
C++
string str = "abcd";
for(int i = 0; i < str.length(); i++)
{
printf("%c", str[i]);
}
如果要读入和输出整个字符串，则只能用 cin 和 cout
通过迭代器访问
C++
string str = "abcd";
for(string:iterator it = str.begin(); it != str.end(); it++)
{
printf("%c", *it);
}
string 和 vector 一样，支持直接对迭代器加减某个数字，如 str.begin() + 3 的写法是可行的
3. string 常用函数解析
operator +=
string 的加法，可以直接将两个 string 拼接起来
str3 = str1 + str2;
str1 += str2;
compare operator
两个 string 类型可以直接用 ==、!=、<、<=、>、>= 比较大小，比较规则是 字典序
length()/size()
前者返回 string 的长度，即存放的字符数，后者与前者基本相同
insert()
string 的 insert() 有很多种写法，下面给出几个常用的写法，时间复杂度 O(N)
insert(pos, string) ，在 pos 位置插入字符串 string
insert(it, it2, it3) , it 为原字符串的欲插入位置，it2 和 it3 为待插字符串的首尾迭代器，用来表示字符串 [it2, it3) 将被插在 it 的位置上
erase()
str.erase(it) 用于删除单个元素，it 为需要删除的元素的迭代器
str.erase(first, last) 删除一个区间内的所有元素，即为删除 [first, last)
str.erase(pos, length) 其中 pos 为需要开始删除的起始位置，length 为删除的字符个数
clear()
用于清空 string 中的数据，时间复杂度一般为 O(1)
substr(pos, len) 返回从 pos 位开始，长度为 len 的子串，时间复杂度为 O(len)
string::npos
string::npos 是一个常数，用以作为 find 函数失配时的返回值，其本身的值为 -1 ，但由于时 unsigned_int 类型，因此实际上也可以认为是 unsigned_int 类型的最大值 4294967295
find()
str.find(str2) 当 str2 是 str 的子串时，返回其在 str 中第一次出现的位置；如果不是，返回 string::npos
str.find(str2, pos) 从 str 的 pos 号位开始匹配 str2 ，返回值与上相同，时间复杂度 O(mn) ，其中 n 和 m 分别为 str 和 str2 的长度
replace()
str.replace(pos, len, str2) 把 str 从 pos 位开始，长度为 len 的子串替换为 str2
str.replace(it1, it2, str2) 把 str 的迭代器 [it1, it2) 范围的子串替换为 str2
map常见用法
map 翻译为映射，可以将任何基本类型（包括 STL 容器）映射到任何基本类型（包括 STL 容器）。要使用 map ，需要添加以下两行：
#include
using namespace std;
1. map定义
map mp;
- <> 内两个类型前者是键的类型，后者是值的类型
- 如果是字符串到整型的映射，必须使用 string 而不能用 char 数组
2. map容器内元素的访问
通过下标访问
例如对一个定义为 map mp 的 map 来说，可以直接使用 mp['c'] 的方式来访问对应的整数，注意，map 中的键值是唯一的
通过迭代器访问
map 迭代器定义与其他 STL 容器相同
map::iterator it;
map 使用 it->first 访问键，使用 it->second 访问值
map 会以键从小到大的顺序自动排序
3. map常用函数解析
find()
find(key) 返回键为 key 的映射的迭代器，时间复杂度 O(logN)
erase()
mp.erase(it) ，删除单个元素，it 为需要删除的元素的迭代器，时间复杂度 O(1)
mp.erase(key) ，删除单个元素， key 为欲删除的映射的键，时间复杂度 O(logN)
mp.erase(first, last) 删除区间 [first, last) 内元素
size()
用来获取 map 中映射的数量，时间复杂度为 O(1)
clear()
用来清空 map 中的所有元素，复杂度 O(N)
4. map常见用途
需要建立字符（或字符串）与整数之间映射的情境，使用 map 可以减少代码量
判断大整数或者其他类型数据是否存在的情况，可以把 map 当 bool 数组用
字符串和字符串的映射可能也会用到
map 的键和值是唯一的，如果一个键需要对应多个值，就只能用 multimap 。C++ 11 中还增加了 unordered_map，以散列代替 map 内部的红黑树实现，使其可以用来处理只映射而不按 key 排序的需求，速度比 map 快得多
