【C++】vector的模拟实现（详解）

上文链接

• 【C++】string类的模拟实现（详解）

一、整体框架

我们模拟 STL 库中的 vector 来实现一个自己的 vector 模板类，因此为了避免使用时与库中的 vector 重名，所以我们将其定义在一个叫 mine 的命名空间中。迭代器我们采用指针来实现，私有成员变量采用三个迭代器（指针）类型，分别指向容器的数据开始、数据结束、容器容量末端。

注：模板类不能将函数声明和定义分离到两个文件中。

namespace mine
{template<class T>class vector{public:typedef T* iterator;// ...private:iterator _start;iterator _finish;iterator _end_of_storage;};
}

---

二、构造函数

1. default

最简单的就是初始化一个空的 vector，那么所有的迭代器只需要初始化为空指针即可。

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}

或者我们可以在成员变量声明处给一个缺省值。

namespace mine
{template<class T>class vector{public:vector(){}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;}
}

---

2. fill

我们还可以将 vector 初始化为 n 个 val。在库中这个 val 是给了缺省值的，也就是说我们可以只指定一个数 n，表明存储的数据个数。然后让这个 vector 中的数据初始化成该数据类型的默认值。比如 int 类型默认为 0，double 类型默认为 0.0。

但是我们知道在 vector 中既可以存储普通的内置类型（比如 int）又可以存储自定义类型（比如 string ，vector 等），那么这个缺省值该怎么给呢？

我们可以直接给一个 T() 这样的匿名对象，即一个构造函数。因为在 C++ 中，内置类型通过升级也有了自己的构造函数。之所以这么做，就是为了满足这样的场景。

vector(size_t n, const T& val = T())
{reserve(n);  // 扩容，把容量扩至 nfor (size_t i = 0; i < n; ++i){push_back(val);  // 尾部插入数据}
}

需要补充的是，由于内置类型有了构造函数，所以我们定义一个内置类型变量的时候也可以通过下面的方式：

int a = int();  // 0
int b = int(1);  // 1
int c(2);  // 2
double d = double();  // 0.0

---

3. range

我们还可以使用迭代区间进行初始化。

template <class InputIterator>
vector(InputIterator first, InputIterator last)
{while (first != last){push_back(*first);++first;}
}

这里之所以用一个模板而不用 vector 内部的迭代器是因为用模板我们即可以支持 vector 的迭代器也可以支持其他类型的迭代器。

mine::vector<int> v1(10, 1); // 迭代区间初始化
mine::vector<int> v2(begin(), v1.begin() + 5);  // { 1, 1, 1, 1, 1 }

但是注意迭代区间（range）初始化和上面的填充（fill）初始化产生冲突。

当我们使用下面这种方式初始化的时候，编译器会报错，说非法的间接寻址。

mine::vector<int> v1(10, 1); 

这时因为这种初始化方式下我们调用的并不是填充初始化而是这里的迭代区间初始化。

vector(size_t n, const T& val = T());  // 填充初始化template <class InputIterator>  // 迭代区间初始化
vector(InputIterator first, InputIterator last)

我们对比两个构造函数的参数列表可以发现，当我们传入 (10, 1) 两个参数时，如果想要调用填充初始化，那么 10 这个默认为 int 类型的值还要通过类型转换成 size_t 才能进行传参。而调用第二个迭代区间初始化直接可以顺利传参，不需要类型准换。所以编译器会优先选择更适合的一个函数进行调用，即这里的迭代区间初始化。而迭代区间初始化有解引用操作，但是我们传过来的参数是 int 类型，所以才会出现非法的间接寻址这样的错误。

为了避免这样的错误，我们可以写两种形式的填充初始化。一种是第一个参数传 size_t 类型，即我们上面写的那种，另一种我们写一个第一个参数传 int 类型的。这样在传参的时候就不会调用到迭代区间去了。

vector(size_t n, const T& val = T())
{// ...
}vector(int n, const T& val = T())
{// ...
}

---

4. initializer list

在 C++11 中还支持一种初始化方式如下：

vector<int> v{ 1, 2, 3 };

即我们可以用一个 {} 指定元素然后对一个 vector 对象进行初始化。它的底层原理是用了一个叫 initializer list 的类来实现的。

其内部有 4 个成员函数。

原理是通过用 begin 获取 {} 中第一个元素的迭代器，用 end 获取 {} 中最后一个元素下一个位置的迭代器，然后通过循环来初始化一个 vector 对象。

