OI-wiki 序列容器全解：vector / array / deque / list / forward_list 的用法、复杂度与底层实现

OI-wiki 序列容器全解vector / array / deque / list / forward_list 的用法、复杂度与底层实现【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikistd::vector、std::array、std::deque、std::list、std::forward_list是 C STL 中五大序列容器Sequence Containers它们按线性顺序组织元素却在内存布局、增删效率与随机访问能力上各具特性。本篇基于 OI-wiki docs/lang/csl/sequence-container.md 整理而成系统讲解每个容器的构造函数、元素访问、迭代器、容量管理与复杂度细节并结合仓库内实际代码如前缀和、WQS 二分等例题说明在竞赛环境中的选型与使用技巧帮助读者在开多大数组与动态增长之间做出正确取舍。上图来自 docs/lang/csl/container.md直观展示了 STL 容器的整体分类。其中的序列式容器共五种向量vector尾部可高效增删的顺序表、数组arrayC11 定长顺序表C 风格数组的简单包装、双端队列deque双端均可高效增删的顺序表、列表list可双向遍历的链表、单向列表forward_list仅能单向遍历的链表。与关联式容器set/map等不同序列容器强调元素的顺序性元素间不存在由比较谓词决定的排列关系。序列容器的共同点所有 STL 容器都以containerNametypeName, ... name的形式声明模板参数内的个数与形式因容器而异其本质原因在于 STL 是标准模板库容器均为模板类。序列容器同样遵循 容器文档 中列举的共有约定具有赋值运算符与复制构造函数begin()/end()返回指向首元素的迭代器、指向末尾元素后继不指向任何元素的迭代器size()返回容器内元素个数max_size()返回容器理论上能存储的最大元素个数依容器类型和存储类型而变empty()返回容器是否为空swap()交换两个容器/!////按字典序比较两个容器。序列容器的差异主要集中在底层内存布局与迭代器能力上这直接决定了各操作的复杂度。依据 迭代器文档vector与array提供随机访问迭代器支持加减与比较运算C17 起进一步满足连续迭代器要求deque提供随机访问迭代器但底层不连续list仅提供双向迭代器支持自减forward_list仅提供前向迭代器只支持自增。迭代器类别决定了哪些 STL 算法 可以直接套用——这正是list需要自带sort()、merge()等成员函数的原因下文会展开说明。vector动态增长的连续数组std::vector是 STL 提供的内存连续的、可变长度的数组亦称列表数据结构能够提供线性复杂度的插入和删除以及常数复杂度的随机访问。为什么使用vector作为 OIer对程序效率的追求远比对工程级别的稳定性要高。由于vector对内存的动态处理其时间效率在部分情况下低于静态数组在 OJ 服务器不一定开全优化的情况下表现更差因此在正常存储数据时通常不选择vector。但以下三个优秀特性使vector在特定场景下不可或缺。其一vector可以动态分配内存。很多时候我们无法提前开好那么大的空间例如预处理 1~n 中所有数的约数。尽管能知道数据总量在空间允许的级别但单份数据可能非常大此时需要vector把内存占用量控制在合适范围内。vector还支持动态扩容在内存非常紧张时该特性尤其有用。其二vector重写了比较运算符及赋值运算符。它重载了六个比较运算符按字典序实现可以方便地判断两个容器是否相等复杂度与容器大小成线性关系。例如可以利用vectorchar实现字符串比较当然用std::string更快更方便。此外vector重载了赋值运算符使数组整体拷贝更加方便。其三vector便利的初始化。由于vector重载了运算符可以方便地进行整体赋值从 C11 起还支持列表初始化如vectorint data {1, 2, 3};。构造函数以下代码覆盖了vector的全部常用构造方式假设已usingstd命名空间相关类型// 1. 创建空 vector; 常数复杂度 vectorint v0; // 1. 向 vector 中插入前 3 个元素时保证常数时间复杂度 v0.reserve(3); // 2. 创建初始空间为 3 的 vector元素默认值为 0; 线性复杂度 vectorint v1(3); // 3. 创建初始空间为 3 的 vector元素默认值为 2; 线性复杂度 vectorint v2(3, 2); // 4. 创建初始空间为 3 的 vector元素默认值为 1 // 并且使用 v2 的空间配置器; 线性复杂度 vectorint v3(3, 1, v2.get_allocator()); // 5. 创建 v2 的拷贝 vector v4内容与 v2 相同; 线性复杂度 vectorint v4(v2); // 6. 创建 v4 的拷贝 vector v5内容是 {v4[1], v4[2]}; 线性复杂度 vectorint v5(v4.begin() 1, v4.begin() 3); // 7. 将 v2 移动构造到新 vector v6不发生拷贝; 常数复杂度; 需要 C11 vectorint v6(std::move(v2)); // 或者 v6 std::move(v2);原文档附带的测试代码可验证上述构造结果用copy(v.begin(), v.end(), ostream_iteratorint(cout, ))逐一输出各容器可以看到v1 0 0 0、v2 2 2 2、v4 2 2 2、v5 2 2取自v4[1]与v4[2]而v6因移动构造继承了v2的内容、v2变为空。元素访问vector提供五种元素访问方式区别在于是否做越界检查at()v.at(pos)返回下标pos处元素的引用越界时抛出std::out_of_range异常operator[]v[pos]返回下标pos处元素的引用不执行越界检查front()返回首元素的引用back()返回末尾元素的引用data()返回内部连续内存空间首元素的指针可与 C 风格接口互操作。迭代器vector提供四组迭代器详见 迭代器文档begin()/cbegin()指向首元素的迭代器*begin frontend()/cend()指向容器尾端占位符的迭代器注意其指向位置没有元素rbegin()/crbegin()指向逆向数组首元素的逆向迭代器可理解为正向容器的末元素rend()/crend()指向逆向数组末元素后一位置的迭代器对应容器首元素的前一个位置没有元素。含字符c的为只读const迭代器不能通过它修改vector中元素的值若vector本身是只读的则普通迭代器与只读迭代器完全等价。只读迭代器自 C11 起支持。长度与容量vector的长度size指有效元素数量容量capacity指实际分配的内存长度两者是独立存储的两个量实现细节见后文。与长度相关empty()返回bool即v.begin() v.end()true为空size()返回元素数量即std::distance(v.begin(), v.end())resize(n)改变长度为n。若n大于当前长度则补充元素提供了补充值则使用之否则用默认值若n小于当前长度则保留前n个元素删除其余元素max_size()返回容器的最大可能长度。与容量相关reserve()预留一定内存空间避免后续不必要的内存分配与拷贝capacity()返回当前已为多少个元素分配了空间shrink_to_fit()使容量与长度一致去除未使用的容量。元素增删及修改clear()清除所有元素insert()支持在某个迭代器位置插入单个或多个元素复杂度与pos到末尾的距离成线性而非常数erase()删除某个迭代器或区间的元素返回最后被删除位置的迭代器复杂度与insert一致push_back()末尾插入一个元素均摊常数复杂度最坏为线性复杂度pop_back()删除末尾元素常数复杂度swap()与另一容器交换常数复杂度而非线性。vector的实现细节vector的底层其实是定长数组其动态扩容靠的是避免数量溢出的操作容器分别存储元素数量长度 $n$与已分配内存最多可容纳的元素数量容量 $N$。当向vector添加元素时若发现 $n N$容器会分配一个尺寸为 $2N$ 的新数组将旧数据从原位置拷贝到新数组再释放原内存。尽管单次扩容操作的渐近复杂度是 $O(n)$但可以证明其均摊复杂度为 $O(1)$末尾删除与元素访问则始终是 $O(1)$。因此只要对vector的尺寸估计得当并善用resize()与reserve()就能使vector的效率与定长数组差距不大。仓库中即有此类实践在 docs/dp/code/opt/wqs-binary-search/black-white-mst-1.cpp 中程序在读入边之前先执行edges[0].reserve(E);与edges[1].reserve(E);即预先为白边、黑边各预留E条边的容量从而将后续push_back的均摊常数时间稳定下来docs/basic/code/prefix-sum/prefix-sum_1.cpp 则直接以std::vectorint承载前缀和数组配合下标从 1 开始的索引约定使用。vectorbool一个需要谨慎的特化标准库为bool提供了vector的特化每个「bool」只占 1 bit且支持动态增长。但其operator[]的返回值类型不是bool而是vectorbool::reference行为与普通vector不一致例如vec[0] i不等于vec[i]。因此使用vectorbool需谨慎可以考虑用dequebool或vectorchar替代若需要节省空间请直接使用bitset。如 bitset 文档 所述vectorbool的存储方式与bitset相同按位压缩区别在于其支持动态开空间而bitset在编译期就确定大小但bitset提供了丰富的库函数且可实现 SIMD 优化故竞赛中通常优先bitset。arrayC11固定长度的连续数组std::array是 STL 提供的内存连续的、固定长度的数组数据结构其本质是对原生数组的直接封装。为什么使用arrayarray相比vector牺牲了动态扩容特性换来了与原生数组几乎一致的性能在开满优化的前提下。因此在支持 C11 的环境下凡是能用原生数组的地方几乎都可以把定长数组换成array动态分配的数组则替换为vector。array提供了 STL 容器统一的接口迭代器、size()、at()等却不会有vector扩容带来的潜在常数开销。成员函数隐式定义的成员函数函数作用operator以来自另一array的每个元素重写array的对应元素元素访问函数作用at访问指定的元素同时进行越界检查operator[]访问指定的元素不进行越界检查front访问第一个元素back访问最后一个元素data返回指向内存中数组第一个元素的指针at若遇到pos size()的情况会抛出std::out_of_range。容量函数作用empty检查容器是否为空size返回容纳的元素数max_size返回可容纳的最大元素数由于每个array都是固定大小容器size()返回值等于max_size()返回值。操作函数作用fill以指定值填充容器swap交换内容注意交换两个array是 $\Theta(\text{size})$ 的而非与常规 STL 容器一样为 $O(1)$。这是因为array内部就是一块定长的连续内存交换必须逐元素进行。非成员函数函数作用operator等按照字典序比较array中的值std::get访问array的一个元素std::swap特化的std::swap算法std::get以编译期常量下标访问元素返回值在编译期确定这使array可以与元组式语法协同使用。使用示例// 1. 创建长度为 3 的 array; 常数复杂度 std::arrayint, 3 v0; // 2. 用指定常数创建 array; 常数复杂度 std::arrayint, 3 v1{1, 2, 3}; v0.fill(1); // 填充数组 // 访问数组 for (int i 0; i ! v1.size(); i) cout v1[i] ;deque双端队列std::deque是 STL 提供的 双端队列 数据结构能够提供线性复杂度的插入和删除以及常数复杂度的随机访问。数据结构章节中的 双端队列一节 给出了 STL 中deque的模板声明templateclass T, class Allocator std::allocatorT class deque;其中T为存储类型Allocator为分配器一般保持默认即可。使用方法deque的迭代器函数与vector相同此处不再赘述重点看构造函数// 1. 定义 int 类型的空双端队列 v0 dequeint v0; // 2. 定义 int 类型的双端队列 v1初始大小为 10; 线性复杂度 dequeint v1(10); // 3. 定义 int 类型的双端队列 v2初始化为 10 个 1; 线性复杂度 dequeint v2(10, 1); // 4. 复制已有的双端队列 v1; 线性复杂度 dequeint v3(v1); // 5. 创建 v2 的拷贝 deque v4内容是 v2.begin() 至 v2.begin()3; 线性复杂度 dequeint v4(v2.begin(), v2.begin() 3); // 6. 将 v2 移动构造到新 deque v5不发生拷贝; 常数复杂度; 需要 C11 dequeint v5(std::move(v2));元素访问与vector一致但无法访问底层内存at()与operator[]均为常数复杂度前者执行越界检查、后者不执行front()与back()分别返回首、末元素引用。长度相关函数与vector一致但没有reserve()和capacity()函数仍保留shrink_to_fit()。这是由deque分段连续的内存模型决定的——它没有单一连续内存块可供预留。元素增删及修改与vector一致并额外支持头部操作clear()清除所有元素insert()支持在某个迭代器位置插入单个或多个元素复杂度与pos到两端距离的较小者成线性erase()删除某个迭代器或区间的元素返回最后被删除位置的迭代器复杂度与insert一致push_front()头部插入一个元素常数复杂度pop_front()删除头部元素常数复杂度push_back()末尾插入一个元素常数复杂度pop_back()删除末尾元素常数复杂度swap()与另一容器交换常数复杂度。deque的实现细节deque通常的底层实现是多个不连续的缓冲区而每个缓冲区内部的内存是连续的。每个缓冲区还会记录首指针和尾指针用来标记有效数据的区间当一个缓冲区填满后会在之前或之后分配新的缓冲区来存储更多数据。这种分段连续结构使得deque能在 $O(1)$ 时间内在两端增删元素同时保持常数复杂度的随机访问多一次指针跳转但代价是失去了reserve/capacity这类面向单块连续内存的能力。更详细的实现剖析可参考 《STL 源码剖析》 中关于deque的章节。list双向链表std::list是 STL 提供的 双向链表 数据结构能够提供线性复杂度的随机访问以及常数复杂度的插入和删除。使用上与deque基本相同但增删操作和访问的复杂度不同迭代器、长度、元素增删及修改相关的函数与deque相同。元素访问由于list的实现是链表它不提供随机访问接口。若需要访问中间元素必须使用迭代器从begin()或end()逐步移动。仅有的直接访问接口是front()返回首元素的引用back()返回末尾元素的引用。针对链表特性的操作list还提供了一些针对其特性实现的成员函数。由于通用 STL 算法 通常需要随机访问迭代器list提供了特殊实现以便高效使用splice()把另一个list中的元素或区间、整个链表拼接到指定位置可做到常数时间remove()/remove_if()按值或按谓词删除元素sort()归并排序式排序链表无法使用需要随机访问的std::sortunique()去除相邻重复元素merge()将两个已排序的list归并同样为链表特化实现。对于需要在序列中频繁任意位置插入/删除的场景list的 $O(1)$ 插入删除在已知迭代器位置的前提下是显著优势但要付出随机访问为 $O(n)$ 的代价。forward_listC11单向链表std::forward_list是 STL 提供的 单向链表 数据结构相比std::list减小了空间开销——每个节点只需一个后继指针而非两个。forward_list的使用方法与list几乎一致但迭代器只有单向的前向迭代器只支持不支持--因此其具体用法不再赘述。空间上的节约使其适合存储海量小元素的场景但相应地失去了rbegin()/rend()反向遍历、back()等依赖双向结构的能力。五大序列容器复杂度与选型速查综合上述各节将五大序列容器的核心特性归纳如下便于在写题时快速决策容器内存布局随机访问头部增删尾部增删任意位置插入/删除迭代器类别array单块连续定长$O(1)$不支持不支持不支持定长随机访问/连续vector单块连续动态扩容$O(1)$$O(n)$需移动元素均摊 $O(1)$$O(n)$与到末尾距离成线性随机访问/连续deque多块连续缓冲区$O(1)$$O(1)$$O(1)$$O(\min(\text{pos},\ \text{size}-\text{pos}))$随机访问list双向链表节点$O(n)$$O(1)$$O(1)$$O(1)$已知迭代器位置双向forward_list单向链表节点$O(n)$$O(1)$不支持$O(1)$已知迭代器位置前向选型建议结合竞赛实际需要随机访问、元素个数确定优先array性能与原生数组几乎一致且享有 STL 统一接口需要随机访问、元素个数动态增长优先vector配合reserve()预分配以消除扩容抖动这正对应容器适配器中priority_queue默认以vector为底层容器 的设计需要两端高效增删如滑动窗口类题目优先deque其双端 $O(1)$ 增删是单调队列等算法的硬件基础stack与queue也默认以deque为底层容器需要在已知位置频繁插入/删除、几乎不做随机访问优先list双向或forward_list单向、更省空间只需存 0/1 且需按位运算避免vectorbool直接使用bitset预先能开够空间的静态场景原生数组或array依然是 OI 环境下的稳妥选择——vector的动态扩容在未开启优化时会有额外的常数开销这与 OI-wiki 算法基础与复杂度分析 中常数不可忽略的告诫一脉相承。以上内容完整覆盖了 sequence-container.md 中vector、array、deque、list、forward_list五大序列容器的构造、访问、增删、容量管理、实现细节与复杂度结论并补充了与仓库内 容器分类、迭代器、容器适配器、bitset、双端队列、链表 等章节的交叉引用以及前缀和、WQS 二分例题代码中的真实使用证据可作为竞赛编码时查阅序列容器接口与复杂度的速查手册。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考