各种各样的 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 新增方法,emplaceswap,可参考前篇文章对它们的简单介绍。

双端队列(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 容器看起来很多,但其内核都是相通的。

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

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

中英文名字头文件作用
栈(stack)stack先进后出
队列(queue)queue先进先出
双端队列(deque)deque兼有栈和队列特性
链表(list)list双向链表
向量(vector)vector动态数组
字符串(string)stringchar* 更好用的字符串
优先队列(priority_queue)queue堆,内部有序
映射(map)map构造键到值的映射
集合(set)set不允许重复值,内部有序

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