C++ 初阶篇 STL 模拟实现之 vector

前言

STL 容器是 C++ 开发中绕不开的 “神兵利器”，而vector作为最常用的动态数组容器，更是新手入门 STL 的核心内容。但多数时候，我们只是 “会用”vector，却对它的底层逻辑一知半解 —— 比如它如何动态扩容？push_back的内存管理是怎样的？构造函数的匹配规则为何如此复杂？

一、vector 的使用

1.1、 vector的介绍

简单说，vector是 C++ 里可以动态变大小的数组—— 它既保留了普通数组 “连续存储、下标访问高效” 的优点，又解决了普通数组 “大小固定、不能自动扩容” 的痛点。

它的底层逻辑是动态分配的数组：

当你往vector里加新元素时，它会自动管理内存 —— 如果当前数组存满了，就会重新分配一块更大的空间，把旧元素全搬过去，再继续存新元素（不过这个 “搬家” 操作开销不低，所以vector会提前多分配一些额外空间，避免频繁搬家）。

vector 是我们学习的第一个真正的 STL 容器，它接口的使用方式和 string 有一点点的不同，但大部分都是一样的，所以这里我们就只演示其中一些接口的使用，大家如果有疑惑的地方直接在 cplusplus 是上面查看对应的文档即可。

1.2、构造函数

vector 提供了四种构造方式 – 无参构造、n 个 val 构造、迭代器区间构造以及拷贝构造：

其中构造函数的最后一个参数 alloc 是空间配置器，它和内存池有关，作用是提高空间分配的效率；我们日常使用时不用管这个参数，使用它的缺省值即可，但是可能有极少数的人想要用自己实现的空间配置器来代替 STL 库提供的，所以留出了这一个参数的位置。

vector<int> v1; // 默认构造：空向量
vector<int> v2(5, 1); // 5 个元素，每个初始化为 1
vector<int> v3(v2.begin(), v2.end()); // 用迭代器区间拷贝构造
vector<int> v4(v3); // 直接拷贝构造

// 遍历输出 v1：当前为空，循环不会执行
for (size_t i = 0; i < v1.size(); ++i)
{
cout << v1[i];
}
cout << endl; // 仅换行

// 遍历输出 v2：5 个 1
for (size_t i = 0; i < v2.size(); ++i)
{
cout << v2[i];
}
cout << endl;

// 再次遍历输出 v3（与上一段完全相同）
for (size_t i = 0; i < v3.size(); ++i)
{
cout << v3[i];
}
cout << endl;

// 再次遍历输出 v4（与上一段完全相同）
for (size_t i = 0; i < v4.size(); ++i)
{
cout << v4[i];
}
cout << endl;

需要注意的是，迭代器区间构造是一个函数模板，即我们可以用其他类来构造 vector 对象：

string s = "hello";
vector<char> v(s.begin(), s.end()); // 用迭代器区间拷贝构造
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i];
}
cout << endl;

同时，上面还有一个非常重要的细节：

在 n 个 val 的构造中，val 的缺省值是 T 的匿名对象就像是T()，该对象使用 T 的默认构造来初始化，而不是以 0 作为缺省值，这是因为 T 不仅仅可能是内置类型，也可能是自定义类型，比如 string、list、vector； 当 T 为自定义类型时，0 就不一定能够对 val 进行初始化，所以我们需要使用 T 的匿名对象来调用默认构造完成初始化工作；当 T 为内置类型时，我们仍然可以以这种方式进行初始化，因为 内置类型也具有构造函数，你没听错，内置类型也是有构造函数的，大家可以理解为，为了解决上面这种情况，编译器对内置类型进行了特殊处理,像是把自定义类型也包装了一下；

利用匿名对象调用构造函数来作为缺省值的方法在下面 模拟实现中也有体现。

1.3、扩容机制

