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

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

std::vector是 C++ 中最常用的顺序容器之一。它用起来像长度可变的数组：支持下标访问，可以在尾部不断添加元素，也能与标准算法直接配合。

真正容易出问题的地方并不在push_back怎么写，而在它背后的内存变化。为什么size()和capacity()不是一回事？为什么一次看似普通的插入会让旧迭代器失效？为什么搬运int数组时看似好用的memcpy，换成string就可能破坏对象？把这些问题串起来，vector的行为就不再零散。

一、vector 是什么

vector是一个元素连续存储、容量可动态增长的顺序容器。假设有如下对象：

std::vector<int>numbers{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 的性能特点

这里的“均摊”很重要。某一次push_back可能触发扩容，代价是O(n)；但扩容不会在每次插入时发生，把多次操作放在一起看，平均成本仍接近常数级。

二、构造、访问与遍历

使用vector需要包含头文件：

#include<vector>

2.1 常见构造方式

#include<iostream>#include<vector>intmain(){std::vector<int>empty;// 空容器std::vector<int>fiveZeros(5);// 5 个 0std::vector<int>fourSevens(4,7);// 4 个 7std::vector<int>source{1,2,3,4};std::vector<int>copy(source);// 拷贝构造std::vector<int>part(source.begin()+1,source.end());for(intvalue:part)std::cout<<value<<' ';std::cout<<'\n';}

输出：

2 3 4

范围构造采用左闭右开区间[first, last)。这与标准库中迭代器区间的通用约定一致，last指向的是区间末尾的下一个位置。

注意：std::vector<int> values(5, 2)表示 5 个值为 2 的元素；std::vector<int> values{5, 2}则表示两个元素 5 和 2。圆括号和花括号不能随意替换。

2.2 三种常用遍历方式

std::vector<int>values{10,20,30};// 下标遍历：需要位置时很方便for(std::size_t i=0;i<values.size();++i)std::cout<<values[i]<<' ';// 迭代器遍历：便于理解并配合标准算法for(std::vector<int>::iterator it=values.begin();it!=values.end();++it)std::cout<<*it<<' ';// 范围 for：只关心元素时最简洁for(intvalue:values)std::cout<<value<<' ';

begin()指向第一个元素，end()指向最后一个元素之后的位置。空vector中begin() == end()，而且任何时候都不能解引用end()。

反向遍历可以使用rbegin()和rend()：

for(autoit=values.rbegin();it!=values.rend();++it)std::cout<<*it<<' ';

输出为30 20 10。

2.3operator[]与at()

std::cout<<values[1]<<'\n';std::cout<<values.at(1)<<'\n';

两者都能访问指定位置，但边界处理不同：

• operator[]不检查下标，越界访问属于未定义行为。
• at()会检查下标，越界时抛出std::out_of_range。

能由程序逻辑保证下标合法时，常用operator[]；下标来自外部输入或边界不容易确认时，at()更容易暴露错误。

三、size、capacity、reserve 与 resize

这四个接口经常放在一起讨论，但它们解决的不是同一件事。

3.1 reserve 只准备空间

std::vector<int>values;values.reserve(100);std::cout<<values.size()<<' '<<values.capacity()<<'\n';

典型输出类似：

0 100

reserve(100)不会创建 100 个可访问元素，所以此时写values[0] = 1仍然越界。它只是提前准备容量，后续 100 次左右的尾部插入通常不需要反复申请空间。

当元素数量大致已知时，提前reserve很实用：

std::vector<int>values;values.reserve(100000);for(inti=0;i<100000;++i)values.push_back(i);

3.2 resize 会改变有效元素数

std::vector<int>values{1,2,3};values.resize(5,9);// 变为 1 2 3 9 9values.resize(2);// 变为 1 2

扩展size时，新位置会被构造；缩小size时，多余元素会被销毁。缩小通常不会同步降低capacity。

3.3 扩容倍率不是固定规则

下面的程序可以观察当前标准库实现的容量变化：

#include<iostream>#include<vector>intmain(){std::vector<int>values;std::size_t oldCapacity=values.capacity();for(inti=0;i<100;++i){values.push_back(i);if(values.capacity()!=oldCapacity){oldCapacity=values.capacity();std::cout<<oldCapacity<<' ';}}std::cout<<'\n';}

某些实现会出现接近 1.5 倍的增长，另一些实现可能按 2 倍增长。C++ 标准没有规定固定倍率，程序不能依赖某一组容量序列。可以依赖的是：capacity()不小于size()，并且扩容后可以容纳所请求的元素。

四、增删查改的完整示例

vector自己提供插入、删除和访问接口；按值查找通常交给<algorithm>中的std::find。

#include<algorithm>#include<iostream>#include<vector>intmain(){std::vector<int>values{10,20,30};values.push_back(40);// 10 20 30 40values.insert(values.begin()+1,15);// 10 15 20 30 40autoposition=std::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::cout<<value<<' ';std::cout<<'\n';}

编译并运行：

g++ vector_basic.cpp-std=c++11-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::vector<int>values{1,2,3};autoit=values.begin();values.reserve(100);// 若发生重新分配，it 失效it=values.begin();// 重新获取后才能继续使用

可能引发重新分配的操作包括push_back、insert、resize、reserve和assign等。是否真的重新分配，要看操作后的容量需求和接口语义。

如果push_back时容量还够，已有元素地址通常不变；一旦触发扩容，原空间中的引用、指针和迭代器全部失效。

5.2 erase 会让删除位置及其后的迭代器失效

删除中间元素后，后续元素会向前移动。因此，删除位置以及它后面的迭代器都不能继续使用。erase的返回值正是处理这个问题的入口：它返回删除位置之后的新有效位置。

下面要删除所有偶数，错误写法是：

// 错误：erase 后 it 已失效，后面的 ++it 继续使用了无效迭代器for(autoit=values.begin();it!=values.end();++it){if(*it%2==0)values.erase(it);}

正确写法：

for(autoit=values.begin();it!=values.end();){if(*it%2==0)it=values.erase(it);else++it;}

如果删除的是末尾元素，erase会返回新的end()，循环条件仍能正确结束。

无效迭代器被继续使用属于未定义行为。程序“这次没崩溃”不能证明代码正确；它也可能输出旧数据、随机数据，或在换一个编译选项后直接终止。

5.3 常见操作的失效规则

处理迭代器失效有两条实用原则：优先接住修改接口返回的新迭代器；无法接住时，在修改后重新调用begin()、end()或按下标重新定位。

六、vector 的两个典型应用

6.1 只出现一次的数字

若数组中除一个数字外，其余数字都出现两次，可以利用异或的性质：x ^ x == 0，0 ^ x == x。

intsingleNumber(conststd::vector<int>&numbers){intresult=0;for(intvalue:numbers)result^=value;returnresult;}

时间复杂度为O(n)，额外空间复杂度为O(1)。这里用const std::vector<int>&接收参数，既避免复制，又明确函数不会修改容器。

6.2 用二维 vector 生成杨辉三角

std::vector<std::vector<int>>是外层元素类型为std::vector<int>的容器。它适合表示每行长度不同的二维结构。

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

每一行的元素连续存储，但不保证不同行的元素空间彼此连续。

#include<iostream>#include<vector>std::vector<std::vector<int>>generateTriangle(introws){std::vector<std::vector<int>>triangle(rows);for(introw=0;row<rows;++row){triangle[row].resize(row+1,1);for(intcolumn=1;column<row;++column){triangle[row][column]=triangle[row-1][column-1]+triangle[row-1][column];}}returntriangle;}intmain(){constautotriangle=generateTriangle(5);for(constauto&row:triangle){for(intvalue:row)std::cout<<value<<' ';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。

#include<algorithm>#include<cstddef>#include<memory>#include<utility>template<classT>classMiniVector{public:usingiterator=T*;usingconst_iterator=constT*;MiniVector():begin_(nullptr),end_(nullptr),cap_(nullptr){}MiniVector(constMiniVector&other):MiniVector(){reserve(other.size());for(constT&value:other)push_back(value);}MiniVector&operator=(MiniVector other){swap(other);return*this;}~MiniVector(){clear();if(begin_!=nullptr)allocator_.deallocate(begin_,capacity());}voidpush_back(constT&value){if(end_==cap_)reserve(capacity()==0?4:capacity()*2);Traits::construct(allocator_,end_,value);++end_;}voidreserve(std::size_t newCapacity){if(newCapacity<=capacity())return;T*newBegin=allocator_.allocate(newCapacity);T*newEnd=newBegin;try{for(T*current=begin_;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 oldCapacity=capacity();clear();if(begin_!=nullptr)allocator_.deallocate(begin_,oldCapacity);begin_=newBegin;end_=newEnd;cap_=newBegin+newCapacity;}voidclear(){while(end_!=begin_){--end_;Traits::destroy(allocator_,end_);}}std::size_tsize()const{returnbegin_==nullptr?0:static_cast<std::size_t>(end_-begin_);}std::size_tcapacity()const{returnbegin_==nullptr?0:static_cast<std::size_t>(cap_-begin_);}T&operator[](std::size_t index){returnbegin_[index];}constT&operator[](std::size_t index)const{returnbegin_[index];}iteratorbegin(){returnbegin_;}iteratorend(){returnend_;}const_iteratorbegin()const{returnbegin_;}const_iteratorend()const{returnend_;}voidswap(MiniVector&other){std::swap(begin_,other.begin_);std::swap(end_,other.end_);std::swap(cap_,other.cap_);}private:usingAllocator=std::allocator<T>;usingTraits=std::allocator_traits<Allocator>;Allocator allocator_;T*begin_;T*end_;T*cap_;};

这段代码的核心在reserve：

1. 申请一块更大的原始空间。
2. 在新空间逐个构造元素，优先移动，必要时复制。
3. 销毁旧元素并释放旧空间。
4. 更新三个位置，使对象接管新空间。

扩容后旧空间已经释放，所以此前获取的迭代器全部失效。这个现象不是某个接口的偶然副作用，而是连续动态数组更换存储区的直接结果。

为什么不能随意用 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::vector<std::vector<int>>是常见的动态二维结构。外层容器连续保存内层vector对象，各行的数据空间由各自的内层对象独立管理。

6. 什么时候不适合使用 vector

如果业务经常在序列中间插入、删除大量元素，移动成本可能较高。选择容器时要看主要访问模式，不能只看接口是否齐全。对于大多数需要随机访问和尾部增长的场景，vector通常仍是很合适的默认选择。

九、总结

理解vector可以抓住一条主线：它是连续存储的动态数组。连续存储带来了O(1)随机访问和良好的局部性，也意味着扩容时需要搬运全部元素，中间插入和删除时需要移动后续元素。

日常使用中，分清size与capacity，知道reserve不会创建元素，并在修改容器后谨慎处理迭代器，已经能避开大部分问题。再往下看，三个位置的存储模型、逐对象构造和资源转移规则，则解释了扩容、迭代器失效以及不能滥用memcpy的根本原因。