C 面试必问STLvector、deque 和 list 区别文章目录C 面试必问STLvector、deque 和 list 区别一、先看三种顺序容器的内存结构1. vector连续动态数组2. deque分段连续空间3. list双向链表二、元素访问at() 和 operator[] 有什么区别三、vector 的空间管理1. reserve() 和 resize() 有什么区别2. vector扩容机制3. 插入元素emplace_back() 和 push_back() 怎么选4. 怎样释放 vector 的多余容量clear() 和 resize(0)shrink_to_fit()使用 swap 释放空间四、扩容与迭代器失效1. 为什么 vector 扩容后全部失效2. vector 未扩容时插入和删除会影响哪些位置3. 为什么 deque 的首尾操作和中间操作失效规则不同4. 为什么 list 通常只让被删除节点的迭代器失效五、vector 是线程安全的吗六、什么时候选哪一个七、总结八、高频面试题精选vector、deque和list都能保存一组元素但底层布局不同导致随机访问、插入删除、缓存命中率和迭代器稳定性完全不同。一、先看三种顺序容器的内存结构这张图可以先建立整体认识vector使用连续内存deque使用由中控结构管理的分段连续内存list则由分散节点通过指针连接。对比项vectordequelist底层结构连续动态数组分段连续数组双向链表随机访问O(1)常数小O(1)需要定位分段不支持尾部插入均摊 O(1)O(1)O(1)头部插入O(n)O(1)O(1)中间插入O(n)O(n)已知位置时 O(1)内存连续是否否缓存局部性最好较好较差需要注意两个复杂度前提vector尾部插入是均摊 O(1)容量不足并触发扩容时需要移动或复制已有元素单次操作为 O(n)。list只有在已经拿到插入或删除位置的迭代器时修改链接才是 O(1)从头查找该位置仍然需要 O(n)。1.vector连续动态数组std::vector的核心是动态数组。它封装一块连续内存元素布局和普通数组一样紧密因此支持 O(1) 随机访问也具有较好的 CPU 缓存局部性与普通数组不同的是它会自动管理元素生命周期和底层内存并在容量不足时动态扩容。主流标准库实现通常可以用三个指针理解start指向连续内存的起始位置也是第一个元素的位置。finish指向最后一个已构造元素的下一个位置。end_of_storage指向整块已分配内存的末尾位置。因此可以得到sizefinish-start;capacityend_of_storage-start;[start, finish)中是已经构造完成、可以访问的元素[finish, end_of_storage)只是预留的原始存储空间其中还没有有效元素不能直接访问。当finish end_of_storage时现有容量已经用完。vector通常会申请一块更大的连续内存将原有元素移动或复制过去再销毁旧元素并释放旧内存。这也是扩容后原有迭代器、指针和引用失效的根本原因。三指针只是常见实现模型。C 标准要求元素连续存储并规定接口行为但不规定vector对象必须包含哪几个成员也不规定固定的扩容倍数。2.deque分段连续空间deque通常由中控数组和多个固定大小的缓冲块组成。中控数组保存各缓冲块的地址访问元素时可以根据下标计算块编号和块内偏移因此随机访问仍为 O(1)但需要比vector多一次间接定位。在头部或尾部空间不足时deque通常只需申请新的缓冲块并把块地址接入中控数组不必像vector那样搬迁全部元素因此两端插入和删除通常为 O(1)。但在中间插入或删除时仍可能移动大量元素复杂度为 O(n)。各缓冲块内部连续块与块之间却不保证相邻所以deque不是整体连续内存不能把首元素地址当作普通数组起点使用。分段寻址还会增加一次间接访问因此随机访问虽然是 O(1)实际常数和缓存局部性通常不如vector。这是主流标准库的常见实现思路。C 标准规定deque的接口和复杂度要求但不强制采用图中的具体中控数组布局或固定缓冲块大小。3.list双向链表list的每个节点分别保存元素、前驱指针和后继指针节点通常独立分配再通过指针连接成双向链表。插入或删除节点时只需修改相邻节点的链接因此在已经拿到目标迭代器时操作为 O(1)而且不会搬迁其他元素。代价是list不支持随机访问。查找第i个元素或寻找插入位置都需要顺序遍历复杂度为 O(n)。每个节点还要额外保存两个指针并承担独立分配开销节点在内存中分散缓存局部性较差所以实际遍历速度通常明显慢于vector。二、元素访问at()和operator[]有什么区别两者都能按照下标访问元素时间复杂度都是 O(1)并且都会返回元素的引用。核心区别在于是否进行边界检查对比项v.at(i)v[i]边界检查会检查i v.size()不检查越界结果抛出std::out_of_range未定义行为时间复杂度O(1)O(1)适用场景下标来自外部或不能确定合法已通过程序逻辑保证下标合法at()的边界检查会增加一次判断但通常不能简单断言它一定明显更慢。只有在性能敏感的高频路径中并且程序已经严格保证下标合法时才有充分理由优先使用operator[]。无论使用哪一种方式合法下标范围都是[0, size())。capacity()大于size()并不代表预留区域中的位置可以访问v[v.size()]同样越界。对于const vector两种接口返回的都是常量引用调用者不能通过该引用修改元素。**选择原则**不确定下标是否合法时使用at()已经通过循环边界或其他逻辑保证合法时使用operator[]。三、vector的空间管理1.reserve()和resize()有什么区别接口是否创建或销毁元素是否可能重新分配内存主要用途reserve(n)否预留空间不足时会提前分配空间减少后续扩容resize(n)是增大元素数量且空间不足时会直接改变有效元素数量图中的具体capacity数值用于演示实际结果由标准库实现决定应关注reserve()不创建元素而resize()会改变元素数量。reserve(n)只预留空间不创建元素。reserve(n)保证容量至少能够容纳n个元素但不会改变size()也不会在预留区域中构造元素。std::vectorintv{1,2,3};v.reserve(100);std::coutv.size();// 3std::coutv.capacity();// 至少为 100此时仍然只有下标0、1、2可以访问。v[50]不会因为已经reserve(100)就变得合法。当n capacity()时reserve(n)不做任何处理也不能用于缩容。当n capacity()时需要重新分配内存所有指向原元素的迭代器、指针和引用都会失效。能提前估计元素数量时先调用reserve()可以减少扩容和批量搬迁。resize(n)改变有效元素数量。resize(n)直接改变size()n size()在尾部创建新元素若容量不足还会触发扩容。n size()销毁尾部多出的元素但通常不会缩小capacity()。resize(n, value)增大时使用value初始化新增元素。std::vectorintv{1,2,3};v.resize(5);// v 为 {1, 2, 3, 0, 0}v.resize(2);// v 为 {1, 2}capacity 通常不变v.resize(4,9);// v 为 {1, 2, 9, 9}对于类类型增大size()会构造新对象缩小size()会析构被移除的对象。因此resize()不只是内存预留操作。核心区别reserve()改变可容纳空间不改变元素数量resize()改变元素数量并负责构造或销毁元素。2. vector扩容机制当插入新元素后所需大小超过capacity()时vector通常会申请一块更大的连续内存。将旧元素移动或复制到新内存。在新内存中构造待插入元素。销毁旧元素并释放旧内存。C 标准没有规定固定扩容倍数。约 1.5 倍和约 2 倍都是常见的几何增长策略具体由标准库实现决定。增长策略优点代价约 1.5 倍空闲容量较少内存利用率更高扩容可能更频繁约 2 倍扩容次数通常更少可能保留更多暂时不用的空间程序不能通过标准接口指定增长倍数也不应依赖某个固定倍数。几何增长以额外容量换取更少的重新分配使尾部插入保持均摊 O(1)。3. 插入元素emplace_back()和push_back()怎么选对象较大时选择接口的关键不是对象大小本身而是对象是否已经构造完成只有构造参数时使用emplace_back(args...)直接在vector尾部构造对象。已经有一个对象时使用push_back(obj)复制或使用push_back(std::move(obj))移动。已知大致元素数量时先调用reserve()可以减少扩容时批量移动或复制已有元素的次数。接口作用复杂度适用场景push_back(value)在末尾复制或移动一个已有对象均摊 O(1)扩容时 O(n)已经有一个待插入对象emplace_back(args...)在末尾用参数直接构造元素均摊 O(1)扩容时 O(n)希望直接调用元素构造函数insert(pos, value)在指定迭代器位置前插入元素通常 O(n)需要在中间或指定位置插入emplace(pos, args...)在指定位置用参数直接构造元素通常 O(n)在指定位置直接构造元素push_back()接收一个已经存在的对象传入左值时通常复制传入右值时通常移动。emplace_back()接收构造参数并在vector尾部直接构造新元素因此可能省去临时对象的一次复制或移动。std::vectorBigObjectobjects;objects.reserve(100);// 只有构造参数直接在 vector 尾部构造。objects.emplace_back(arg1,arg2);// 对象已经存在移动进 vector避免复制大对象。BigObjectobj(arg1,arg2);objects.push_back(std::move(obj));调用std::move(obj)后obj仍然是有效对象但其具体值处于合法但未指定状态在重新赋值或销毁前不应依赖它原来的内容。不过emplace_back()并不保证一定比push_back()更快。如果已经有一个同类型对象直接push_back()通常更清楚当插入触发扩容时两者都需要重新分配内存并移动或复制原有元素。在中间使用insert()或emplace()时插入位置之后的元素通常需要整体后移所以复杂度为 O(n)。如果发生扩容所有迭代器、指针和引用都会失效即使没有扩容插入位置及其之后的迭代器、指针和引用通常也会失效。**面试结论**大对象尚未构造时使用emplace_back()对象已经存在且不再使用原值时使用push_back(std::move(obj))提前reserve()往往比纠结两种接口带来的收益更明显。4. 怎样释放vector的多余容量删除元素和释放底层容量是两件不同的事操作元素数量预留空间是否保留元素clear()清零通常保留否resize(0)清零通常保留否shrink_to_fit()不变请求缩小是std::vectorT().swap(v)清零通常释放否std::vectorT(v).swap(v)不变通常压缩是但需要复制元素clear()和resize(0)两者都会销毁全部元素但通常保留已分配的内存方便之后再次插入。因此它们不是释放容量的可靠方法。shrink_to_fit()shrink_to_fit()请求容器释放未使用容量同时保留现有元素v.clear();v.shrink_to_fit();但它只是非强制请求标准库可以选择不缩容。如果实际发生重新分配原有迭代器、指针和引用都会失效。使用swap释放空间如果元素也不再需要可以让空临时对象接管并释放原存储std::vectorBigObject().swap(objects);交换后objects为空原来的内存由临时对象在语句结束时释放。这种写法也会销毁所有元素并使原有迭代器、指针和引用失效。如果要保留元素可以使用复制并交换的传统缩容写法std::vectorBigObject(objects).swap(objects);它会创建一个只包含现有元素的新vector再释放旧存储但需要复制全部元素具体容量仍由实现决定。现代 C 中通常先使用语义更清楚的shrink_to_fit()只有确实需要控制内存并且能够接受复制或清空成本时才考虑swap技巧。**释放原则**还会继续复用容器时保留容量通常更高效内存压力明显且元素已不再需要时可用空临时对象swap需要保留元素时优先尝试shrink_to_fit()。四、扩容与迭代器失效容器插入时删除时原因vector扩容全部失效未扩容插入点及其后失效删除点及其后失效连续存储需要搬移元素deque首尾迭代器失效中间全部失效中间全部失效首尾主要影响被删位置分段连续受操作位置影响list原有位置不失效仅被删节点失效独立节点不移动其他元素表中的“位置”包括迭代器、指针和引用。deque首尾插入后迭代器失效但已有元素的指针和引用仍有效尾部删除还会使原来的end()失效。这张表先给出结论下面再分别解释为什么会出现这些差异。1. 为什么vector扩容后全部失效vector必须连续存储元素。容量不足时它会申请一块更大的连续内存将已有元素移动或复制过去再释放旧内存。原来的迭代器、指针和引用仍然保存旧地址因此扩容后会全部失效旧的end()也不能继续使用。autoitvalues.begin();values.push_back(42);// 如果触发扩容it 失效如果后续需要继续访问应在扩容操作之后重新获取迭代器能够提前估计数量时可以先reserve()减少扩容次数。2.vector未扩容时插入和删除会影响哪些位置即使没有重新分配内存插入和删除也可能移动元素插入插入位置之前的迭代器、指针和引用仍有效插入位置及其之后的全部失效。删除被删除位置及其之后的全部失效因为后面的元素会向前移动。尾部插入且未扩容已有元素的位置不变但旧的end()失效。遍历时删除元素应使用erase()返回的下一个有效迭代器for(autoitvalues.begin();it!values.end();){if(shouldRemove(*it)){itvalues.erase(it);}else{it;}}3. 为什么deque的首尾操作和中间操作失效规则不同deque使用多个缓冲块保存元素。首尾插入通常只需在两端增加元素或缓冲块不必移动已有元素中间插入或删除则可能移动两侧的大量元素。首尾插入所有迭代器会失效但指向已有元素的指针和引用仍然有效。中间插入所有迭代器、指针和引用都会失效。头部删除通常只有指向被删除元素的位置失效。尾部删除指向被删除元素的位置失效旧的end()也可能失效。中间删除所有迭代器、指针和引用都会失效。deque的失效规则比vector和list更复杂。修改结构后如果仍需遍历重新获取迭代器通常更稳妥。4. 为什么list通常只让被删除节点的迭代器失效list的每个元素都位于独立节点中插入和删除只需要修改相邻节点之间的链接不会搬迁其他节点。插入新节点原有迭代器、指针和引用仍然有效。删除节点只有指向被删除节点的迭代器、指针和引用失效。splice()转移节点节点本身不会被复制或移动指向这些节点的迭代器通常仍有效但节点已经属于目标链表。clear()或销毁容器指向所有元素的位置全部失效。这也是list适合需要稳定节点地址场景的原因但不能忽略它额外的指针开销和较差的缓存局部性。五、vector是线程安全的吗vector不会自动加锁。多个线程只读同一个vector通常没有问题但只要存在并发写入就可能产生数据竞争。push_back()、resize()、clear()等操作还可能改变容器结构一旦触发扩容旧内存会被释放其他线程持有的迭代器、指针和引用也可能失效。**结论**共享的vector只有只读访问时通常安全存在写操作时应使用mutex等同步机制统一保护相关读写。六、什么时候选哪一个**默认选vector**连续内存、随机访问快、缓存友好而且额外内存开销较小。**频繁操作两端选deque**头尾插入和删除效率高同时保留随机访问能力但内存不整体连续。**需要稳定节点或拼接选list**插入、删除不会移动其他节点splice()可以直接转移节点但不支持随机访问。中间插入多不一定选listlist找位置需要 O(n)每个节点还存在分配和指针开销元素较小、数据量不大时vector搬移元素反而可能更快。七、总结**vector是默认选择。**底层是连续内存支持 O(1) 随机访问缓存友好尾部插入均摊 O(1)代价是扩容需要搬迁元素并使原有迭代器、指针和引用失效。**deque适合频繁操作两端。**底层是分段连续内存支持 O(1) 随机访问以及高效的头尾插入和删除但不保证整体内存连续失效规则也更复杂。**list适合稳定节点和链表拼接。**底层是双向链表已知位置的插入、删除为 O(1)通常不会影响其他节点代价是不支持随机访问、节点开销大且缓存局部性较差。**选择时不能只看单次操作复杂度。**一般先选vector需要频繁操作两端时选deque只有确实需要稳定节点地址、频繁splice()或已经持有插入删除位置时再考虑list。**一句话记忆**连续存储选vector两端操作选deque稳定节点与拼接选list。八、高频面试题精选vector的扩容机制是什么扩容倍数固定吗reserve()和resize()有什么区别vector扩容后哪些对象会失效vector和list应该怎样选择deque为什么可以在两端高效插入如果对象比较大怎样把它放入vectoremplace_back()和push_back()有什么区别vector::at()和operator[]有什么区别越界时分别会发生什么vector是线程安全的吗多个线程能否同时读取或写入CodeACM 是面向算法竞赛和编程面试的 ACM 在线刷题网站支持在线刷题、代码提交、在线判题与专题练习。网站地址https://codeacm.cn#C面试 #STL容器 #vector #deque和list #CodeACM