鄙人认为 C++ 相比 C 最大的更新就是内置的 STL 了，里面封装了一堆好用的容器，而不用关心其内部实现的原理和具体代码，十分方便快捷，除了容器外还有一堆算法，这个在下一篇会讲

本文仅记录我认为比较常用的容器，例如 pair 这种比较鸡肋的就不记录了

注意：使用 STL 必须要定义命名空间，例如using namespace std;

Vector

vector 直译为“向量”，但是一般当成可变长的数组用

众所周知，C/C++ 中的数组一旦定义就无法改变长度，而 vector 就可以解决这个问题，但是代价也是明显的：运行速度更慢

记得使用 #include <vector> 来引入头文件

定义

1	vector<typename> name;

以上定义相当于定义了一个一维数组 name[size] ，但是 size 不确定，其长度可以根据需要而变化。其中 typename 可以是任何基本类型，例如 int、 double 、char 、结构体等，也可以套娃 STL 标准容器，例如 vector 、 queue 等

访问

使用下标

这就像是访问传统的数组一样，非常方便，例：

1 2	vector<int> v; printf("%d ",v[index]);

注意：

不能越界，不然会报错
这种方法仅限于访问，不能通过它来修改

使用迭代器

可以将迭代器（iterator）理解为一种类似指针的变量。其定义为：vector<typename>::iterator it; ，例：

1 2	vector<int>::iterator it= v.begin(); for(int i = 0; i <= 5; i++) printf("%d ",*(it + i));

常用方法

push_back(x) ：在后面添加一个元素 x，时间复杂度为 O(1)
size() ：用来获得元素的个数
pop_back() ：弹出尾元素，时间复杂度为 O(1)
clear() ：清空所有元素，时间复杂度为 O(n)
insert(it,x) ：在迭代器 it 处插入一个元素 x，时间复杂度为 O(n)
erase() ：删除元素，使用 erase(it)删除迭代器 it 处的元素（时间复杂度为 O(1)），或使用 erase(first,last) 删除左闭右开区间 [first,last) 内的所有元素（时间复杂度为 O(last-first)）

Stack

stack 翻译为栈，是一种“后进先出”的容器，只能通过 top() 和 pop() 来访问栈顶元素

记得使用 #include <stack> 来引入头文件

定义

1	stack<typename> name;

类似地，typename 可以是任何基本类型或者容器，name 是栈的名字

常用方法

push(x) ：将 x 压入栈，时间复杂度为 O(1)
top() ：获得栈顶元素（但不删除），时间复杂度为 O(1)
pop() ：弹出栈顶元素，时间复杂度为 O(1)
empty() ：检测是否为空，空返回 true，否则返回 false，时间复杂度为 O(1)
size() ：返回元素个数，时间复杂度为 O(1)

Queue

queue 翻译为队列，是一种“先进先出”的容器，只能通过函数 front() 来访问队首元素，或通过函数 back() 来访问队尾元素

记得使用 #include <queue> 来引入头文件

定义

1	queue<typename> name;

其中，typename 可以是任何基本类型或者容器，name 为队列的名字

常用方法

push(x) ：将 x 入队，时间复杂度为 O(1)
front() ：获取队首元素，时间复杂度为 O(1)
back() ：获取队尾元素，时间复杂度为 O(1)
pop() ：让队首元素出队，时间复杂度为 O(1)
empty() ：检测是否为空，空返回 true，否则返回 false，时间复杂度为 O(1)
size() ：返回元素个数，时间复杂度为 O(1)

priority_queue

STL 中还有两种容器与队列有关，分别是双端队列（deque）和优先队列（priority_queue）

但是用的最多的还是优先队列，简单的说就是可以同时帮你在内部排序的队列

基本定义式与一般队列相似，但如果要指定排序方向，则需要复杂一点，请看下面的两个实例

1 2	priority_queue<int> q; priority_queue<int,vector<int>,less<int> > q;

第二种定义方式的尖括号内多出了 2 个参数：一个是 vector<int> ，表示的是承载底层数据结构——堆（heap）的容器，其类型要与第 1 个参数一致；另一个是 less<int> ，是对第 1 个参数的比较类， less<int> 表示数字越大的优先级越大（大根堆），而如果用 greater<int> 则表示数字越小的优先级越大（小根堆）

一定要记得 less 是大在前， greater 是小在前

而默认的就是大在前，所以这两个定义其实是一样的

它的方法与 queue 大同小异，但是也有不同：

push() 方法的时间复杂度提升为 $\log _{2}n$ ，毕竟内部要排序
没有了 front() 和 back() 方法，只能通过 top() 或 pop() 访问队首元素

Map

map 翻译为映射，是STL中的常用容器。其实，数组就是一种映射，比如：int a[100]; 就是定义了一个 int 到 int 的映射。而 a[5]=25; 就是把 5 映射到 25。数组总是将 int 类型映射到其它基本类型（称为数组的基类型），这同时也带来了一个问题，有时候我们希望把 string 映射成一个 int，数组就不方便了。这时就可以使用 map，map 可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）

记得使用 #include <map> 来引入头文件

定义

1	map<typename1,typename2> name;

其中，typename1 是映射前的类型（键 key），typename2 是映射后的类型（值 value），name 为映射的名字

访问

和 vector 类似，有下标和迭代器两种方法

使用下标

通过下标访问就像普通的数组元素访问，例如先定义 map<char,int> mp ，然后就可以通过 mp['c'] 的方式来访问它对应的元素，如 mp['c']=124

与 vector 不同，你可以用这种方法直接添加键值对

使用迭代器

