本文讲了一些 C++ STL 容器和容器适配器的基本用法和原理，当然没有所有的内容，只是说了一些比较常用的东西。

方法并不是所有都有提到，只是挑了一些常用的，并没有所有都讲（太多了）。

参考资料：

• 《算法竞赛进阶指南》

• 菜鸟教程

• CPlusPlus - Reference

• OI Wiki

• 百度百科

• 文老师的网站 - 关于STL容器的简单总结

在此表示感谢。

0. 什么是 STL

C++ 标准模板库（Standard Template Library），简称 STL，是 C++ 标准库的一部分。

主要有算法（Algorithms）、容器（Containers）、迭代器（Iterators）三大部分。

简单来说，就是一个个封装好的数据结构和算法，方便使用

1. vector

vector 简单来说就是动态数组，包含在 \(\texttt{vector}\) 头文件里面。

实现

那么 vector 是怎么做到动态数组的呢？

vector 内部实现基于倍增思想：

设 \(n,m\) 为 vector 的实际长度和最大长度，向 vector 加入元素前，若 \(n=m\)，则在内存中申请 \(2m\) 的连续空间，并把内容转移到新的地址上（同时释放旧的空间），再执行插入。从 vector 中删除元素后，若 \(n\le m/4\)，则释放一半的空间。

（所以 vector 比较慢。

vector 支持随机访问，因为重载了运算符 []，所以对于任意的下标 \(0 \le i < n\) 可以向数组一样用 [\(i\)] 取值。

因为 vector 不是链表，所以不支持在任意位置 \(O(1)\) 插入元素。

声明

#include<vector>

vector<type> Name;

\(\texttt{type}\) 里面可以放任意的类型，包括结构体和类，\(\texttt{Name}\) 也可以是数组，比如 vector<int> b[10]; 也是可以的。

方法

• 构造函数

  vector() 创建一个空的 vector.

  vector(int nSize) 创建一个 vector，元素个数为 \(\texttt{nSize}\).

  vector(int nSize, const T& t) 创建一个vector，元素个数为 \(\texttt{nSize}\)，且值均为 \(\texttt{t}\).

• \(\texttt{push_back}\) / \(\texttt{pop_back}\)

  push_back(x) 往 vector 的最后加入元素 \(\texttt{x}\).

  pop_back() 删除最后一个元素。

• \(\texttt{size}\) / \(\texttt{empty}\)

  size() 函数返回的是 vector 的元素个数，empty() 函数检测 vector 是否为空。

• \(\texttt{clear}\)

  clear() 函数清空 vector.

• 迭代器

  迭代器就像 STL 容器的“指针”，可以用 * 操作符解除引用。

  迭代器的声明：

  vector<type>::iterator Name;
  

  \(\texttt{type}\) 和指向的 vector 的类型要相同。

  vector<int> a;
  vector<int>::iterator it;
  

  迭代器可以与整数相加进行移动，或者和另外一个迭代器相减得到距离，和指针类似。

• \(\texttt{begin}\) / \(\texttt{end}\)

  begin() 函数返回的是指向 vector 中的第一个元素的迭代器，end() 返回的指向最后一个元素的下一个元素的迭代器。

  为什么要返回一个指向最后一个元素的下一个元素的迭代器呢？

  方便，比如：

  for(vector<int>::iterator it = a.begin(); i != a.end(); i++)
      cout << *it << " ";
  

  这样就可以遍历整个 vector 了。

  因为迭代器像指针，所以 *a.begin() 也等同于 a[0]。

  *a.end() 等同于 a[a.size()]，这里越界访问了。

  同样的，上面的遍历 vector 的代码也可以写成：

  for(int i = 0; i < a.size(); i++)
  	cout << a[i] << " ";
  

• \(\texttt{front}\) / \(\texttt{back}\)

  front() 函数返回 vector 的第一个元素，等价于 *a.begin() 和 a[0]。

  back() 函数返回 vector 的最后一个元素，等价于 *(a.end() - 1) 和 a[a.size() - 1]。

• \(\texttt{insert}\)

  insert(iterator it, const T& x) 向量中迭代器指向元素前增加一个元素 \(\texttt{x}\).

  注意 \(\texttt{insert}\) 的时候，迭代器位置可能将改变，因为元素移动，所以迭代器指向的在修改前后可能不是同一个元素。

