STL 使用指南 — 丰富实用的容器

各种各样的 STL 容器，承担着各式各样的使命。

上篇文章的容器只提到了栈（stack），它是一种十分简单的容器，并不算什么强大的容器，功能很少。

上篇文章仅仅是入门时的小打小闹罢了。本篇文章将会想你介绍更多的、功能强大的 STL 容器，能够让你见识到 STL 的真正实力。

本文适用人群：对面向对象编程语言有了解的人，有 C++ 基础更佳。
如果你还对此不了解，请移步上篇的入门文章。

通用方法

下面的通用方法，如无特殊说明，是所有 STL 容器均具有的，请务必记住哦（只有下面三个）。意味着所有的 STL 容器都能使用它们。

这里以 c 作为容器名举例。

c.empty();   // -> bool    容器是否为空
c.size();    // -> size_t （int 或其他数值类型） 容器大小（元素个数）
c.clear();   // -> void    清空容器

如无特殊说明，STL 容器都是有迭代器的。如果你对这两个都不了解，请阅读上篇文章。

c.begin();   // -> iterator          头迭代器
// 如果想要取容器里第三个元素的位置，可以使用 c.begin() + 2
// 容器的第一个元素相当于是 c.begin() + 0

c.end();     // -> iterator          尾迭代器
c.rbegin();  // -> reverse_iterator  反向头迭代器
c.rend();    // -> reverse_iterator  反向尾迭代器

如无特殊说明，STL 容器都是能够使用 algorithm 提供的算法函数的。例如：

sort(c.begin(), c.end());    // 将容器 c 内的元素从小到大排序
reverse(c.begin(), c.end()); // 将容器 c 的内容左右翻转

更多 algorithm 用法请参考 cplusplus.com。

基本容器

这些容器都是自己手写也比较好实现的，利用 STL 可以偷懒。

队列与栈

关于栈的介绍，请移步上文。

队列（queue）

队列是先进先出的，就像现实生活中的队伍一样，队首的人处理完成事情之后会离开（pop）并轮到下一个。

需要的头文件

#include <queue>

using namespace std;

注意：所有 STL 容器都是在 std 命名空间内的，所以想要省事请加上 using namespace std;。为了简洁，后面的文章将省略这行，但是实际写代码不要忘记这行哦。

声明与定义

queue<char> q;  // 声明一个名字为 q，存储 char 的队列

注意：以后的所有容器将默认为 char 类型，你可以根据实际情况进行改动，这里只是作为例子。

方法

q.front();    // -> char 队首元素
q.back();     // -> char 队尾元素
q.push('a');  // -> void 向队尾添加元素：字符'a'
q.pop();      // -> void 弹出队首元素

还有两个 C++11 新增方法，emplace 与 swap，可参考前篇文章对它们的简单介绍。

双端队列（deque）

顾名思义，双端队列两头都可以进出，兼有栈和队列的特性。

需要的头文件

#include <deque>

声明与定义

deque<char> q;  // 声明一个名字为 q，存储 char 的双端队列

方法

q.front();   // -> char   队首元素
q.back();    // -> char   队尾元素
// 以上部分和 queue 一样
q.push_front('a'); // -> void 在队首插入元素：字符'a'
q.pop_front();     // -> void 弹出队首元素
q.push_back('a');  // -> void 在队尾插入元素：字符'a'
q.pop_back();      // -> void 弹出队尾元素

更多方法参见 cplusplus.com。本文章只介绍常见的。

链表（list）

经典数据结构——双向链表。可以 $O(1)$ 快速插入和和删除某个元素，$O(n)$ 遍历元素。

需要的头文件

#include <list>

声明与定义

list<char> l;  // 声明一个名字为 l，存储 char 的链表

方法