vector 的扩容机制和 string 的扩容机制是一样的，因为它们都是动态增长的数组：VS 下大概是 1.5 被扩容，Linux g++ 下是标准的二倍扩容，多出来的也是一样因为内存对齐的原因，测试用例如下：

void TestVectorExpand()
{
size_t sz;
vector<int> v;
sz = v.capacity();
cout << "making v grow:\\n";
for (int i = 0; i < 1000; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\\n';
}
}
}

1.4、三种遍历方式

和 string 一样，vector 也支持三种遍历方式 – 下标加[]遍历、迭代器遍历、范围for遍历：

vector<int> v(10, 5); // 10 个元素，每个值为 5

// 1. 下标 + []
for (int i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;

// 2. 迭代器
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;

// 3. 范围 for
for (auto& e : v)
cout << e << " ";
cout << endl;

需要注意的是，vector 和 string 之所以支持 下标 + [] 的方式遍历，是因为它们底层都是数组，而数组支持随机访问，但是像我们后面要学习的 list set map 等容器，它们的底层不是数组，不支持随机访问，就只能通过迭代器和范围 for 的方式进行遍历了；不过，范围 for 只是一个外壳，它在使用时也是被替换成迭代器，所以其实迭代器遍历才是最通用的遍历方式。

1.5、容量操作

vector 有如下容量相关的接口：

其中，最重要的两个函数是 reserve 和 resize，reserve 只用于扩容，它不改变 size 的大小；而 resize 是扩容加初始化，既会改变 capacity，也会改变 size；

注意：reserve 和 resize，包括后面的 clear 函数都不会缩容，因为缩容需要开辟新空间、拷贝数据、释放旧空间，而对于自定义类型又有可能存在深拷贝问题，时间开销极大；vector 中唯一可能缩容的函数就只有 shrink_to_fit，对于它来说，如果 capacity 大于 size，它会进行缩容，让二者相等。

1.6、元素访问

其中，operator 和 at 都是返回 pos 下标位置元素的引用，且它们内部都会对 pos 的合法性进行检查；不同的是，operator[] 中如果检查到 pos 非法，那么它会直接终止程序，报断言错误，而 at 则是抛异常；

1.7、修改 – 迭代器失效

vector 提供了如下接口来进行修改操作：

vector<int> v(5,1);
for (auto& e : v)
cout << e << " ";
cout << endl;
v.assign(2, 2);
for (auto& e : v)
cout << e << " ";
cout << endl;
v.push_back(3);
for (auto& e : v)
cout << e << " ";
cout << endl;
v.pop_back();
for (auto& e : v)
cout << e << " ";
cout << endl;
v.insert(v.begin(), –1);
for (auto& e : v)
cout << e << " ";
cout << endl;
auto it= v.erase(v.begin());
for (auto& e : v)
cout << e << " ";
cout << endl;
cout << "删除后下一个的位置"<< * it << endl;
vector<int> tmp(6, 6);
v.swap(tmp);
for (auto& e : v)
cout << e << " ";
cout << endl;
v.clear();
for (auto& e : v)
cout << e << " ";
cout << endl;

• assign && push_back && pop_back assign 函数用来替换 vector 对象中的数据，支持 n 个 val 替换，以及迭代器区间替换，push_back 尾插、pop_back 尾插，这些接口的使用和 string 一模一样，这里就不再过多阐释；
• insert && erase 和 string 不同，为了提高规范性，STL 中的容器都统一使用 iterator 作为 pos 的类型，并且插入/删除后会返回 pos： 所以，以后我们如果要在中间插入或删除元素的话，必须配合算法库里面的 find 函数来使用： 代码演示

vector<int> v;
for (size_t i = 0; i < 20; i++)
{
v.push_back(i);
}
//找到6删除6
vector<int>::iterator tmp= find(v.begin(),v.end(),6);
v.erase(tmp);
for (auto& e : v)
cout << e << " ";

这里其实有一个问题我们来解引用一下*tmp 程序报了一个这个错误这个就是迭代器失效了为什么了我来画个图理解一下 如何解决了我们让tmp指向删除元素的下一个位置就好了 那我们继续思考一下是不是insert 也会有问题先分析在验证一下

但是为了代码的可移植性，我们 统一认为 insert 和 erase 之后迭代器会失效，所以，如果要再次使用迭代器，我们必须对其进行更新；我们以移除 vector 中的所有偶数为例：

vector<int> v;
vector<int>::iterator it=v.begin();
for (size_t i = 0; i < 20; i++)
{
it=v.insert(it, i);
}
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
it++;
}
for (auto& e : v)
cout << e << " ";
cout << endl;