通过迭代器访问，先作如下定义：map<typename1,typename2>::iterator it;

因为 map 的每一对映射都有两个 typename ，所以，我们使用 it->first 来访问键，而使用 it->second 来访问值

常用方法

find(key) ：返回键为 key 的映射的迭代器，时间复杂度为 O( $\log _{2}n$ )
size() ：获得映射的对数，时间复杂度为 O(1)
clear() ：清空所有映射，时间复杂度为 O(n)
erase() ：与 vector 中的相同：删除元素，使用 erase(it)删除迭代器 it 指向的元素（时间复杂度为 O(1)），或使用 erase(first,last) 删除左闭右开区间 [first,last) 内的所有元素（时间复杂度为 O(last-first)），但是还多了一个用法：erase(key) ，时间复杂度为 O( $\log _{2}n$ )

Set

set 翻译为集合，是一个内部自动有序且不含重复元素的容器。set 最主要的作用就是自动去重并按升序排序，因此遇到需要去重但是又不方便直接开数组的情况。set 中的元素是唯一的，其内部采用“红黑树”实现

记得使用 #include <map> 来引入头文件

定义

方法一

基础模板

1	set<typename> name;

其中，typename 可以是任何基本类型或者容器，name 是集合的名字

当然有些时候会定义 set 数组，例如：set<int> st[100]; ，这样 st[0]～st[99] 中的每一个元素都是一个 set 容器

方法二

直接通过花括号枚举我们要传入set的值

1	set<string> st{"good", "bad", "medium"};

方法三

从其他结构导入元素

1 2	set<string> st{"good", "bad", "medium"}; set<string> st2(st);

1 2	int myints[] = {75,23,65,42,13}; set<int> myset (myints, myints+5);

访问

set 只能通过迭代器访问。即先定义一个迭代器：set<typename>::iterator it; 然后使用 *it来访问 set 中的元素，例：

1 2	for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it) cout << ' ' << *it;

注意 set 不支持 *(it+i) 或 it < st.end() 的访问方式（实际上除了 vector 和 string 之外的 STL 容器都不支持）

常用方法

insert(x)
find(value) ：返回对应值为 value 的迭代器，时间复杂度为 O( $\log _{2}n$ )
size() ：获得元素个数，时间复杂度为 O(1)
clear() ：清空所有元素，时间复杂度为 O(n)
erase() ：

与 map 相同，有三种用法
- erase(it) ，删除迭代器 it 指向的元素（时间复杂度为 O(1)），
- erase(first,last) ，删除左闭右开区间 [first,last) 内的所有元素（时间复杂度为 O(last-first)）
- erase(value) ，时间复杂度为 O( $\log _{2}n$ )

String

在 C 中，一般使用字符数组 char str[] 来存放字符串，但是操作麻烦，容易出错。C++ 在 STL 中加入了 string 类型，对字符串常用的需求功能进行了封装，使得操作起来更加方便，且不必担心内存是否足够、字符串的长度等问题

定义

1	string name;

其中 name 是字符串变量的名字

当然，你也可以当场就初始化，例如：

1	string str="abcd"

访问

使用下标

就像普通字符数组一样操作，非常方便

1 2	string str= "abcd" ; for(int i = 0; i < str.length(); i++) printf( "%c" ,str[i]);

使用迭代器

先定义 string 迭代器 string::iterator it ，然后就可以通过 *it 来访问 string 里的每一个字符了，例：

1
2
3

string str="abcdefg";
for(string::iterator it = str.begin() + 2; it != str.end(); it++)
    printf("%c",*it); //输出 cdefg

输入输出

如果要读入或者输出整个字符串，一般只能用 cin 和 cout ，如果非要用printf 输出 string，则需要用 c_str() 方法将 string 转换成字符数组，例如：

string str;
cin>>str;
cout<<str<<endl;
printf("%s\n",str.c_str());

运算

string 可以使用 + 来连接两个字符串，大小比较也是可以使用的

常用方法

length() 和 size() ：求长度，时间复杂度为 O(1)（?），二者完全相同
clear() ：清空，时间复杂度为 O(1) （鄙人疑惑：为什么不是 O(n)）
substr(pos,len) ：返回从 pos 号位置开始、长度为 len 的子串，时间复杂度为 O(n)
insert ()：

有多种写法，时间复杂度都是 O(n)
- insert(pos,string) ：在 pos 号位置插入字符串 string
- insert(it,it2,it3) ：it 为原字符串的欲插入位置，it2 和 it3 为待插入字符串的首尾迭代器（左闭右开区间）
erase() ：
- erase(it) ，删除迭代器 it 指向的元素（时间复杂度为 O(1)），
- erase(first,last) ，删除左闭右开区间 [first,last) 内的所有元素（时间复杂度为 O(last-first)）
- erase(pos,length) ，从 pos 位置开始删 length 个字符（时间复杂度为 O(length)）
find() ：

两种写法，时间复杂度都是 O(n*m)
- str.find(str2) ，当 str2 是 str 的子串时，返回其在 str 中第一次出现的位置；否则返回string::npos。string::npos 是一个常数，其本身的值等于 -1，但由于是 unsigned int 类型，因此，也可以认为是 unsigned int 类型的最大值
- str.find(str2,pos) ，是从 str 的 pos 号位开始匹配 str2 ，返回值同上
replace() ：

两种写法，时间复杂度都是 O(str.length)
- str.replace(pos,len,str2) ：表示把 str 从 pos 号位开始、长度为 len 的子串替换为 str2
- str.replace(it1,it2,str2) ：表示把 str 的迭代器 it1 ~ it2 范围内（左闭右开区间）的子串替换为 str2