l.front();           // -> char   首位元素
l.back();            // -> char   末尾元素
l.push_front('a');   // -> void   在首位插入元素：字符'a'
l.pop_front();       // -> void   弹出首元素
l.push_back('a');    // -> void   在末尾插入元素：字符'a'
l.pop_back();        // -> void   弹出尾元素
// 以上部分和 deque 一样

l.insert(l.begin(), 'a');
// -> iterator 在指定位置（这里的例子是队首，其实是迭代器就行）插入字符'a'，返回插入后元素的迭代器
l.insert(l.begin(), 3, 'a');  // 插入 3 个'a'（次）

l.erase(l.begin());
// -> iterator 删除指定位置（这里的例子是队首，其实是迭代器就行）的元素，返回被删除元素下一个元素的迭代器
l.erase(l.begin(), l.end()); // 删除指定区间的元素

更多方法参见 cplusplus。本文章只介绍常见的。

其他

下面这些不常用，感兴趣的读者可自行搜索相关资料。

数组（array）

和普通定长数组一样，没什么特别之处，不怎么常用。

单向链表（forward list）

比起双向链表，唯一的优点也许只有内存占用小了吧。因为是单向，所以不提供反向迭代器。

有点意思的容器

这里的容器都是看起来简单，却实际却又没那么简单的容器。

向量 / 动态数组（vector）

动态数组，顾名思义，长度是动态的。可以像数组一样 $O(1)$ 下标访问，就像普通数组一样。

需要的头文件

#include <vector>

声明与定义

vector<char> v;

构造器

构造器是初始化一个容器时用的，它会在容器创建时自动执行。在声明时这样写即可使用构造器。

// 定义时，将指定区间拷贝到 v 中
vector<char> v(l.begin(), l.end());
// 如果用的是数组，可以像下面这样构造 vector
int a[] = {11, 4, 51, 4};
vector<int> v(a, a + 4);
// 也可以指定初始化数目和变量，如下，定义一个含有 4 个字符'a'的 vector
vector<char> v(4, 'a')；

方法

v.front();           // -> char   首位元素
v.back();            // -> char   末尾元素
v.push_back('a');    // -> void   在末尾插入元素：字符'a'
v.pop_back();        // -> void   弹出尾元素
v.insert(v.begin(), 'a');     // -> iterator 在指定位置插入字符'a'，返回插入后元素的迭代器
v.insert(v.begin(), 3, 'a');  // 插入 3 个（次）'a'
v.erase(v.begin());           // -> iterator 删除指定位置的元素，返回被删除元素下一个元素的迭代器
v.erase(v.begin(), v.end());  // 删除指定区间的元素
// 以上部分和 list 一样
v[1]    // -> char 访问下标为 1 的元素
v.at(1) // -> char 同上

字符串（string）

功能强大的字符串类，字符串处理题好帮手。

需要的头文件

#include <string>

声明与定义

string s;

构造器

string s("hanwan");  // 可以把 C 风格的字符数组作为构造器参数，让它变成 string
string s(3, 'a');    // 当然也能填充字符，定义一个含有 3 个'a'字符串"aaa"。

输入输出方式

使用 C++ 的输入输出流。

// 输入
cin >> s;          // 读入一个单词（遇到空格时结束输入）
getline(cin, s);   // 读入整行（遇到换行符结束输入）
// 输出
cout << s;         // 不换行
cout << s << endl; // 换行

方法

字符串提供的方法有太多了。这里分了几组。

访问方法

s[1]; s.at(1);     // -> char    访问下标为 1 的字符
// 以上和 vector 一样
s.length();        // -> size_t  字符串长度（等价于 s.size()）

拼接方法

s += 'a';   s.push_back('a');  // -> string& 在 s 后面添加字符'a'
s += "abc"; s.append("abc");   // -> string& 在 s 后面添加字符串"abc"
s = s1 + s2                    // -> string  拼接 s1 和 s2
// 可以说 += 和 + 是 string 最强大的运算了，解决了各种情况的拼接问题
s1 == s2;                      // -> bool    直接比较两个字符串是否相同，这不比 strcmp 优雅？