• swap 和 string 一样，由于算法库 swap 函数存在深拷贝的问题，vector 自己提供了一个不需要深拷贝的 swap 函数，用来交换两个 vector 对象：

同时，为了避免我们不使用成员函数的 swap，vector 还将算法库中的 swap 进行了重载，然后该重载函数的内部又去调用成员函数 swap：

二、vector 的模拟实现

2.1、浅析 vector 源码

对于编程来说，学习初期进步最快的方式就是阅读别人优秀的代码，理解其中的逻辑和细节后自己独立的去实现几次，学习 STL 也是如此；我们可以适当的去阅读 STL 的源码，当然我们并不是要逐行的进行阅读，因为这样太耗费时间，况且其中很多 C++ 的语法我们也还没学。

当前阶段，我们阅读 STL 源码是为了学习 STL 库的核心框架，然后根据这个框架自己模拟实现一个简易的 vector (只实现核心接口)；阅读源码与模拟实现能够让我们更好的了解底层，对 STL 做到 能用，并且 明理。 可以看到，vector.h 仅仅是将几个头文件包含在一起，vector 的主要实现都在 stl_vector.h 里面。

2.2、核心框架

我们可以根据上面的 vector 源码来得出 vector 的核心框架：

namespace ljm {
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

public:
//成员函数

private:
T* _start;
T* _finish;
T* _end_of_storage;
};
}

可以看到，vector 的底层和 string 一样，都是一个指针指向一块动态开辟的数组，但是二者不同的是，string 是用 _size 和 _capacity 两个 size_t 的成员函数来维护这块空间，而 vector 是用 _finish 和 _end_of_storage 两个指针来维护这块空间；虽然 vector 使用指针看起来难了一些，但本质上其实是一样的 _size = _finish – _start, _capacity = _end_of_storage – _start

2.3、构造函数

//无参构造
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
}

// 填充构造：创建n个值为val的元素
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
_start = new T[n];
_finish = _start;
_endofstorage = _start + n;
while (n— && n != 0)
{
*_finish = val;
_finish++;
}
}

// 范围构造：通过其他容器/序列的迭代器范围[first,last)初始化
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
size_t n = last – first;//这里计算链式存储结构的时候会有问题，n不对，我后续回来实现那一个方法的。
_start = new T[n];
_finish = _start;
_endofstorage = _start + n;
while (first != last)
{
*_finish=*first;
_finish++;
first++;
}
}

在我们模拟实现了构造函数中的迭代器区间构造和 n 个 val 构造后，我们会发现一个奇怪的问题，我们使用 n 个 val 来构造其他类型的对象都没问题，唯独构造 int 类型的对象时会编译出错，如下：

这是由于编译器在进行模板实例化以及函数参数匹配时会调用最匹配的一个函数，当我们将 T 实例化为 int 之后，由于两个参数都是 int，他就走了迭代器构造，所以对于迭代器构造函数来说，它会直接将 InputIterator 实例化为 int；

但对于 n 个 val 的构造来说，它不仅需要将 T 实例化为 int，还需要将第一个参数隐式转换为 size_t；所以编译器默认会调用迭代器构造，同时由于迭代器构造内部会对 first 进行解引用，所以这里报错 “非法的间接寻址”；