• \(\texttt{erase}\)

  erase(iterator it) 删除向量中迭代器指向元素。

  同 \(\texttt{insert}\)，\(\texttt{erase}\) 的时候，迭代器位置可能将改变。

应用

数组需要节省空间时使用。

例：建图。

例题：【模板】建图。

2. queue

queue 就如其名，是一个队列（queue），包含在 \(\texttt{queue}\) 头文件里面。

queue 是一个容器适配器，建立在容器 list 或容器 deque 上。

底层使用链表实现所以不支持随机访问任意元素。

所以 queue 不支持随机访问，也就没有迭代器，插入删除时间复杂度为 \(O(1)\)。

声明

#include<queue>

queue<type> Name;

方法

• 构造函数

  queue() 创建一个空的 queue.

• \(\texttt{push}\) / \(\texttt{pop}\)

  push(x) 往 queue 的最后加入元素 \(\texttt{x}\).

  pop() 弹出第一个元素。

• \(\texttt{size}\) / \(\texttt{empty}\)

  同 vector.

  size() 函数返回的是 queue 的元素个数，empty() 函数检测 queue 是否为空。

• \(\texttt{front}\) / \(\texttt{back}\)

  front() 返回 queue 的第一个元素。

  back() 返回 queue 的最后一个元素。

其他技巧

• 清空队列

  因为 queue 的底层是由链表实现的，链表的每一个元素不一定靠在一起，

  所以 queue 没有办法像 vector 一样 \(O(1)\) 清空队列，且 STL 也没有提供这个函数。

  所以我们如果要清空 queue 就需要自己写。

  代码（其中 \(q\) 为 queue 定义的队列）：

  while(!q.empty()) q.pop();
  

  意思：弹出队列的第一个元素直到队列为空。

  注意时间复杂度是 \(O(n)\) 的。

应用

队列就。。队列。

例：广搜。

例题：滑动窗口 /【模板】单调队列。

3. priority_queue

priority 英[praɪˈɒrəti] 美[praɪˈɔːrəti]

n. 优先事项; 最重要的事; 首要事情; 优先; 优先权; 重点; (车辆的)优先通行权;

[例句] But respondents ranked it last on a list of priorities.

但被调查者将它排在优先事项列表的最后。

[其他] 复数：priorities

priority_queue 即优先队列，或叫优先级队列。

priority_queue 和 queue 一样，都包含在头文件 \(\texttt{queue}\) 里。

同 queue，priority_queue 也是一个容器适配器，建立在容器 vector 上。

优先队列

什么是优先队列？

明显地，是一个队列。但这个队列有一个优先级，下标越小，优先级越高。

比如规定数字大的优先级越高，那么这个队列就是一个不升序列。

为了维护这个队列的优先性，每进入一个元素或删除一个元素，都要进行一定次数的交换，以维护队列。

实现

如何实现优先队列？

你可能会想每次操作去对这个序列进行排序。

但是排序的时间复杂度太高了，大部分时间复杂度低的排序都为 \(O(n\log n)\)，如果我们有 \(n\) 个元素，那么最多会到 \(O(n^2\log n)\)，很显然不够高效

还有一个是插入排序和一部分的冒泡排序，但是时间复杂度最坏也会到达 \(O(n)\).

那有没有更快的？

有，堆。

为了方便，STL 使用了二叉堆（不知道的可以看 OI Wiki - 二叉堆），一次操作维护时间复杂度最坏为 \(O(\log_2n)\)，已经很高效了。

但也因为是堆，所以 priority_queue 不支持随机访问，也就没有迭代器。

STL 有内置的实现堆的函数，可以直接调用，priority_queue 就用了这几个函数。

这几个函数是对数组使用的，也可以用在 vector 上，而 priority_queue 就使用了 vector，所以 priority_queue 需要一个 vector.

声明

#include<queue>

priority_queue<type> Name;

priority_queue<type,vector<type> > Name;

priority_queue<type, vector<type>, functional> Name;

priority_queue 有 \(3\) 种声明方法，第一种，即定义一个 priority_queue，类型为 \(\texttt{type}\)，名称为 \(\texttt{Name}\).