vector(initializer_list<T> il)
{reserve(il.size());  // 开和 {} 一样大的空间for (auto& e : il)  // 支持迭代器就支持范围for{push_back(e);}
}

需要注意的是这里的范围 for 中一定要加 &。因为 vector 中存储的可能是自定义类型比如 string、vector。当内层的自定义类型修改的时候，那么在 vector 中所存储的自定义类型也要修改，所以要加引用。

---

三、析构函数

两个核心：释放空间，置空指针。但是注意如果原本的空间本身就为空，即三个私有成员都是空指针，那么就不需要释放了，所以在先前就要判断一下。

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

---

四、拷贝构造

为了避免深浅拷贝的问题，我们还需要自己实现一份拷贝构造函数。即开一样大的空间，然后拷贝数据。

vector(const vector<T>& v)
{reserve(v.capacity());for (auto& e : v)  // 注意这里一定要加&{push_back(e);  // 依次拷贝数据}
}

---

五、赋值重载

我们可以老老实实地像拷贝构造一样地写，我们也可以采用一种现代的写法。

vector<T>& operator=(vector<T> v)
{swap(v);return *this;
}

原理是这里的参数是一个传值传参，它会调用拷贝构造拷贝出一个新的对象。比如 v1 = v2 这样一个赋值语句就会将 v2 拷贝给 v，然后这时只需要将 v1 与 v 做一个交换即可达到 v2 赋值给 v1 的效果。而 v 是一个局部变量，出了这个函数会自动销毁。

添加一个返回值的目的是为了支持像 v1 = v2 = v3 这样的连续赋值语句。

---

六、迭代器

基本的迭代器这里我们实现两种，一种是普通的 iterator，一种是 const 版本的 const_iterator。

typedef T* iterator;
typedef const T* const_iterator;  // const 在 * 左边表示指向的内容不可修改

---

1. begin

返回数据开始位置的迭代器。

iterator begin()
{return _start;
}// const 版本
const_iterator begin() const
{return _start;
}

---

2. end

返回最后一个数据下一个位置的迭代器。

iterator end()
{return _finish;
}// const 版本
const_iterator end() const
{return _finish;
}

---

七、容量相关

1. capacity

返回 vector 所能存储的最大数据个数，即我们开辟的总空间大小。所以只需要让 _end_of_storage 指针和 _start 指针做差即可。又由于此函数不会对任何数据进行修改，最好将其设置成 const 成员函数。

size_t capacity() const
{return _end_of_storage - _start;
}

---

2. size

返回 vector 存储的有效数据个数。只需要让 _finish 指针和 _start 指针做差即可。同样我们将其设计为 const 成员函数。

size_t size() const
{return _finish - _start;
}

---

3. reserve

在标准库中的 reverse 的操作是对 vector 进行扩容操作，即传入一个 n，将 vector 的总空间扩至 n。如果这个 n 小于总空间大小，那么这个函数不起作用，因为 vector 不会缩容。

扩容的思路就是开辟一块新的空间，然后将原来旧空间的数据拷贝过去再释放旧空间。拷贝这里采用 memcpy。

注意事项：

1. 一定要事先计算旧空间的大小再更新迭代器。
2. memcpy 之前检查一下旧空间是否为空，否则拷贝时会出问题。

void reserve(size_t n)
{if (n > capacity())  // 只有 n 大于总空间大小才扩容{size_t old_size = size();  // 注意这里一定要事先计算旧空间大小T* tmp = new T[n];if (_start)  // 检查旧空间是否为空{memcmp(tmp, _start, sizeof(T) * size());  // 拷贝数据delete[] _start;  // 释放原来的空间}// 更新迭代器_start = tmp;_finish = tmp + old_size;_end_of_storage = _start + n;}
}

如果不先计算就空间容量大小而在更新数据的时候用 size() 的话就会出问题。

