C++ vector 原理与实践：从常用接口到扩容和迭代器失效

C vector 原理与实践从常用接口到扩容和迭代器失效std::vector是 C 中最常用的顺序容器之一。它用起来像长度可变的数组支持下标访问可以在尾部不断添加元素也能与标准算法直接配合。真正容易出问题的地方并不在push_back怎么写而在它背后的内存变化。为什么size()和capacity()不是一回事为什么一次看似普通的插入会让旧迭代器失效为什么搬运int数组时看似好用的memcpy换成string就可能破坏对象把这些问题串起来vector的行为就不再零散。一、vector 是什么vector是一个元素连续存储、容量可动态增长的顺序容器。假设有如下对象std::vectorintnumbers{10,20,30,40};四个int在内存中依次排列因此numbers[i]可以通过“起始地址 偏移量”快速定位随机访问的时间复杂度是O(1)。可以把一个典型的vector对象理解为维护了三个位置start finish end_of_storage | | | v v v ---------------------------------------- | 10 | 20 | 30 | 40 | 备用容量 | ---------------------------------------- ------ size ------ ---------------- capacity ----------------start指向第一个元素。finish指向最后一个有效元素的下一个位置。end_of_storage指向当前存储空间的末尾。标准并没有要求某个实现必须真的使用这三个同名指针但这种模型非常适合理解size()、capacity()和扩容过程。vector 的性能特点操作常见时间复杂度原因下标访问O(1)元素连续存储可直接计算地址尾部插入均摊O(1)容量足够时直接构造偶尔需要整体扩容尾部删除O(1)销毁末尾元素即可中间插入、删除O(n)插入点之后的元素需要移动按值查找O(n)通常需要从头到尾比较这里的“均摊”很重要。某一次push_back可能触发扩容代价是O(n)但扩容不会在每次插入时发生把多次操作放在一起看平均成本仍接近常数级。二、构造、访问与遍历使用vector需要包含头文件#includevector2.1 常见构造方式#includeiostream#includevectorintmain(){std::vectorintempty;// 空容器std::vectorintfiveZeros(5);// 5 个 0std::vectorintfourSevens(4,7);// 4 个 7std::vectorintsource{1,2,3,4};std::vectorintcopy(source);// 拷贝构造std::vectorintpart(source.begin()1,source.end());for(intvalue:part)std::coutvalue ;std::cout\n;}输出2 3 4范围构造采用左闭右开区间[first, last)。这与标准库中迭代器区间的通用约定一致last指向的是区间末尾的下一个位置。注意std::vectorint values(5, 2)表示 5 个值为 2 的元素std::vectorint values{5, 2}则表示两个元素 5 和 2。圆括号和花括号不能随意替换。2.2 三种常用遍历方式std::vectorintvalues{10,20,30};// 下标遍历需要位置时很方便for(std::size_t i0;ivalues.size();i)std::coutvalues[i] ;// 迭代器遍历便于理解并配合标准算法for(std::vectorint::iterator itvalues.begin();it!values.end();it)std::cout*it ;// 范围 for只关心元素时最简洁for(intvalue:values)std::coutvalue ;begin()指向第一个元素end()指向最后一个元素之后的位置。空vector中begin() end()而且任何时候都不能解引用end()。反向遍历可以使用rbegin()和rend()for(autoitvalues.rbegin();it!values.rend();it)std::cout*it ;输出为30 20 10。2.3operator[]与at()std::coutvalues[1]\n;std::coutvalues.at(1)\n;两者都能访问指定位置但边界处理不同operator[]不检查下标越界访问属于未定义行为。at()会检查下标越界时抛出std::out_of_range。能由程序逻辑保证下标合法时常用operator[]下标来自外部输入或边界不容易确认时at()更容易暴露错误。三、size、capacity、reserve 与 resize这四个接口经常放在一起讨论但它们解决的不是同一件事。接口作用是否改变元素个数是否可能重新分配size()返回当前有效元素数否否capacity()返回不重新分配时最多可容纳的元素数否否reserve(n)请求容量至少达到n否是resize(n, value)把有效元素数改为n是是3.1 reserve 只准备空间std::vectorintvalues;values.reserve(100);std::coutvalues.size() values.capacity()\n;典型输出类似0 100reserve(100)不会创建 100 个可访问元素所以此时写values[0] 1仍然越界。它只是提前准备容量后续 100 次左右的尾部插入通常不需要反复申请空间。当元素数量大致已知时提前reserve很实用std::vectorintvalues;values.reserve(100000);for(inti0;i100000;i)values.push_back(i);3.2 resize 会改变有效元素数std::vectorintvalues{1,2,3};values.resize(5,9);// 变为 1 2 3 9 9values.resize(2);// 变为 1 2扩展size时新位置会被构造缩小size时多余元素会被销毁。缩小通常不会同步降低capacity。3.3 扩容倍率不是固定规则下面的程序可以观察当前标准库实现的容量变化#includeiostream#includevectorintmain(){std::vectorintvalues;std::size_t oldCapacityvalues.capacity();for(inti0;i100;i){values.push_back(i);if(values.capacity()!oldCapacity){oldCapacityvalues.capacity();std::coutoldCapacity ;}}std::cout\n;}某些实现会出现接近 1.5 倍的增长另一些实现可能按 2 倍增长。C 标准没有规定固定倍率程序不能依赖某一组容量序列。可以依赖的是capacity()不小于size()并且扩容后可以容纳所请求的元素。四、增删查改的完整示例vector自己提供插入、删除和访问接口按值查找通常交给algorithm中的std::find。#includealgorithm#includeiostream#includevectorintmain(){std::vectorintvalues{10,20,30};values.push_back(40);// 10 20 30 40values.insert(values.begin()1,15);// 10 15 20 30 40autopositionstd::find(values.begin(),values.end(),30);if(position!values.end())values.erase(position);// 10 15 20 40values.pop_back();// 10 15 20values[0]8;// 8 15 20for(intvalue:values)std::coutvalue ;std::cout\n;}编译并运行g vector_basic.cpp-stdc11-Wall-Wextra-pedantic-ovector_basic ./vector_basic预期输出8 15 20这段代码有几个细节insert(position, value)在position之前插入。std::find不是vector的成员函数必须包含algorithm。查找失败会返回end()传给erase前必须判断。空容器不能调用pop_back()否则属于未定义行为。五、迭代器失效最需要警惕的行为迭代器记录了元素的位置。对vector做修改后元素可能被搬到新空间也可能在原空间内前后移动旧位置便不再可靠。不同标准库可以用裸指针或包装类型实现迭代器。代码不应依赖具体表示只需要遵守失效规则。5.1 重新分配会让全部迭代器失效std::vectorintvalues{1,2,3};autoitvalues.begin();values.reserve(100);// 若发生重新分配it 失效itvalues.begin();// 重新获取后才能继续使用可能引发重新分配的操作包括push_back、insert、resize、reserve和assign等。是否真的重新分配要看操作后的容量需求和接口语义。如果push_back时容量还够已有元素地址通常不变一旦触发扩容原空间中的引用、指针和迭代器全部失效。5.2 erase 会让删除位置及其后的迭代器失效删除中间元素后后续元素会向前移动。因此删除位置以及它后面的迭代器都不能继续使用。erase的返回值正是处理这个问题的入口它返回删除位置之后的新有效位置。下面要删除所有偶数错误写法是// 错误erase 后 it 已失效后面的 it 继续使用了无效迭代器for(autoitvalues.begin();it!values.end();it){if(*it%20)values.erase(it);}正确写法for(autoitvalues.begin();it!values.end();){if(*it%20)itvalues.erase(it);elseit;}如果删除的是末尾元素erase会返回新的end()循环条件仍能正确结束。无效迭代器被继续使用属于未定义行为。程序“这次没崩溃”不能证明代码正确它也可能输出旧数据、随机数据或在换一个编译选项后直接终止。5.3 常见操作的失效规则操作发生重新分配时未重新分配时push_back/emplace_back全部失效原end()失效其余通常保持有效insert/emplace全部失效插入位置及其后的迭代器失效erase通常不重新分配删除位置及其后的迭代器失效reserve容量增长时全部失效容量未增长时保持有效resize重新分配时全部失效缩小时被删除元素及其后的迭代器失效处理迭代器失效有两条实用原则优先接住修改接口返回的新迭代器无法接住时在修改后重新调用begin()、end()或按下标重新定位。六、vector 的两个典型应用6.1 只出现一次的数字若数组中除一个数字外其余数字都出现两次可以利用异或的性质x ^ x 00 ^ x x。intsingleNumber(conststd::vectorintnumbers){intresult0;for(intvalue:numbers)result^value;returnresult;}时间复杂度为O(n)额外空间复杂度为O(1)。这里用const std::vectorint接收参数既避免复制又明确函数不会修改容器。6.2 用二维 vector 生成杨辉三角std::vectorstd::vectorint是外层元素类型为std::vectorint的容器。它适合表示每行长度不同的二维结构。triangle -- triangle[0] - 1 -- triangle[1] - 1 1 -- triangle[2] - 1 2 1 -- triangle[3] - 1 3 3 1 -- triangle[4] - 1 4 6 4 1每一行的元素连续存储但不保证不同行的元素空间彼此连续。#includeiostream#includevectorstd::vectorstd::vectorintgenerateTriangle(introws){std::vectorstd::vectorinttriangle(rows);for(introw0;rowrows;row){triangle[row].resize(row1,1);for(intcolumn1;columnrow;column){triangle[row][column]triangle[row-1][column-1]triangle[row-1][column];}}returntriangle;}intmain(){constautotrianglegenerateTriangle(5);for(constautorow:triangle){for(intvalue:row)std::coutvalue ;std::cout\n;}}预期输出1 1 1 1 2 1 1 3 3 1 1 4 6 4 1外层vector负责管理“行”内层vector负责管理每一行的数据。triangle[row].resize(row 1, 1)先把当前行调整到正确长度并把元素初始化为 1之后只计算中间位置。七、从简化实现理解 vector下面是为了帮助理解而写的简化版本只实现构造、析构、拷贝、尾插、扩容和下标访问。它没有覆盖分配器传播、自定义分配器、完整异常规范等标准容器细节不能替代std::vector。#includealgorithm#includecstddef#includememory#includeutilitytemplateclassTclassMiniVector{public:usingiteratorT*;usingconst_iteratorconstT*;MiniVector():begin_(nullptr),end_(nullptr),cap_(nullptr){}MiniVector(constMiniVectorother):MiniVector(){reserve(other.size());for(constTvalue:other)push_back(value);}MiniVectoroperator(MiniVector other){swap(other);return*this;}~MiniVector(){clear();if(begin_!nullptr)allocator_.deallocate(begin_,capacity());}voidpush_back(constTvalue){if(end_cap_)reserve(capacity()0?4:capacity()*2);Traits::construct(allocator_,end_,value);end_;}voidreserve(std::size_t newCapacity){if(newCapacitycapacity())return;T*newBeginallocator_.allocate(newCapacity);T*newEndnewBegin;try{for(T*currentbegin_;current!end_;current,newEnd){Traits::construct(allocator_,newEnd,std::move_if_noexcept(*current));}}catch(...){while(newEnd!newBegin){--newEnd;Traits::destroy(allocator_,newEnd);}allocator_.deallocate(newBegin,newCapacity);throw;}conststd::size_t oldCapacitycapacity();clear();if(begin_!nullptr)allocator_.deallocate(begin_,oldCapacity);begin_newBegin;end_newEnd;cap_newBeginnewCapacity;}voidclear(){while(end_!begin_){--end_;Traits::destroy(allocator_,end_);}}std::size_tsize()const{returnbegin_nullptr?0:static_caststd::size_t(end_-begin_);}std::size_tcapacity()const{returnbegin_nullptr?0:static_caststd::size_t(cap_-begin_);}Toperator[](std::size_t index){returnbegin_[index];}constToperator[](std::size_t index)const{returnbegin_[index];}iteratorbegin(){returnbegin_;}iteratorend(){returnend_;}const_iteratorbegin()const{returnbegin_;}const_iteratorend()const{returnend_;}voidswap(MiniVectorother){std::swap(begin_,other.begin_);std::swap(end_,other.end_);std::swap(cap_,other.cap_);}private:usingAllocatorstd::allocatorT;usingTraitsstd::allocator_traitsAllocator;Allocator allocator_;T*begin_;T*end_;T*cap_;};这段代码的核心在reserve申请一块更大的原始空间。在新空间逐个构造元素优先移动必要时复制。销毁旧元素并释放旧空间。更新三个位置使对象接管新空间。扩容后旧空间已经释放所以此前获取的迭代器全部失效。这个现象不是某个接口的偶然副作用而是连续动态数组更换存储区的直接结果。为什么不能随意用 memcpy 搬运元素下面这种写法看起来很快却不能作为通用的元素搬运方式// 错误示意不能对任意 T 这样搬运std::memcpy(newBuffer,oldBuffer,size()*sizeof(T));memcpy只复制对象表示中的字节不会调用复制构造或移动构造。对于std::string这类管理资源的对象字节复制可能让新旧对象保存同一个内部地址随后出现重复释放、悬空指针等问题。更准确地说只有在类型满足相应的平凡可复制要求并且对象生命周期规则也得到满足时字节复制才适合作为优化手段。通用容器实现应通过构造操作逐个搬运元素让类型自己决定如何转移资源。八、常见问题与易错点1. reserve 之后为什么 size 还是 0因为reserve只调整容量不创建有效元素。需要新增元素时使用push_back、emplace_back或者用resize改变元素个数。2. capacity 能不能当作有效下标范围不能。合法下标范围只由size决定即[0, size())。容量中尚未构造元素的部分不能通过operator[]访问。3. clear 会释放全部内存吗clear()会销毁所有元素并把size()变为 0但通常保留容量以便后续复用。标准也不保证shrink_to_fit()一定释放多余容量它只是一个非强制请求。4. 为什么不能边遍历边直接 erase可以边遍历边删除但必须使用erase返回的新迭代器。继续使用删除前的迭代器会触发未定义行为。5. vector 能否保存 vector可以。std::vectorstd::vectorint是常见的动态二维结构。外层容器连续保存内层vector对象各行的数据空间由各自的内层对象独立管理。6. 什么时候不适合使用 vector如果业务经常在序列中间插入、删除大量元素移动成本可能较高。选择容器时要看主要访问模式不能只看接口是否齐全。对于大多数需要随机访问和尾部增长的场景vector通常仍是很合适的默认选择。九、总结理解vector可以抓住一条主线它是连续存储的动态数组。连续存储带来了O(1)随机访问和良好的局部性也意味着扩容时需要搬运全部元素中间插入和删除时需要移动后续元素。日常使用中分清size与capacity知道reserve不会创建元素并在修改容器后谨慎处理迭代器已经能避开大部分问题。再往下看三个位置的存储模型、逐对象构造和资源转移规则则解释了扩容、迭代器失效以及不能滥用memcpy的根本原因。