此外，string 也可以按照字典序进行大小比较，直接用 < 或 > 比较即可。

在使用 sort 排序 string 数组时，默认就是按照字典序从小到大排序了。

增删

// 也有 vector 风格的 insert 和 erase
s.insert(2, 'a');  // -> string&  在下标为 2 的位置插入字符'a'
s.erase(1, 2);     // -> string&  从下标为 1 的位置开始，删除两个字符

转换

s.c_str();         // -> char*  返回 C 风格字符串，可以在需要 C 风格字符串时使用

查找

s.find('a', 0);    // 可省略第二个参数，默认为 0
// -> size_t  在字符串中从第 0 位开始查找字符'a'，返回结果的下标。如果没找到就返回 string::npos
s.find("abc", 0);  // -> size_t  也能查找字符串，匹配上前几个字符就算找到了。返回第一个匹配字符的下标。
s.rfind('a');      // 和 find 一样，不过是反向查找。

s.find_first_of("abc", 0);  // 可省略第二个参数，默认为 0
// -> size_t  和 find 差不多，不过是只要字符串里有'a'或'b'或'c‘就算找到了。
s.find_last_of("abc");      // -> size_t  也可以反着找

s.find_first_not_of("abc", 0);  // 可省略第二个参数，默认为 0
// -> size_t  和 find_first_of 反着来，字符串里没有'a'或'b'或'c‘就算找到了。
s.find_last_not_of("abc");      // -> size_t  也可以反着找

截取

s.substr(1, 3);    // -> string 截取从下标 1 开始，长度为 3 的子字符串，返回截取的子字符串

C++11 的转换方法

stoi("2333", nullptr, 10);  // -> int     将字符串转换为整数，第三个参数为进制数，十进制可省略
to_string(2333);            // -> string  将数值转换为字符串

更多方法参见 cplusplus.com

其他

元组（tuple）

和数组差不多，就是没有固定类型，里面的可以同时存储不同类型的数据。

#include <tuple>
using namespace std;
auto t = make_tuple("xm", 1, 'a'); // 赋值
int n = get<1>(t);                 // -> 1 按下标访问

看起来很高级的容器

这里的容器具有一定的特殊功能，自己手写可不好写哦。

优先队列（priority queue）

优先队列会自动在插入时将元素排好顺序，即堆（heap）这种数据结构。默认顶部为最大的值，即大根堆。

需要的头文件

#include <queue>          // 没错，还是队列那个头文件

声明与构造

为方便起见，从这里开始声明和构造器就合一起了。

priority_queue<int> p;    // 声明一个名为 p，存储 int 的优先队列，默认为大根堆，顶部为最大值
priority_queue<int, vector<int>, greater<int> > p;     // 小根堆的声明方法，顶部为最小值
// 你也可以重载运算符 <，让优先队列按自己需要顺序排序

方法

只有通用的和下面的三个，不多。

p.push(2);  // -> void  将整数 2 插入到优先队列
p.top();    // -> int   返回顶部的值
p.pop();    // -> void  弹出顶部元素

映射（map）

了解过 Python 的同学应该都知道，Python 有字典（dict）这个类，可以通过一个键访问到对应的值。JavaScript 也有类似的类型：对象（object），其他语言或许有也哈希表（hash table）。

就拿 Python 举例来说，定义一个像这样表示三个人成绩的字典

grades = {
    'xiaoming': 89,
    'lihua': 93,
    'hanmeimei': 95
}

如果想要根据人名获得对应的成绩，那只需要

xm_grade = grades['xiaoming'] # -> 89

只需要提供键（key）：'xiaoming'，就能得到它对应的值（value）：89。

STL 的 map 容器提供的便是这种功能。map 有两种：

