Skip to main content

标准库

Summary

标准模板库（Standard Template Library，STL）是 C++ 标准库的一部分，提供一批模板化的通用数据结构与算法，是竞赛编码的基础。文中按类别梳理常用容器：序列式容器有 array、vector、deque、list、forward_list；关联式容器有基于红黑树、元素有序的 set、multiset、map、multimap，以及以哈希实现、平均常数级操作的对应无序版本；容器适配器有 stack、queue、priority_queue；此外还有 bitset、string、pair、tuple 等并不严格属于容器体系的类型。对 deque、stack、queue 逐一列出访问、修改、容量三类常用成员函数，最后汇总 sort、lower_bound、next_permutation 等高频算法，这些算法大多以迭代器为接口，能够作用于不同的容器之上。

参考资料​

标准模板库​

标准模板库（Standard Template Library，STL）是 C++ 标准库的一部分，里面包含了一些模板化的通用的数据结构和算法。

STL 容器​

序列式容器​

array​

vector​

deque​

The "ueue" in "queue" is silent, but not in "deque."
Walski Schölder

访问：

  • front() 返回队首元素
  • back() 返回队尾元素

修改：

  • push_back() 将元素添加到容器末尾
  • pop_back() 移除末元素
  • push_front() 插入元素到容器起始
  • pop_front() 移除首元素
  • clear() 清除内容
  • insert() 在指定位置前插入元素（传入迭代器和元素，O(n)O(n)）
  • erase() 擦除指定位置的元素（传入迭代器，O(n)O(n)）

容量：

  • empty() 检查容器是否为空
  • size() 返回元素数

list​

forward_list​

关联式容器​

set​

multiset​

map​

multimap​

无序关联式容器​

unordered_set​

unordered_multiset​

unordered_map​

unordered_multimap​

容器适配器​

stack​

访问：

  • top() 访问栈顶元素

修改：

  • push() 向栈顶插入元素
  • pop() 移除栈顶元素

容量：

  • empty() 检查容器适配器是否为空
  • size() 返回元素数

queue​

访问：

  • front() 访问第一个元素
  • back() 访问最后一个元素

修改：

  • push() 向队列尾部插入元素
  • pop() 移除首个元素

容量：

  • empty() 检查容器适配器是否为空
  • size() 返回元素数

priority_queue​

其他容器（非 STL 容器）​

bitset​

string​

pair​

tuple​

STL 算法​

  • std::find
  • std::reverse
  • std::unique
  • std::shuffle
  • std::sort
  • std::binary_search
  • std::lower_bound
  • std::upper_bound
  • std::next_permutation
  • std::prev_permutation