本文介绍了 C++ STL 的简单使用。陈列不全，仅陈列自认为较有用的内容。并期待在有一天加入 STL 源码级的分析。

容器

序列容器

vector（向量）

动态大小阵列的序列容器。

:::default

vector<bool> 是一种动态的 bitset

:::

常见操作复杂度：

• 随机存取 $\mathcal{O}(1)$
• 尾部插入 $\mathcal{O}(1)$
• 其他位置插入 $\mathcal{O}(n)$​

类型成员

• value_type
• size_type
• difference_type ：两个迭代器之间的距离
• iterator
• const_iterator
• reverse_iterator
• const_reverse_iterator

成员函数

// vector 的四种初始化形式
vector(const Allocator& = Allocator());
vector(size_type n, const T& value = T(), const Allocator = Allocator());
template<class InputIterator>
    vector(InputIterator first, InputIterator last, const Allocator = Allocator);
vector(const vector<T, Allocator> &x);

// 数据存取
vector<int> v{1, 2, 3};
v[0];        // 不可越界，与内置数组不同
v.front(); // 取出第一个元素的引用
v.back(); // 取出最后一个元素的引用
v.data;    // 返回一个指针，这里为 int *

// 迭代器
v.begin();
v.cbegin(); // const 属性，只读迭代器
v.end();
v.cend();

// 容量、大小相关
v.empty();
v.size();
v.max_size();                         // 所能分配的 size 最大值
v.reserve(vector::size_type); // 分配元素数量大小至参数
v.capacity();                          // 目前动态分配的存储量
v.shrink_to_fit();                   //  将多余的分配量 free

// 清空元素
v.clear();

// 插入元素返回插入的第一个元素的迭代器
v.insert(pos, elem);       // 在 pos 位置之前插入元素 elem
v.insert(pos, n, elem);   // 在 pos 位置之前插入 n 个 elem
v.insert(pos, first, last); // 在 pos 位置之前插入其他容器的区域元素
v.insert(pos, initlist);     // 在 pos 位置之前插入初始化列表

// 插入一个元素，直接使用构造函数初始化新元素而不像 insert 一样先构造再拷贝或移动
v.emplace(pos, elem);

// 删除元素，返回删除后的第一个元素的迭代器
v.erase(itr pos);             // 删除迭代器位置的值
v.erase(itr first, itr last); // 删除前闭后开区间的元素

// 在末尾插入元素
v.push_back(elem);
v.emplace_back(elem);

// 在末尾删除元素
v.pop_back();

// 强行限定容器大小，新增或切除
v.resize(vector::size_type);

// 交换容器，常数级，可以远离作用域达到释放多余空间的目的
v.swap(v2);

array（数组）

deque（双端队列）

forward_list（单链表）

list（双向链表）

有序关联容器

无序关联容器

容器适配器