• map：底层实现是红黑树，是按照插入顺序严格有序的，因此访问也慢一些（$O(\log n)$）。
• unordered_map：（C++11 才有的）底层实现是哈希表，无需，访问也更快（$O(1)$）。

需要的头文件

// 按需任选其一
#include <map>
#include <unordered_map> // C++11

声明与定义

// 按需任选其一
map<string, int> grades;       // 定义一个键为 string 型，值为 int 型的 map，名为 grades
unordered_map<string, int> m;

注意：由于这两种 map 基本用法都一样，所以下面都以 map 来举例。

遍历

map 内部存储的元素类型是 pair。

像上面定义的例子，grades 里的元素是 pair<string, int>。

可以理解成，grades 里的元素的是这样的结构体：

struct pair
{
    string first;
    int second;
}

如何遍历 map 呢？就像下面这样：

for (map<string, int>::iterator it = grades.begin(); it != grades.end(); it++) {
    cout << it->first << " => " << it->second << endl;
}

方法

// 还是上面那个例子，这次我们用 C++ 来写

// 像这样可以添加映射
grades["xiaoming"] = 89;
grades["lihua"] = 93;
grades["hanmeimei"] = 95;
// 也可以像这样构造映射，直接赋值
grades = {
    {"xiaoming", 89},
    {"lihua", 93},
    {"hanmeimei": 95}
};

// 像这样可以访问键对应的值
int xm_grade = grades["xiaoming"]; // -> 89

// 支持经典的 insert 和 erase，也可以像下面这样用
grades.insert(pair<string, int>("xiaomeng", 100));
// -> pair<iterator, bool> 相当于 grades["xiaomeng"] = 100，但是它返回 pair
// 其中，first 为插入元素（或已存在的相同键）的迭代器，second 为是否插入成功（如键已存在则插入不成功）
grades.erase("xiaowang");  // -> size_t  删除键为"xiaowang"的映射记录

// 查找方法
map<string, int>::iterator xm = grades.find("xiaoming"); // 和下标访问不同的是，它返回的是一个迭代器
xm->first;  // -> "xiaoming" 键
xm->second; // -> 89         值

集合（set）

数学上的集合是不能出现重复值的，set 容器也是一样的。不过与数学上集合的无序性不同的是，set 容器内部是有序的（默认从小到大排序）。相对地还有个 unordered_set（C++11 才有的），它是无序的，因此速度也比有序的 set 更快。之前也写过关于它的文章。

需要的头文件

// 按需任选其一
#include <set>
#include <unordered_set> // C++11

声明与定义

set<int> s;            // 定义一个名为 s，存储 int 的集合
unordered_set<int> s1;

构造器

为方便起见，下面都以 set 为例。

int a[] = {19, 19, 8, 10};
set<int> s(a, a + 4);      // 构造一个集合 {8, 10, 19}
set<int, greater<int> > s; // 第二个参数可以自定义比较器，这个例子 s 内部从大到小排序

方法

s.insert(8);  // -> pair<iterator, bool> 插入单个元素
// 返回的 pair，first 为插入值（或已存在的相同值）的迭代器，second 为是否插入成功（如已存在则插入不成功）
s.erase(19);  // -> void                 删除指定元素

其他

multiset

允许有重复值的集合，跟优先队列很像，不知道有什么用呢。

bitset

说是集合，却没有集合的特性，就当它是个存储位（bit）的数组吧。每一个元素都是一位，支持位运算。

比起 bool 数组来说，这东西更省空间，要对位进行精确操作可以用它。之前写过关于它的文章。

太长不看版

文章太长了一头雾水？STL 容器看起来很多，但其内核都是相通的。

现代编辑器都拥有完善的代码补全，所以你不用担心方法名能不能记住，你只需要知道这些方法是做什么的就可以了，以及，以上容器的拼写。

这里再列下它们的名字吧。

如果想看详细用法就点击目录吧。注意，要先看通用方法哦。
参考资料：cplusplus.com