【C++】vector的模拟实现

vector模拟实现

最坚实的数据结构，恰恰长着最简单的模样——用指针织一片连续的内存，便装下了万物的来去

1. 什么是vector

想必大家都学过顺序表这个数据结构。顺序表通过开辟一块连续的内存空间来存储数据，在C语言中，如果要自己实现一个顺序表，需要先定义一个动态数组，然后还要实现增删改查相关的操作函数。

但是C语言实现顺序表有一个很大的局限：如果程序涉及到多种数据类型的顺序表，就得为每种数据类型写一份重复的代码，导致代码冗余且难以维护。C++的vector正是为了解决这个问题而生——它是一个模板类，内部维护的是一个动态数组，增删改查等操作都封装好了，并且会自动扩容。编译器会根据创建的对象类型，实例化出对应数据类型的vector类，我们只需要放心使用即可。

2. vector的核心设计

2.1 成员变量的设计

不同于string用_str、_size、_capacity三个独立变量，vector在成员变量的设计上采用了三个迭代器（指针）来维护数组：

template<classT>classvector{private:iterator _start=nullptr;// 指向数组起始位置iterator _finish=nullptr;// 指向有效元素末尾的下一个位置iterator _endofstorage=nullptr;// 指向已分配空间的末尾};

这种设计的好处很明显：

• _finish - _start直接得到元素个数（size）
• _endofstorage - _start直接得到当前容量（capacity）

用指针的差值来表示大小和容量，省去了单独维护size和capacity的烦恼，这是仿照SGI版本STL源码的设计思路。

2.2 迭代器的实现

在vector中，迭代器就是原始指针的别名：

typedefT*iterator;typedefconstT*const_iterator;

因为vector的底层是一段连续的内存空间，指针天然的"++"就能移动到下一个元素，所以在vector中迭代器的实现就这么简洁直接。

四个迭代器函数分别返回_start和_finish，并通过const版本来支持const对象的只读访问。

2.3 基本接口：size、capacity、empty、clear、operator[]

size_tsize()const{return_finish-_start;}size_tcapacity()const{return_endofstorage-_start;}boolempty()const{return_start==_finish;}voidclear(){_finish=_start;}T&operator[](size_t n){assert(n<size());return_start[n];}constT&operator[](size_t n)const{assert(n<size());return_start[n];}

• size()和capacity()利用指针差值直接计算，时间复杂度O(1)。
• empty()判断起始和结束指针是否重合。
• clear()只需将_finish指向_start，逻辑上清空所有元素（内存并未释放）。
• operator[]提供下标访问，内部带断言检查越界。

3. 构造函数与析构函数

3.1 迭代器区间构造与SFINAE技巧

向量不仅可以通过无参构造和初始化列表构造，还可以通过迭代器区间构造。这里包含了一个很有意思的细节：

template<classInputiterator,class=typenamestd::enable_if<!std::is_integral<Inputiterator>::value>::type>vector(Inputiterator first,Inputiterator last){while(first!=last){push_back(*first);++first;}}

为什么要用enable_if加上is_integral呢？

这是因为vector还有两个构造函数的重载：

vector(size_t n,T val=T());// 用n个val初始化vector(intn,T val=T());// 为了兼容int类型的n

如果不加限制，当调用vector<int> v(5, 1)时，编译器会纠结：(5, 1)到底该匹配"迭代器区间构造"（把5和1当作两个迭代器），还是匹配"n个val构造"（5是元素个数，1是元素值）？

通过enable_if检查Inputiterator是否为整型，如果是整型就排除这个重载，确保编译器能够正确选择"n个val构造"。这就是C++中SFINAE（Substitution Failure Is Not An Error）原则的应用——当一个模板重载在类型推导时失败，编译器不会报错，只是把这个重载从候选集中移除，然后尝试下一个候选函数。

⚠️ 温馨提示：enable_if必须出现在函数签名中才能参与重载解析，不能放在函数体内。而且C++20提供了concepts机制，可以用更清晰的方式来写这类约束。

3.2 拷贝构造与赋值操作

拷贝构造的实现思路很简单：根据被拷贝对象的容量先开辟好足够大的空间，然后逐个元素进行赋值。需要注意的细节是reserve的参数应该传被拷贝对象的capacity()而不是size()。如果传的是size()，虽然也能运行，但下一次push_back会立即触发扩容，效率会打折扣。提前预留足够的容量可以避免多次扩容带来的性能损耗。

vector(constvector<T>&v){reserve(v.capacity());for(auto&e:v){push_back(e);}}

赋值操作则巧妙地利用了拷贝交换（copy-and-swap）惯用法：

voidswap(vector<T>tmp){std::swap(_start,tmp._start);std::swap(_finish,tmp._finish);std::swap(_endofstorage,tmp._endofstorage);}vector<T>&operator=(vector<T>v)// 传值调用自动生成了副本{swap(v);// 交换副本与当前对象的内容return*this;}

先通过传值调用生成一份副本，再通过交换成员变量完成赋值，最后副本在函数结束时自动析构——简洁且异常安全。

3.3 析构函数

~vector(){if(_start){delete[]_start;_start=_finish=_endofstorage=nullptr;}}

析构函数负责释放动态分配的内存，并将三个指针置空，防止悬空指针。

4. 容量管理与动态扩容

4.1 reserve：预留空间

reserve是vector扩容的核心函数，它保证容器能够容纳n个元素而不需要重新分配内存：

voidreserve(size_t n){if(n>capacity()){size_t old_size=size();T*tmp=newT[n];if(_start){for(size_t i=0;i<old_size;i++){tmp[i]=_start[i];}delete[]_start;}_start=tmp;_finish=_start+old_size;_endofstorage=_start+n;}}

有几个关键点值得注意：

关键点一：为什么要提前记录old_size？_finish和_start都是指针，size() = _finish - _start在扩容过程中。如果先更新_start再计算_finish，等式右边会算错。所以必须在_start被覆盖之前把size()保存下来。

关键点二：为什么不直接用memcpy拷贝？如果T是string等自定义类型，memcpy只是按字节复制浅拷贝，会导致两个对象指向同一块资源，析构时会double free。用赋值运算符逐个赋值，才能调用自定义类型的拷贝逻辑，实现深拷贝。

4.2 push_back与pop_back

有了reserve，尾插操作变得简洁：

voidpush_back(constT&val){if(_finish==_endofstorage){reserve(capacity()==0?4:2*capacity());}*_finish=val;++_finish;}

当空间满了就用reserve扩容，扩容因子是2倍（g++下是2倍扩容，VS下是1.5倍）。然后直接在_finish指向的位置放入新元素即可。

尾删的逻辑更直接：

voidpop_back(){assert(!empty());--_finish;}

只需要确保容器非空，然后让_finish指针前移一位即可——这就是顺序表删除操作的简洁之处。

5. 插入与删除

5.1 insert：在指定位置插入

insert操作的实现思路分为三步：判断是否需要扩容、将pos及之后的元素后移、在pos位置放入新元素。

iteratorinsert(iterator pos,constT&x){assert(pos>=_start&&pos<=_finish);if(_finish==_endofstorage){size_t len=pos-_start;reserve(capacity()==0?4:2*capacity());pos=_start+len;// 关键：重新定位pos}iterator end=_finish-1;while(end>=pos){*(end+1)=*end;--end;}*pos=x;++_finish;returnpos;}

这里有一个非常隐蔽的问题：如果在扩容前保存了pos，扩容后新空间来了，pos指向的还是旧空间的地址——此时旧空间已被释放，pos变成了野指针！解决方法是在扩容前记录pos相对于_start的偏移量len，扩容后让pos重新指向新空间中对应的位置。

5.2 erase：删除指定位置

erase的实现思路是：将pos位置之后的元素逐个向前覆盖一位，然后将_finish指针前移。

iteratorerase(iterator pos){assert(pos>=_start&&pos<_finish);iterator it=pos+1;while(it!=_finish){*(it-1)=*it;++it;}--_finish;returnpos;}

5.3 迭代器失效问题剖析

迭代器本质上就是指针，迭代器失效意味着这个指针指向的内存已经被释放了，如果继续使用就会产生未定义行为，程序可能会崩溃。

在vector中有以下几种情况会导致迭代器失效：

• 扩容类操作（reserve、resize、push_back、insert等）。当触发扩容时，容器会重新分配一块新内存，将旧空间的元素逐个拷贝过去，然后释放旧空间。此时任何指向旧空间的迭代器都会失效，变成野指针。
• erase删除操作。当删除pos位置的元素时，pos位置之后的元素会向前覆盖。虽然底层空间没有变化，但VS等编译器认为该位置的迭代器已经失效，尤其是删除最后一个元素时，pos会变成end位置，而end位置没有元素，因此pos失效。

5.4 resize：调整容器大小

resize函数根据n的不同取值分两种情况处理：

voidresize(size_t n,T val=T()){if(n>size()){reserve(n);while(_finish!=_start+n){*_finish=val;++_finish;}}else{_finish=_start+n;}}

• 当n大于当前size时，扩容后用val填充多出的位置。
• 当n小于当前size时，只需将_finish指针调整到_start + n位置即可，相当于截断处理。

6. 总结

从成员变量的设计（三个迭代器）、迭代器的简单实现（原生指针），到自动扩容机制（2倍扩容因子），再到插入删除时对迭代器失效的处理（记录偏移量重新定位），每一个细节都体现了C++顺序表这一核心数据结构的设计精髓。正如我们在本文开头所说的那样——最坚实的数据结构，恰恰长着最简单的模样。希望这次模拟实现的讲解，能帮助大家更深入地理解vector的底层原理，在实际开发中写出更健壮的代码。

7. vector.h完整代码

#pragmaonce#include<iostream>#include<assert.h>#include<vector>#include<type_traits>usingnamespacestd;namespaceray{template<classT>classvector{public:typedefT*iterator;typedefconstT*const_iterator;iteratorbegin(){return_start;}iteratorend(){return_finish;}const_iteratorbegin()const{return_start;}const_iteratorend()const{return_finish;}vector()=default;vector(initializer_list<T>il){reserve(il.size());for(auto&e:il)push_back(e);}vector(constvector<T>&v){reserve(v.capacity());for(auto&e:v)push_back(e);}voidswap(vector<T>tmp){std::swap(_start,tmp._start);std::swap(_finish,tmp._finish);std::swap(_endofstorage,tmp._endofstorage);}vector<T>&operator=(vector<T>v){swap(v);return*this;}template<classInputiterator,class=typenamestd::enable_if<!std::is_integral<Inputiterator>::value>::type>vector(Inputiterator first,Inputiterator last){while(first!=last)push_back(*first++);}vector(size_t n,T val=T()){resize(n,val);}vector(intn,T val=T()){resize(n,val);}~vector(){if(_start)delete[]_start;_start=_finish=_endofstorage=nullptr;}voidresize(size_t n,T val=T()){if(n>size()){reserve(n);while(_finish!=_start+n)*_finish++=val;}else_finish=_start+n;}size_tsize()const{return_finish-_start;}size_tcapacity()const{return_endofstorage-_start;}T&operator[](size_t n){assert(n<size());return_start[n];}constT&operator[](size_t n)const{assert(n<size());return_start[n];}voidreserve(size_t n){if(n>capacity()){size_t old_size=size();T*tmp=newT[n];if(_start){for(size_t i=0;i<old_size;++i)tmp[i]=_start[i];delete[]_start;}_start=tmp;_finish=_start+old_size;_endofstorage=_start+n;}}voidpush_back(constT&val){if(_finish==_endofstorage)reserve(capacity()==0?4:2*capacity());*_finish++=val;}voidclear(){_finish=_start;}boolempty()const{return_start==_finish;}voidpop_back(){assert(!empty());--_finish;}iteratorinsert(iterator pos,constT&x){assert(pos>=_start&&pos<=_finish);if(_finish==_endofstorage){size_t len=pos-_start;reserve(capacity()==0?4:2*capacity());pos=_start+len;}iterator end=_finish-1;while(end>=pos)*(end+1)=*end--;*pos=x;++_finish;returnpos;}iteratorerase(iterator pos){assert(pos>=_start&&pos<_finish);iterator it=pos+1;while(it!=_finish)*(it-1)=*it++;--_finish;returnpos;}private:iterator _start=nullptr;iterator _finish=nullptr;iterator _endofstorage=nullptr;};}