如果以第一种定义，则定义了一个以元素大到小的 priority_queue。

但是因为 STL 是泛型编程，要适用于任意的类型。对于一些结构体、类，怎么比大小？

你可能知道了，可以重载运算符。在 priority_queue 中，使用 < 来比较大小的，所以你可以重载运算符 <。

不知道重载运算符可以看 菜鸟教程 - C++ 重载运算符和重载函数。

如果有两个优先队列，同一个类型，但比较方法不一样，为了再写一个类型定义另外一个比较方法，

于是就有了第三种声明方式，其中 \(\texttt{functional}\) 是比较方式，用仿函数。

仿函数是一个重载了 () 运算符的类或结构体，因为可以像函数一样调用但又不是函数，所以被叫做仿函数。在这里不对仿函数进行详细的讲解，想了解可以看 百度百科 - 仿函数。

第二种是一个相对完整的写法，传了一个 vector，如果不给这个 vector 数组用第一种定义方法，则 priority_queue 会自己定义。

如果你就只想让队列由小到大排，且里面的元素就只是单纯的数，但又不想重载运算符或写仿函数，其实 STL 已经提供了一个内置的仿函数 greater 可以直接使用，像这样：

priority_queue<int, vector<int>, greater<int> > q;

这样就定义了一个从小到大排的整型优先队列。

方法

• 构造函数

  priority_queue() 创建一个空的 priority_queue.

• \(\texttt{push}\) / \(\texttt{pop}\)

  push(x) 往 priority_queue 加入元素 \(\texttt{x}\).

  pop() 弹出队首元素。

• \(\texttt{size}\) / \(\texttt{empty}\)

  同 vector.

  size() 函数返回的是 priority_queue 的元素个数，empty() 函数检测 priority_queue 是否为空。

• \(\texttt{top}\)

  top() 返回 priority_queue 的队首元素。

其他技巧

• 清空队列

  可以像 queue 一样清空队列。

应用

比如需要用到堆的地方。

例题：【模板】堆。

4. set

set 除了设置、放，还有集合的意思。

所以 set 即集合，包含在 \(\texttt{set}\) 头文件中。

集合

关于集合的最简单的说法就是在朴素集合论（最原始的集合论）中的定义，即集合是“确定的一堆东西”，集合里的“东西”则称为元素。现代的集合一般被定义为：由一个或多个确定的元素所构成的整体。

实现

set 保证元素有序，基于红黑树实现。

红黑树是一颗二叉平衡搜索树，平衡树是二叉搜索树中的一类，这个搜索树满足任意节点的子树的高度差都小于等于 \(1\)，操作一次时间复杂度可以做到 \(O(\log n)\).

红黑树怎么实现？我不会，直接查 百度 - 红黑树。

声明

#include<set>

set<type> Name;

set<type, functional> Name;

定义一个 set，类型为 \(\texttt{type}\)，名称为 \(\texttt{Name}\).

一样的，因为 set 保证元素有序又要泛型编程，所以和 priority_queue 一样，结构体、类需要重载运算符 <（搜索树是需要比较的）或者写仿函数。

方法

这里的左边指优先级高，右边指优先级低。

• 构造函数

  set() 创建一个空的 set.

• \(\texttt{size}\) / \(\texttt{empty}\)

  不讲了。

• \(\texttt{clear}\)

  clear() 函数清空 set.

• \(\texttt{insert}\) / \(\texttt{erase}\)

  insert(x) 往 set 里加入元素 \(\texttt{x}\)，重复插入无效。

  erase(x) 删除元素 \(\texttt{x}\).

  erase(iterator it) 删除迭代器 \(\texttt{it}\) 指向的元素。

• \(\texttt{count}\)

  count(x) 查看元素 \(\texttt{x}\) 的个数。因为重复插入无效，所以返回不是 \(1\) 就是 \(0\)。

• \(\texttt{begin}\) / \(\texttt{end}\)

  begin() 函数返回的是指向 set 中的最左边的元素的迭代器，end() 返回的指向最右边的元素的下一个元素的迭代器。

• \(\texttt{find}\)

  find(x) 返回一个指向 \(\texttt{x}\) 位置的迭代器，找不到则返回 end() 的位置。

