顺序容器
本文最后更新于：2022年3月19日 凌晨
顺序容器实现能按顺序访问的数据结构。
std::array#
静态的连续数组
定义于头文件
<array>
std::array是封装 固定大小数组 的容器。
| 隐式定义的成员函数 | |
|---|---|
| (构造函数)(隐式声明) | 遵循聚合初始化的规则初始化 array （注意默认初始化可以导致非类的 T 的不确定值） (公开成员函数) |
| (析构函数)(隐式声明) | 销毁 array 的每个元素 (公开成员函数) |
| operator=(隐式声明) | 以来自另一 array 的每个元素重写 array 的对应元素 (公开成员函数) |
| 元素访问 | |
| at(C++11) | 访问指定的元素，同时进行越界检查 (公开成员函数) |
| [operator](C++11) | 访问指定的元素 (公开成员函数) |
| front(C++11) | 访问第一个元素 (公开成员函数) |
| back(C++11) | 访问最后一个元素 (公开成员函数) |
| data(C++11) | 直接访问底层数组 (公开成员函数) |
| 迭代器 | |
| begincbegin(C++11) | 返回指向起始的迭代器 (公开成员函数) |
| endcend(C++11) | 返回指向末尾的迭代器 (公开成员函数) |
| rbegincrbegin(C++11) | 返回指向起始的逆向迭代器 (公开成员函数) |
| rendcrend(C++11) | 返回指向末尾的逆向迭代器 (公开成员函数) |
| 容量 | |
| empty(C++11) | 检查容器是否为空 (公开成员函数) |
| size(C++11) | 返回容纳的元素数 (公开成员函数) |
| max_size(C++11) | 返回可容纳的最大元素数 (公开成员函数) |
| 操作 | |
| fill(C++11) | 以指定值填充容器 (公开成员函数) |
| swap(C++11) | 交换内容 |
std::vector#
定义于头文件 <vector>
std::vector是封装 动态数组 的顺序容器。
| at | 访问指定的元素，同时进行越界检查 (公开成员函数) |
|---|---|
| [operator] | 访问指定的元素 (公开成员函数) |
| front | 访问第一个元素 (公开成员函数) |
| back | 访问最后一个元素 (公开成员函数) |
| data | 直接访问底层数组 (公开成员函数) |
| 迭代器 | |
| begincbegin(C++11) | 返回指向起始的迭代器 (公开成员函数) |
| endcend(C++11) | 返回指向末尾的迭代器 (公开成员函数) |
| rbegincrbegin(C++11) | 返回指向起始的逆向迭代器 (公开成员函数) |
| rendcrend(C++11) | 返回指向末尾的逆向迭代器 (公开成员函数) |
| 容量 | |
| empty | 检查容器是否为空 (公开成员函数) |
| size | 返回容纳的元素数 (公开成员函数) |
| max_size | 返回可容纳的最大元素数 (公开成员函数) |
| reserve | 预留存储空间 (公开成员函数) |
| capacity | 返回当前存储空间能够容纳的元素数 (公开成员函数) |
| shrink_to_fit(C++11) | 通过释放未使用的内存减少内存的使用 (公开成员函数) |
| 修改器 | |
| clear | 清除内容 (公开成员函数) |
| insert | 插入元素 (公开成员函数) |
| emplace(C++11) | 原位构造元素 (公开成员函数) |
| erase | 擦除元素 (公开成员函数) |
| push_back | 将元素添加到容器末尾 (公开成员函数) |
| emplace_back(C++11) | 在容器末尾就地构造元素 (公开成员函数) |
| pop_back | 移除末元素 (公开成员函数) |
| resize | 改变容器中可存储元素的个数 (公开成员函数) |
| swap | 交换内容 (公开成员函数) |
非成员函数#
| (构造函数) | 构造 vector (公开成员函数) |
|---|---|
| (析构函数) | 析构 vector (公开成员函数) |
| operator= | 赋值给容器 (公开成员函数) |
| assign | 将值赋给容器 (公开成员函数) |
| get_allocator | 返回相关的分配器 (公开成员函数) |
| 元素访问 | |
| at | 访问指定的元素，同时进行越界检查 (公开成员函数) |
| operator[] | 访问指定的元素 (公开成员函数) |
| front | 访问第一个元素 (公开成员函数) |
| back | 访问最后一个元素 (公开成员函数) |
| data | 直接访问底层数组 (公开成员函数) |
| 迭代器 | |
| begin cbegin(C++11) | 返回指向起始的迭代器 (公开成员函数) |
| end cend(C++11) | 返回指向末尾的迭代器 (公开成员函数) |
| rbegin crbegin(C++11) | 返回指向起始的逆向迭代器 (公开成员函数) |
| rend crend(C++11) | 返回指向末尾的逆向迭代器 (公开成员函数) |
| 容量 | |
|---|---|
| empty | 检查容器是否为空 (公开成员函数) |
| size | 返回容纳的元素数 (公开成员函数) |
| max_size | 返回可容纳的最大元素数 (公开成员函数) |
| reserve | 预留存储空间 (公开成员函数) |
| capacity | 返回当前存储空间能够容纳的元素数 (公开成员函数) |
| shrink_to_fit(C++11) | 通过释放未使用的内存减少内存的使用 (公开成员函数) |
| 修改器 | |
| clear | 清除内容 (公开成员函数) |
| insert | 插入元素 (公开成员函数) |
| emplace(C++11) | 原位构造元素 (公开成员函数) |
| erase | 擦除元素 (公开成员函数) |
| push_back | 将元素添加到容器末尾 (公开成员函数) |
| emplace_back(C++11) | 在容器末尾就地构造元素 (公开成员函数) |
| pop_back | 移除末元素 (公开成员函数) |
| resize | 改变容器中可存储元素的个数 (公开成员函数) |
| swap | 交换内容 (公开成员函数) |
非成员函数
| std::swap(std::vector)(C++20) | 特化std::swap 算法 (函数模板) |
|---|---|
| erase(std::vector) erase_if(std::vector)(C++20) | 擦除所有满足特定判别标准的元素 (函数模板) |
std::deque#
- 定义于头文件
双端队列
std::deque （ double-ended queue ，双端队列）是有 下标顺序容器，它允许在其首尾两端快速插入及删除。另外，在 deque 任一端插入或删除不会非法化指向其余元素的指针或引用。
与 std::vector 相反， deque 的元素不是相接存储的：典型实现用单独分配的固定大小数组的序列，外加额外的登记，这表示下标访问必须进行二次指针解引用，与之相比 vector 的下标访问只进行一次。
deque 的存储按需自动扩展及收缩。扩张 deque 比扩张 std::vector 更优，因为它不涉及到复制既存元素到新内存位置。另一方面， deque 典型地拥有较大的最小内存开销；只保有一个元素的 deque 必须分配其整个内部数组（例如 64 位 libstdc++ 上为对象大小 8 倍； 64 位 libc++ 上为对象大小 16 倍或 4096 字节的较大者）。
deque 上常见操作的复杂度（效率）如下：
- 随机访问——常数 O(1)
- 在结尾或起始插入或移除元素——常数 O(1)
- 插入或移除元素——线性 O(n)
| 元素访问 | |
|---|---|
| at | 访问指定的元素，同时进行越界检查 (公开成员函数) |
| [operator] | 访问指定的元素 (公开成员函数) |
| front | 访问第一个元素 (公开成员函数) |
| back | 访问最后一个元素 (公开成员函数) |
| 迭代器 | |
| begincbegin(C++11) | 返回指向起始的迭代器 (公开成员函数) |
| endcend(C++11) | 返回指向末尾的迭代器 (公开成员函数) |
| rbegincrbegin(C++11) | 返回指向起始的逆向迭代器 (公开成员函数) |
| rendcrend(C++11) | 返回指向末尾的逆向迭代器 (公开成员函数) |
| 容量 | |
| empty | 检查容器是否为空 (公开成员函数) |
| size | 返回容纳的元素数 (公开成员函数) |
| max_size | 返回可容纳的最大元素数 (公开成员函数) |
| shrink_to_fit(C++11) | 通过释放未使用的内存减少内存的使用 (公开成员函数) |
| 修改器 | |
|---|---|
| clear | 清除内容 (公开成员函数) |
| insert | 插入元素 (公开成员函数) |
| emplace(C++11) | 原位构造元素 (公开成员函数) |
| erase | 擦除元素 (公开成员函数) |
| push_back | 将元素添加到容器末尾 (公开成员函数) |
| emplace_back(C++11) | 在容器末尾就地构造元素 (公开成员函数) |
| pop_back | 移除末元素 (公开成员函数) |
| push_front | 插入元素到容器起始 (公开成员函数) |
| emplace_front(C++11) | 在容器头部原位构造元素 (公开成员函数) |
| pop_front | 移除首元素 (公开成员函数) |
| resize | 改变容器中可存储元素的个数 (公开成员函数) |
| swap | 交换内容 (公开成员函数) |
非成员函数
| std::swap(std::deque) | 特化 std::swap 算法 (函数模板) |
|---|---|
| erase(std::deque) erase_if(std::deque)(C++20) | 擦除所有满足特定判别标准的元素 (函数模板) |
std::forward_list#
定义于头文件
<forward_list>
- 单链表
std::forward_list 是支持从容器中的任何位置快速插入和移除元素的容器。不支持快速随机访问。它实现为单链表，且实质上与其在 C 中实现相比无任何开销。与 std::list 相比，此容器在不需要双向迭代时提供更有效地利用空间的存储。
在链表内或跨数个链表添加、移除和移动元素，不会非法化当前指代链表中其他元素的迭代器。然而，在从链表移除元素（通过 erase_after ）时，指代对应元素的迭代器或引用会被非法化。
| 元素访问 | |
|---|---|
| front(C++11) | 访问第一个元素 (公开成员函数) |
| 迭代器 | |
| before_begincbefore_begin(C++11) | 返回指向第一个元素之前迭代器 (公开成员函数) |
| begincbegin(C++11) | 返回指向起始的迭代器 (公开成员函数) |
| endcend(C++11) | 返回指向末尾的迭代器 (公开成员函数) |
| 容量 | |
| empty(C++11) | 检查容器是否为空 (公开成员函数) |
| max_size(C++11) | 返回可容纳的最大元素数 (公开成员函数) |
| 修改器 | |
| clear(C++11) | 清除内容 (公开成员函数) |
| insert_after(C++11) | 在某个元素后插入新元素 (公开成员函数) |
| emplace_after(C++11) | 在元素后原位构造元素 (公开成员函数) |
| erase_after(C++11) | 擦除元素后的元素 (公开成员函数) |
| push_front(C++11) | 插入元素到容器起始 (公开成员函数) |
| emplace_front(C++11) | 在容器头部原位构造元素 (公开成员函数) |
| pop_front(C++11) | 移除首元素 (公开成员函数) |
| resize(C++11) | 改变容器中可存储元素的个数 (公开成员函数) |
| swap(C++11) | 交换内容 (公开成员函数) |
| 操作 | |
| merge(C++11) | 合并二个已排序列表 (公开成员函数) |
| splice_after(C++11) | 从另一 forward_list 移动元素 (公开成员函数) |
| removeremove_if(C++11) | 移除满足特定标准的元素 (公开成员函数) |
| reverse(C++11) | 将该链表的所有元素的顺序反转 (公开成员函数) |
| unique(C++11) | 删除连续的重复元素 (公开成员函数) |
| sort(C++11) | 对元素进行排序 (公开成员函数) |
| std::swap(std::forward_list)(C++11) | 特化 std::swap 算法 (函数模板) |
|---|---|
| erase(std::forward_list) erase_if(std::forward_list)(C++20) | 擦除所有满足特定判别标准的元素 (函数模板) |
std::list#
定义于头文件
<list>
双链表
std::list 是支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表。与 std::forward_list 相比，此容器提供双向迭代但在空间上效率稍低。
在 list 内或在数个 list 间添加、移除和移动元素不会非法化迭代器或引用。迭代器仅在对应元素被删除时非法化。
| 元素访问 | |
|---|---|
| front | 访问第一个元素 (公开成员函数) |
| back | 访问最后一个元素 (公开成员函数) |
| 迭代器 | |
| begincbegin(C++11) | 返回指向起始的迭代器 (公开成员函数) |
| endcend(C++11) | 返回指向末尾的迭代器 (公开成员函数) |
| rbegincrbegin(C++11) | 返回指向起始的逆向迭代器 (公开成员函数) |
| rendcrend(C++11) | 返回指向末尾的逆向迭代器 (公开成员函数) |
| 容量 | |
| empty | 检查容器是否为空 (公开成员函数) |
| size | 返回容纳的元素数 (公开成员函数) |
| max_size | 返回可容纳的最大元素数 (公开成员函数) |
| 修改器 | |
| clear | 清除内容 (公开成员函数) |
| insert | 插入元素 (公开成员函数) |
| emplace(C++11) | 原位构造元素 (公开成员函数) |
| erase | 擦除元素 (公开成员函数) |
| push_back | 将元素添加到容器末尾 (公开成员函数) |
| emplace_back(C++11) | 在容器末尾就地构造元素 (公开成员函数) |
| pop_back | 移除末元素 (公开成员函数) |
| push_front | 插入元素到容器起始 (公开成员函数) |
| emplace_front(C++11) | 在容器头部原位构造元素 (公开成员函数) |
| pop_front | 移除首元素 (公开成员函数) |
| resize | 改变容器中可存储元素的个数 (公开成员函数) |
| swap | 交换内容 (公开成员函数) |
| 操作 | |
| merge | 合并二个已排序列表 (公开成员函数) |
| splice | 从另一个list中移动元素 (公开成员函数) |
| removeremove_if | 移除满足特定标准的元素 (公开成员函数) |
| reverse | 将该链表的所有元素的顺序反转 (公开成员函数) |
| unique | 删除连续的重复元素 (公开成员函数) |
| sort | 对元素进行排序 (公开成员函数) |
| std::swap(std::list) | 特化 std::swap 算法 (函数模板) |
|---|---|
| erase(std::list)erase_if(std::list)(C++20) | 擦除所有满足特定判别标准的元素 (函数模板) |
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！