这个时候有两种办法解决这个问题：

方法1：

将6显式指定为size_t类型（写成10u），这样编译器会优先匹配填充构造函数（而非范围构造函数），从而正常创建包含 10 个值为 1 的元素的 vector。

方法2：

新增一个以int类型为参数的填充构造函数重载版本，让vector v(10, 1)这类传入int型数值的场景，能直接匹配该重载函数，避免编译器误匹配范围构造函数。

2.4拷贝构造和赋值运算符重载（深拷贝）

由于vector包含动态申请的资源，因此不能使用浅拷贝（浅拷贝仅复制指针地址，会导致多个对象共用同一块内存，引发析构时重复释放等问题），必须实现深拷贝：

//swap
void swap(vector<T>& v)
{
std::swap(_start, v._start); //复用算法库的swap函数
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._end_of_storage);
}

//拷贝构造传统写法
//vector(const vector<T>& v)
//:_start(nullptr)
//, _finish(nullptr)
//, _endofstorage(nullptr)
//{
//size_t n = v._start -v. _finish;//这里计算链式存储结构的时候会有问题，n不对，我后续回来实现那一个方法的。
//_start = new T[n];

////浅拷贝 – 容器存储的是有动态资源的自定义类型，使用memcpy就会造成浅拷贝
//// 当 vector 里存的是带有动态资源的类（比如含 char* 成员），memcpy 会把同一块堆地址复制给两个对象，结果双份析构 → 同一块内存被 free 两次 → 程序崩溃。
////memcpy(_start,v._start,sizeof(T)* v.size());

////深拷贝
//for (size_t i = 0; i < v.size(); i++)
//{
//_start[i] = v._start[i];
//}
//_finish = _start + v.size();
//_endofstorage = _start + v.capacity();
//}

//拷贝构造现代写法
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
vector<T> tmp(v.begin(), v.end()); //复用构造函数和swap函数
swap(tmp);//空手套白狼
}

///赋值重载传统写法
//vector<T>& operator=(vector<T>& v)
//{
//T* tmp = new T[v.capacity()];
//for (size_t i = 0; i < v.size(); i++)
//{
//tmp[i] = v._start[i];
//}
//delete[] _start;

//_start = tmp;
//_finish = _start + v.size();
//_endofstorage = _start + v.capacity();

//return *this;
//}

//赋值重载现代
// v1 = v2
vector<T>& operator=(vector<T> v)
{
swap(v);

return *this;
}

2.4、析构函数

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

2.5、迭代器

由上面可得

iterator begin()
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}

2.6、vector容量相关接口

1、size

size_t size()
{
return _finish – _start;
}

2、capacity

size_t capacity()
{
return _endofstorage – _start;
}

3、empty

bool empty()
{
return size() == 0;
}

4、reserve