void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];if (_start) {memcmp(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = tmp + size();  // 这样写会出问题_end_of_storage = _start + n;}
}

这是因为 size() 函数计算的是 _finish - _start，而 _finish 指向的是旧空间的数据结束的位置，而 _start 已经更新了，现在指向的是新空间 tmp 的数据开始位置。所以不能在 _start 更新之后用 size() 去更新 _finish，可以在没更新之前把旧空间的大小算出来之后再更新。

但是，这就是正确的了吗？其实还是不够完善。如果 vector 内部存储的是内置类型，那么这样写没有问题，但是一旦内部存储的是自定义类型比如 string，就可能会出问题！

int main()
{mine::vector<string> v;v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111");v.push_back("1111111111111");for (auto& e : v) cout << e << endl;return 0;
}

这是由于 memcpy 所导致的浅拷贝的问题。vector 中每一个位置都存储的是一个 string 对象，每一个位置都指向一块堆上开辟的空间。但是 memcpy 只能做到按字节进行拷贝，也就是一种浅拷贝。拷贝出来的对象中所存储的 string 对象依然指向同一块空间，那么将原来的空间 delete 掉之后就会导致出错。所以我们需要修改为深拷贝。

void reserve(size_t n)
{if (n > capacity()){size_t old_size = size(); T* tmp = new T[n];if (_start) {// memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < old_size; ++i)  // 深拷贝{tmp[i] = _start[i];}delete[] _start; }_start = tmp;_finish = tmp + old_size;_end_of_storage = _start + n;}
}

这里每一个 _start[i] 都对应了一个 string 类的对象，当它在赋值号的右边时，会调用它自己的拷贝构造函数，从而去开辟一块新的空间，达到深拷贝的效果。

这下我们再来运行上面的代码就不会出错了。

---

4. resize

对容器的 size 进行修改，分为三种情况：

• n > capacity：扩容并填充数据。
• size < n < capacity：填充数据。
• n < size：删除数据。

void resize(size_t n, T val = T())
{if (n > size())  // 插入数据{// 扩容到 n// n 可能比总容量小，但是不影响，因为 reserve 内部会判断reserve(n); while (_finish != _start + n){*_finish = val;++_finish;}}else  // 删除数据{_finish = _start + n;}
}

---

八、获取元素

1. operator[ ]

重载 [] 想要访问第 i 个位置的元素，返回 _start[i] 即可，注意检查 i 的范围是否合法。

T& operator[](size_t i)
{assert(i < size());return _start[i];
}

---

九、修改操作

1. push_back

尾插操作，传入一个元素 x，在 vector 的尾部插入该元素。

具体的实现思路就是如果容器没满，那么直接在最后一个位置插入数据然后更新 _finish。如果容器满了则先扩容再插入数据。

void push_back(const T& x)
{if (_finish == _end_of_storage){// 如果容量为 0 则扩容至 4，不为 0 则扩容至 2 倍size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);  // 扩容}*_finish = x;  // 插入数据++_finish;  
}

---

2. pop_back

尾删操作，删除末尾的元素。只需要将 _finish 减 1 即可。不需要将处理尾部的数据，因为 _start 到 _finish 这一部分的数据才是有效数据，不在这部分的数据我们不关心。注意容器没有存有效数据时就不能再删除了。

void pop_back()
{assert(_finish > _start);  // 保证容器中存储了数据，不为空，为空就断言--_finish;
}

---

3. insert

在指定位置 pos 处插入数据 x。如果容器满了则先扩容再插入数据。（pos 是一个迭代器）

void insert(iterator pos, const T& x);// 使用
insert(v.begin() + 1, 2);

具体实现思路为：

1. 判断 pos 位置是否合法。
2. 判断是否需要扩容。
3. 挪动数据。
4. 插入数据并更新迭代器。

根据上面的步骤，我们大致可以写出以下的代码，观察下面的代码存在什么问题？

void insert(iterator pos, const T& x)
{// 检查 pos 位置是否合法assert(pos >= _start);assert(pos <= _finish);// 判断是否需要扩容if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}iterator it = _finish - 1;while (it >= pos)  // 挪动数据{*(it + 1) = *it;--it;}*pos = x;  // 插入数据++_finish;
}

上面的代码当不扩容时不会出错，但是一旦扩容就会出问题。这是因为扩容我们是需要找一块新空间的，那么扩容之后 _start 和 _finish 的地址都改变了，但是 pos 的位置还指向旧空间，因此就会导致 while 循环的循环次数不对，从而出问题。这种情况我们称之为 “迭代器失效”，这里的迭代器失效是由扩容造成的。

因此，我们需要在扩容后更新 pos 的位置。

void insert(iterator pos, const T& x)
{assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;  // 记录 pos 与 _start 的相对距离size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;  // 在扩容之后更新 pos}iterator it = _finish - 1;while (it >= pos)  // 挪动数据{*(it + 1) = *it;--it;}*pos = x;  // 插入数据++_finish;
}

虽然上面的代码解决了扩容时导致的迭代器失效的问题，但是我们在使用时仍需注意迭代器失效。

mine::vector<int> v{1, 2, 3, 4};
int x;
cin >> x;
auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{v.insert(p, x * 10);// insert 之后 pos 不能使用，因为 pos 可能失效，不要访问这个迭代器// cout << *p << endl;
}

---

4. erase

删除 pos 位置的数据（pos 为迭代器）。

和 insert 的思路类似，erase 的实现可分为以下几步：

1. 判断 pos 位置是否合法。
2. 挪动数据。
3. 更新迭代器。

void erase(iterator pos)
{// 判断 pos 位置是否合法assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish)  // 挪动数据{*(it - 1) = *it;++it;}--_finish;  // 更新迭代器
}

了解了 erase 的基本原理之后，我们再来看看有关于它的一个有趣的现象。

void test_vector()
{std::vector<int> v{ 1, 2, 2, 3, 4, 5, 6 };for (auto e : v) cout << e << " ";cout << endl;// 删除所有偶数// 在 VS 下，会崩溃std::vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) v.erase(it);else ++it;}for (auto e : v) cout << e << " ";
}int main()
{test_vector();return 0;
}

运行结果如下：

为什么会崩溃呢？是因为迭代器失效的问题。虽然说从代码理解上开看 erase 并不会造成迭代器失效的问题，它不像 insert 那样会扩容从而导致空间的地址的改变。但是在 VS 下认为 erase 后 it 失效了，它对失效的迭代器进行了强制检查，访问时就会报错。相当于 VS 认为该迭代器对应的位置被删除了，默认它变成了一个无效的迭代器，对它进行了强制检查，因为报错。而在 g++ 下就并没有这样的强制检查。

那么怎么解决这样的问题呢？在标准库中的 erase 函数还提供了一个返回值，返回被删除位置下一个位置的迭代器。

我们可以在每次删除元素之后重新更新迭代器，这样在 VS 下就不会认为它是一个失效的迭代器了。

void test_vector()
{std::vector<int> v{ 1, 2, 2, 3, 4, 5, 6 };for (auto e : v) cout << e << " ";cout << endl;// 删除所有偶数// 在 VS 下，会崩溃std::vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) it = v.erase(it);  // 更新迭代器else ++it;}for (auto e : v) cout << e << " ";
}

所以我们基于返回值这一点我们可以对我们自己实现的 erase 函数也增加一个返回值。

iterator erase(iterator pos)
{assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;
}

---

5. swap

交换两个 vector 之间的“值”。仅需交换它们的成员变量即可。交换成员变量可直接用库中的 swap 函数。

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

---

十、完整代码

注：不能将模板的函数声明与定义分离到两个文件。

// vector.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<cstring>
#include<cassert>
#include<iostream>using namespace std;namespace mine
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}vector(){}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}vector(int n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; ++i){push_back(val);}}template <class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}vector(initializer_list<T> il){reserve(il.size());for (auto& e : il){push_back(e);}}vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}vector<T>& operator=(vector<T> v){swap(v);return *this;}~vector(){if (_start){delete[] _start;_start = _finish = _end_of_storage = nullptr;}}size_t capacity() const{return _end_of_storage - _start;}size_t size() const{return _finish - _start;}void reserve(size_t n){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];if (_start) {// memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < old_size; ++i){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = tmp + old_size;_end_of_storage = _start + n;}}void resize(size_t n, T val = T()){if (n > size())  // 插入数据{// 扩容到 n// n 可能比总容量小，但是不影响，因为 reserve 内部会判断reserve(n); while (_finish != _start + n){*_finish = val;++_finish;}}else  // 删除数据{_finish = _start + n;}}T& operator[](size_t i){assert(i < size());return _start[i];}void push_back(const T& x){if (_finish == _end_of_storage){size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);}*_finish = x;++_finish;}void pop_back(){assert(_finish > _start);--_finish;}iterator insert(iterator pos, const T& x){assert(pos >= _start);assert(pos <= _finish);if (_finish == _end_of_storage){size_t len = pos - _start;size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newcapacity);pos = _start + len;}iterator it = _finish - 1;while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it < _finish){*(it - 1) = *it;++it;}--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}