其他技巧

• \(\texttt{lower_bound}\) / \(\texttt{upper_bound}\)

  lower_bound(x) 返回一个指向大于等于 \(\texttt{x}\) 的第一个元素的迭代器。

  upper_bound(x) 返回一个指向大于 \(\texttt{x}\) 的第一个元素的迭代器。

应用

就。。集合。

例题：[NOIP2006 普及组] 明明的随机数。

5. map

map 除了地图，还有映射的意思。

map 即映射，包含在 \(\texttt{map}\) 头文件中。

映射

什么是映射，在数学里，映射是个术语，指两个元素的集之间元素相互“对应”的关系。

两个非空集合 \(A\) 与 \(B\) 间存在着对应关系 \(f\)，而且对于 \(A\) 中的每一个元素 \(a\)，\(B\) 中总有唯一的一个元素 \(b\) 与它对应，就这种对应为从 \(A\) 到 \(B\) 的映射，记作 \(f:A→B\)。其中，\(b\) 称为元素 \(a\) 在映射 \(f\) 下的像，记作：\(b=f(a)\)。\(a\) 称为 \(b\) 关于映射 \(f\) 的原像。集合 \(A\) 中所有元素的像的集合称为映射 \(f\) 的值域，记作 \(f(A)\)。

百度百科上抄的，看起来有点复杂，但其实说得已经很好理解了，可以多读几遍。

明显地，\(B\) 集合里面的元素不一定都用得上，也有可能一个元素对应 \(A\) 中的多个元素，也就是原像可能没有或者不止一个，所以一般的两个集合不存在逆映射。

在 map 中，\(A\) 集合叫做键，\(B\) 集合叫做值.

实现

map 保证元素有序，和 set 一样基于红黑树实现。

所以操作一次时间复杂度同 set 可以做到 \(O(\log n)\).

声明

#include<map>

map<key_type,value_type> Name;

map<key_type, value_type, functional> Name;

\(\texttt{key_type}\) 相当于集合 \(A\) 的类型，或者是键的类型。

\(\texttt{value_type}\) 相当于集合 \(B\) 的类型，或者是值的类型。

\(\texttt{functional}\) 不解释（之前说过了）。

方法

这里的左边指优先级高，右边指优先级低。

• 构造函数

  map() 创建一个空的 map.

• \(\texttt{size}\) / \(\texttt{empty}\)

  不讲了。

• \(\texttt{clear}\)

  clear() 函数清空 map.

• 插入元素

  • \(\texttt{insert}\)

    insert(pair<key_type, value_type> x) \(\texttt{x}\) 为一个 pair，第一个值为键，第二个值为值，即键对应值。

    不知道 pair 看这里 百度百科 - pair。

  • “数组”方式

    set<string, int> s;
    
    s["123"] = 1;
    

    map 重载了运算符 [] 和 =，可以像数组一样更改键所对应的值。

• \(\texttt{erase}\)

  erase(x) 删除键 \(\texttt{x}\)。

  erase(iterator it) 删除迭代器 \(\texttt{it}\) 指向的键。

• \(\texttt{count}\)

  count(x) 查看键 \(\texttt{x}\) 的个数。因为重复插入无效（像是唯一的），所以返回不是 \(1\) 就是 \(0\)。

• \(\texttt{begin}\) / \(\texttt{end}\)

  begin() 函数返回的是指向 map 中的最左边的键的迭代器，end() 返回的指向最右边的键的下一位的迭代器。

• 查找元素

  • \(\texttt{find}\)

    find(x) 返回一个指向键 \(\texttt{x}\) 位置的迭代器，找不到则返回 end() 的位置。

  • “数组”方式

    set<string, int> s;
    
    cout << s["123"] << endl;
    

    map 重载了运算符 []，可以像数组一样获取键所对应的值。

应用

标记一个值但是数据很大时可以用 map 代替数组标记。

例题：【模板】哈希。

6. 其他

STL 的容器、容器适配器不止这些，比如还有：

序列容器：list、forward_list、deque、array 等。

关联容器：multiset、multimap、unordered_set、unordered_map、bitset 等。

容器适配器：stack.

...