void reserve(size_t n)
{

if (n > capacity())
{
T* tmp = new T[n];//开空间
size_t sz = size();
if (_start)
{
for (size_t i = 0; i < sz; i++)//拷数据
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
else
{
return;
}

}

该接口用于为vector预留至少n个元素的存储空间，仅当n大于当前容器容量时才执行扩容操作；扩容时先记录当前有效元素个数，开辟n个大小的临时空间，通过循环调用元素赋值重载完成深拷贝（解决自定义类型动态资源的浅拷贝问题），随后释放原空间，更新容器的_start、_finish、_endofstorage指针，使容器容量更新为n，且保留原有全部有效元素，有效避免频繁扩容带来的性能损耗。

扩容接口有两个特殊问题：

1、自定义类型动态资源的浅拷贝问题：当容器存储的是带动态资源的自定义类型时，直接用memcpy拷贝会导致浅拷贝，这一问题的解决思路在赋值运算符重载和拷贝构造的内容中已有说明，此处不再赘述；

2、必须提前用 sz 记录当前有效元素个数：因为扩容后原空间会被释放，_start指针会指向新空间，若此时再调用size()获取元素个数，会因_start和_finish不再指向原空间而计算错误，所以需要在扩容前先把当前元素个数存到 sz 变量中。 5、resize 先看是什么样的

////1.n<capacity()&&n<size,不用扩容，也不用加数据
vector<int> v1(5,6);
for (auto v:v1)
{
cout << v;
}
cout << endl;
cout << "1.开始：" << v1.size() << " " << v1.capacity() << endl;
v1.resize(2, 2);
for (auto v : v1)
{
cout << v;
}
cout << endl;
cout << "1.结束：" << v1.size() << " " << v1.capacity() << endl;
//2.n<capacity()&&n>size,不用扩容，加数据
v1.resize(5, 5);
for (auto v : v1)
{
cout << v;
}
cout << endl;
cout << "1.结束：" << v1.size() << " " << v1.capacity() << endl;

v1.resize(10, 2);
for (auto v : v1)
{
cout << v;
}
cout << endl;
cout << "1.结束：" << v1.size() << " " << v1.capacity() << endl;

这段resize接口用于调整vector的有效元素个数：

第二个参数的缺省值是调用默认构造，内置类型由于加入了模板，也有了自己的默认构造

当 n 小于当前元素数时，直接截断（仅调整_finish指针，保留前 n 个元素）；

当 n 更大时，先调用reserve预留空间，再将新增位置填充为指定值，最终更新_finish指针，既支持缩小容器，也能安全扩容并填充元素。

void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n; // 缩小，析构多余元素（如有需要）
}
else if (n > size())
{
reserve(n); // reserve 内部会判断是否需要扩容

size_t old_size = size();
for (size_t i = old_size; i < n; i++)
{
_start[i] = val;
}
_finish = _start + n;
}
}

2.7、vector增删查改

1、push_back

void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);

}
*_finish = x;
_finish++;

}

2、insert

//指定位置插入
iterator insert(iterator pos, const T& x)
{
if (_finish == _endofstorage)
{
//记录相对位置
size_t len = pos – _start;

size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);

//之前的pos位置失效了之前的是基于没扩容前的
pos = _start + len;
}
iterator end = _finish ;
while (pos <= end)
{
*end = *(end–1);
end—;
}
*pos = x;
_finish++;
return pos;
}

3、erase

// 指定位置删除元素
iterator erase(iterator pos)
{
// 断言：确保pos迭代器合法（在有效元素区间内），且vector非空，防止非法访问
assert(pos >= _start && pos < _finish && size()>0);

// 定义迭代器it，从pos的下一个元素开始遍历
iterator it = pos + 1;
// 循环：将pos之后的所有元素依次向前移动一位，覆盖待删除元素（实现逻辑删除）
while(it != _finish)
{
*(it – 1) = *it; // 后一个元素的值赋给前一个元素，完成前移覆盖
it++; // 迭代器后移，处理下一个元素
}

// 尾指针前移一位，缩小有效元素范围（底层内存未释放，仅标记该位置元素无效）
—_finish;

// 返回原pos迭代器（此时pos指向被删除元素的下一个有效元素，避免外部迭代器失效）
return pos;
}

4、pop_back

//尾删
void pop_back()
{
earse(—end());
}

5、operator[]

// 可读可写版本：返回非const引用，支持修改元素值
T& operator[](size_t pos)
{
assert(pos < size()); // 断言确保访问的下标合法，不越界

return _start[pos]; // 返回对应位置元素的引用，支持读和写
}

// 仅读版本：const成员函数，返回const引用，禁止修改元素值
const T& operator[](size_t pos) const
{
assert(pos < size()); // 断言确保访问的下标合法，不越界

return _start[pos]; // 返回对应位置元素的const引用，仅支持读操作
}

6、find

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val)
{
while (first != last)
{
if (*first == val)
{
return first;
}

first++;
}

return last;
}