【C++】vector的模拟实现

---

前言

本篇博客讲的是vector的模拟实现，因为上一篇博客已经模拟了string的实现，所以在模拟vector的实现中会比较熟悉，模拟vector的实现是为了我们更好地理解和掌握vector，接下来我们会实现vector一些重要的接口。

一. vector的底层

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
//用命名空间MyVector封装vector，避免与std库的vector冲突
namespace MyVector
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;private:iterator start; //指向数据块的开始iterator finish; //指向有效数据的末尾iterator end_of_storage; //指向存储容量的末尾};
}

vector的底层实现是由三个迭代器start,finish,end_of_storage来管理内存和数据的，而vector的迭代器就是一个原生态指针T*

1. start：指向vector中第一个元素的地址。
2. finish：指向vector中最后一个元素的下一个位置（即逻辑上的结束位置）。
3. end_of_storage：指向vector分配的内存量的结束位置（即实际分配的内存大小）

注意：end_of_storage是一个指针，它指向分配的内存块的逻辑结束位置，但并不是指向具体的内存单元，而是指向分配的内存块的末尾的下一个位置。它的作用是表示分配的内存的容量上限，而不是实际存储数据的地址。总的来说，end_of_storage是一个虚拟的边界标记。

内存管理

• start到finish：表示vector中实际存储的元素范围。
• finish到end_of_storage：表示已分配但未使用的内存区域。

当 vector 的容量不足时（例如调用 push_back 或 resize），它会重新分配一块更大的内存区域，并将旧数据复制到新内存中，然后释放旧内存。这种机制确保了 vector 的动态扩展能力。

侯捷老师《STL源码剖析》的原图如下：

begin()就是start，end()就是finish

注意：vector是一个类模板，所以在vector的实现中声明和定义不能分离。

类模板的实例化发生在编译阶段，而不是链接阶段。编译器需要知道类模板的完整定义（包括实现）才能生成具体的代码。如果实现部分不在头文件中，编译器无法完成模板的实例化。

模板的编译机制：

模板类的代码（包括定义和实现）必须在编译时完全可见。这是因为模板类的实例化（instantiation）是基于模板参数（如类型参数）动态生成具体代码的。编译器需要在编译时根据模板参数生成具体的代码，因此模板的定义和实现不能分离。

二. 关于容量和大小的函数

2.1 size和capacity

size_t size() const
{return finish - start; //返回容器中有效数据的个数
}
size_t capacity() const
{return end_of_storage - start; //返回容器的最大容量
}

2.2 reserve

reserve规则：
1.当n大于对象当前的容量，就将容量扩容到n。
2.当n小于等于对象当前的容量，就什么都不做。

void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n]; //开辟新空间if (start) {memcpy(tmp, start, sizeof(T) * oldsize); //拷贝数据}delete[] start; //释放旧空间start = tmp;finish = start + oldsize;end_of_storage = start + n;}
}

注意：在进行扩容操作前需要记录当前容器的有效数据个数。

因为要改变finish指针，而finish等于start+有效数据的个数，但是start已经指向新空间了，当试图调用size函数获取有效数据个数时就会返回一个随机值，所以在进行操作之前就要先将容器的有效数据个数记录下来。

2.3 resize

resize规则：
1.当n大于容器的有效数据个数size时，将size扩大到n，用val填充未初始化的数据，如果val没有给出，val默认为容器所存储数据类型的默认值。
2.当n小于容器的有效数据个数size时，将size缩小到n。

void resize(size_t n, const T& val = T())
{if (n < size()){finish = start + n;}else{reserve(n); //检查是否需要扩容while (finish < start + n){*finish = val;finish++;}}
}

注意：在C++中，对于自定义类型需要通过默认构造函数：类型()构造出一个临时对象，val再引用这个临时对象，而对于内置类型也可以通过类型()获得该类型的默认值，这是为了兼并内置类型和自定义类型。

2.4 empty

判断容器是否为空

bool empty() const
{return start == finish;
}

三. vector的默认成员函数

3.1 构造函数

3.1.1 无参构造函数

对于vector的无参构造函数，直接将三个成员变量都初始化为nullptr即可。

vector():start(nullptr),finish(nullptr),end_of_shorage(nullptr)
{ }

3.1.2 构造初始化为n个val值

构造一个vector容器，该容器的数据为n个val值。先调用reserve函数将容器的容量设置为n，再将n个val插入容器当中即可。

vector(size_t n, const T& val = T())
{reserve(n);for (size_t i = 0; i < n; i++){start[i] = val;}finish = start + n;
}

3.1.3 用initializer_list构造初始化

在 C++ 中，std::initializer_list 是一个模板类，用于表示初始化列表（即用 {} 包围的值列表）。它通常用于支持统一初始化语法，这是 C++11 引入的一种初始化方式。std::initializer_list 提供了一种类型安全的方式来处理初始化列表，并且可以在函数参数、数组初始化、容器初始化等场景中使用。

基本概念

std::initializer_list 是一个轻量级的容器，它存储了初始化列表的开始和结束指针，但不会复制列表中的元素。它的主要目的是提供一种统一的语法来初始化对象或传递参数。

语法

std::initializer_list<T> list = { value1, value2, ..., valuen };

其中 T 是列表中元素的类型。

vector(initializer_list<T> il)

这个构造函数的作用是将 initializer_list< T > 中的元素复制到 vector 的内部存储中。

实现细节

从 initializer_list 中获取元素的迭代器范围（begin() 和 end()），遍历每个元素，将这些元素逐个复制到vector的内部存储中。

注意事项

1. std::initializer_list 的生命周期与初始化列表的生命周期相同。例如，如果初始化列表是在函数调用中传递的，那么 std::initializer_list 的生命周期只持续到函数调用结束。
2. std::initializer_list 中的元素是只读的，不能直接修改。如果需要修改，可以先复制到 vector 中，然后对 vector 进行操作。

vector(initializer_list<T> il)
{reserve(il.size());size_t i = 0;for (auto& x : il){start[i++] = x;}finish = start + i; //不要忘记修改finish
}

3.1.4 使用迭代器区间进行构造初始化

为了不止可以用该容器的迭代器区间构造初始化，也可以用其他容器的迭代器区间进行构造初始化，所以我们可以将该构造函数设计为一个函数模板，用模板参数自动推导出迭代器的类型即可。

template<class InputIterator>
vector(InputIterator first, InputIterator last) //左闭右开
{reserve(last - first);size_t i = 0;while (first != last){start[i++] = *first;first++;}finish = start + i;
}

注意：这里有个小bug，如果调用构造函数MyVector::vector< int > vv(5, 1);时，因为构造函数vector(size_t n, const T& val = T())的第一个数n是size_t类型，要调用只能隐式类型转换，而函数模板可以将InputIterator推导为int，两个函数参数都是int类型，无需进行隐式类型转换，那么编译器会选择更加适配的vector(InputIterator first, InputIterator last)构造函数，从而引发报错，那么怎么解决这个问题呢？

可以再写一个第一个函数参数n为int类型的构造函数：vector(int n, const T& val = T())

vector(int n, const T& val = T())
{reserve(n);for (int i = 0; i < n; i++){start[i] = val;}finish = start + n;
}

3.2 拷贝构造函数

思路很简单，先将该容器扩容到和容器v的size一样大小，再将v的数据拷贝过来即可。

vector(const vector<T>& v)
{size_t sz = v.size();reserve(sz);memcpy(start, v.start, sizeof(T) * sz);finish = start + sz;
}

注意：严格来说，将容器v的数据一个一个拷贝过来时不能使用memcpy函数，当vector容器存储的是内置类型或无需进行深拷贝的自定义类型时，可以使用memcpy函数，但是当vector存储的是需要进行深拷贝的自定义类型时，memcpy函数就不适用了，会引发一块空间被多次释放的问题。

例如：当vector存储的是string类型时，情况如下

vector存储的每一个string对象都指向自己所存储的字符串。

如果此时我们使用memcpy函数进行拷贝构造，那么拷贝构造出来的vector存储的string对象的成员变量和被拷贝的vector存储的string对象的成员变量是一模一样的，它们的_str指针都指向同一块内存空间。

当调用vector的析构函数时，从而调用string的析构函数，这样会引起同一块空间被释放多次的问题。

那么如何解决这个问题呢？
当要将vector的string拷贝过来时，应当实现深拷贝，怎样才能实现深拷贝呢？——>string的赋值运算符重载

这样就实现了深拷贝，避免了一块空间被释放多次的问题。

vector(const vector<T>& v)
{size_t sz = v.size();reserve(sz);for (size_t i = 0; i < sz; i++){start[i] = v.start[i];}finish = start + sz;
}

还有一种现代写法，复用了使用迭代器区间进行构造初始化的构造函数：

vector(const vector<T>& v)
{vector<T> tmp(v.begin(), v.end());std::swap(start, tmp.start);std::swap(finish, tmp.finish);std::swap(end_of_storage, tmp.end_of_storage);
}

我们可以实现一个交换函数：

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(const vector<T>& v)
{vector<T> tmp(v.begin(), v.end());swap(tmp);
}

3.3 赋值运算符重载

vector<T>& operator=(vector<T> v) //调用拷贝构造函数构造出v对象
{swap(v);//交换两个对象return *this; //支持连续赋值
}

注意要使用传值传参，编译器会间接调用拷贝构造函数构造出v对象，然后将该对象与v交换即可，为了支持连续赋值，最后返回该对象，编译器在函数调用结束时会自动调用v的析构函数，将v释放掉。

3.4 析构函数

~vector()
{if (start) { //先判断start为不为空，如果不为空则释放空间，否则无需进行操作delete[] start;}start = finish = end_of_storage = nullptr;
}

析构前先判断start是否为空，如果不为空，则释放指向的空间，否则就无需释放，最后将三个指针start,finish,end_of_storage都指向空即可。

四. iterator迭代器

typedef T* iterator;
typedef const T* const_iterator;

vector迭代器就是原生指针T*，begin函数返回容器第一个元素的地址，即start；end函数返回容器最后一个元素的下一个地址，即finish。

注意：const对象的begin和end函数要用const修饰this指针指向的内容，因为const对象不允许被修改。

iterator begin()
{return start;
}
iterator end()
{return finish;
}
const_iterator begin() const
{return start;
}
const_iterator end() const
{return finish;
}

测试：

void Test()
{MyVector::vector<int> v = { 1,2,3,4,5,6 };MyVector::vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;const MyVector::vector<int> v1 = { 1,3,5,7,9 };MyVector::vector<int>::const_iterator it1 = v1.begin();while (it1 != v1.end()){cout << *it1 << " ";it1++;}
}

因为实现了迭代器，所以支持使用范围for去遍历vector

void Test()
{MyVector::vector<int> v = { 1,2,3,4,5,6 };for (auto& e : v){cout << e << " ";}cout << endl;const MyVector::vector<int> v1 = { 1,3,5,7,9 };for (auto& e : v1){cout << e << " ";}
}

五. operator[]访问函数

T& operator[](size_t i)
{assert(i < size()); //检查下标是否合法return start[i];
}
const T& operator[](size_t i) const
{assert(i < size()); //检查下标是否合法return start[i];
}

注意：不要忘了重载一个适用于const对象的operator[]函数，因为const对象只允许读，不允许修改。

六. 修改容器内容的相关函数

6.1 push_back

尾插前先判断容器是否已满，如果满了就先扩容再尾插，如果没满直接尾插即可，最后不要忘了将finish向后移一位。

void push_back(const T& x)
{if (finish == end_of_storage) {reserve(capacity() == 0 ? 4 : 2 * capacity());}*finish = x;finish++;
}

测试：

void Test()
{MyVector::vector<string> v;v.push_back("hello world");v.push_back("hello world");v.push_back("hello world");v.push_back("hello world");for (auto& e : v){cout << e << endl;}
}

运行后感觉是没什么问题，如果此时我再尾插一个相同的数据，会发生什么呢？

void Test()
{MyVector::vector<string> v;v.push_back("hello world");v.push_back("hello world");v.push_back("hello world");v.push_back("hello world");v.push_back("hello world"); //再尾插一个相同的数据for (auto& e : v){cout << e << endl;}
}

可以看到，程序崩溃了，为什么会这样呢？

容器里有四个string对象不会报错，再尾插一个就报错了，那么问题应该是出现在了扩容函数上：

void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n]; //开辟新空间if (start) {memcpy(tmp, start, sizeof(T) * oldsize); //拷贝数据}delete[] start; //释放旧空间start = tmp;finish = start + oldsize;end_of_storage = start + n;}
}

可以看到，reserve函数里拷贝数据的方式用的是memcpy函数，也就是浅拷贝（一个字节一个字节地拷贝），但是string是自定义类型，之前提到过，string实现的是深拷贝，所以memcpy函数在这里就不适用了，应当使用string的赋值运算符重载函数。

void reserve(size_t n)
{if (n > capacity()){size_t oldsize = size();T* tmp = new T[n]; //开辟新空间if (start) {//memcpy(tmp, start, sizeof(T) * oldsize); //拷贝数据for (size_t i = 0; i < oldsize; i++){tmp[i] = start[i]; //深拷贝}}delete[] start; //释放旧空间start = tmp;finish = start + oldsize;end_of_storage = start + n;}
}

再进行测试就没问题了。

6.2 pop_back()

尾删前先判断容器是否为空，如果为空则做断言处理，不为空则将finish指针向前移动一位即可。

void pop_back()
{assert(!empty()); //判断容器是否为空，为空则断言finish--; //将finish指针向前移一位
}

测试：

void Test()
{MyVector::vector<int> v = { 1,2,3,4 };for (auto& e : v){cout << e << " ";}cout << endl;while (!v.empty()){v.pop_back();for (auto& e : v){cout << e << " ";}cout << endl;}
}

6.3 insert

在pos迭代器的指定位置插入数据x，在插入数据之前先判断是否需要扩容，在pos以及之后的数据向后移动一位，注意是从后往前的顺序，最后在pos位置插入数据x，还有不要忘了将finish向后移动一位，使有效数据个数加一即可。

void insert(iterator pos, const T& x)
{assert(pos >= begin() && pos <= end()); //检查迭代器pos是否合法if (finish == end_of_storage) {//因为要扩容，旧空间会被释放掉，pos迭代器会失效，所以要更新pos迭代器size_t oldsize = pos - start; //记录pos和start之间的长度reserve(capacity() == 0 ? 4 : 2 * capacity()); //扩容pos = start + oldsize; //将pos指向新空间的指定位置}//将pos以及之后的数据向后移动一位iterator it = finish;while (it > pos){*it = *(it - 1);it--;}*pos = x; //更新数据finish++; //finish向后移动一位，有效数据加一
}

测试：

void Test()
{MyVector::vector<int> v = { 1,2,3,4,5,6 };v.insert(v.begin() + 6, 7);v.insert(v.begin() + 2, 8);for (auto& e : v){cout << e << " ";}cout << endl;
}

6.4 erase

将迭代器pos位置的数据删除，首先检查容器是否为空和pos迭代器是否在[start,finish)区间内，如果有一项不符合就做断言处理，删除数据时将pos之后的数据向前移动一位即可（把pos位置的数据覆盖掉），这里注意是从前往后的顺序。

iterator erase(iterator pos)
{assert(!empty()); //检查容器是否为空assert(pos >= start && pos < finish); //检查迭代器pos是否合法//将pos之后的数据向前移动一位iterator it = pos + 1;while (it < finish){*(it - 1) = *it;it++;}finish--; //finish向前移动一位，有效数据减一return pos; //返回被删除数据的下一个数据的迭代器
}

测试：

void Test()
{MyVector::vector<int> v = { 1,2,2,3,4,5,6,7,8 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0) {//v.erase(it)之后it迭代器就失效了，所以要让it指向被删除数据位置的下一个迭代器it = v.erase(it);}else {it++;}}for (auto& e : v){cout << e << " ";}cout << endl;
}

6.5 clear

将容器内存储的数据清空。

void clear()
{finish = start;
}

测试：

void Test()
{MyVector::vector<int> v = { 1,2,3,4,5,6 };for (auto& e : v){cout << e << " ";}cout << endl;v.clear();for (auto& e : v){cout << e << " ";}cout << endl;
}

七. 源代码

vector.h文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
//用命名空间MyVector封装vector，避免与std库的vector冲突
namespace MyVector
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;size_t size() const{return finish - start; //返回容器中有效数据的个数}size_t capacity() const{return end_of_storage - start; //返回容器的最大容量}void reserve(size_t n){if (n > capacity()){size_t oldsize = size();T* tmp = new T[n]; //开辟新空间if (start) {//memcpy(tmp, start, sizeof(T) * oldsize); //拷贝数据for (size_t i = 0; i < oldsize; i++){tmp[i] = start[i]; //深拷贝}}delete[] start; //释放旧空间start = tmp;finish = start + oldsize;end_of_storage = start + n;}}void resize(size_t n, const T& val = T()){if (n < size()){finish = start + n;}else{reserve(n); //检查是否需要扩容while (finish < start + n){*finish = val;finish++;}}}bool empty() const{return start == finish;}iterator begin(){return start;}iterator end(){return finish;}const_iterator begin() const{return start;}const_iterator end() const{return finish;}vector():start(nullptr),finish(nullptr),end_of_storage(nullptr){}vector(size_t n, const T& val = T()){reserve(n);for (size_t i = 0; i < n; i++){start[i] = val;}finish = start + n;}vector(int n, const T& val = T()){reserve(n);for (int i = 0; i < n; i++){start[i] = val;}finish = start + n;}vector(initializer_list<T> il){reserve(il.size());size_t i = 0;for (auto& x : il){start[i++] = x;}finish = start + i; //不要忘记修改finish}template<class InputIterator>vector(InputIterator first, InputIterator last) //左闭右开{reserve(last - first);size_t i = 0;while (first != last){start[i++] = *first;first++;}finish = start + i;}/*vector(const vector<T>& v){size_t sz = v.size();reserve(sz);memcpy(start, v.start, sizeof(T) * sz);finish = start + sz;}*//*vector(const vector<T>& v){size_t sz = v.size();reserve(sz);for (size_t i = 0; i < sz; i++){start[i] = v.start[i];}finish = start + sz;}*/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(const vector<T>& v){vector<T> tmp(v.begin(), v.end());swap(tmp);}vector<T>& operator=(vector<T> v) //调用拷贝构造函数构造出v对象{swap(v);//交换两个对象return *this; //支持连续赋值}~vector(){if (start) { //先判断start为不为空，如果不为空则释放空间，否则无需进行操作delete[] start;}start = finish = end_of_storage = nullptr;}T& operator[](size_t i){assert(i < size()); //检查下标是否合法return start[i];}const T& operator[](size_t i) const{assert(i < size()); //检查下标是否合法return start[i];}void push_back(const T& x){if (finish == end_of_storage) {reserve(capacity() == 0 ? 4 : 2 * capacity());}*finish = x;finish++;}void pop_back(){assert(!empty()); //判断容器是否为空，为空则断言finish--; //将finish指针向前移一位}void insert(iterator pos, const T& x){assert(pos >= begin() && pos <= end()); //检查迭代器pos是否合法if (finish == end_of_storage) {//因为要扩容，旧空间会被释放掉，pos迭代器会失效，所以要更新pos迭代器size_t oldsize = pos - start; //记录pos和start之间的长度reserve(capacity() == 0 ? 4 : 2 * capacity()); //扩容pos = start + oldsize; //将pos指向新空间的指定位置}//将pos以及之后的数据向后移动一位iterator it = finish;while (it > pos){*it = *(it - 1);it--;}*pos = x; //更新数据finish++; //finish向后移动一位，有效数据加一}iterator erase(iterator pos){assert(!empty()); //检查容器是否为空assert(pos >= start && pos < finish); //检查迭代器pos是否合法//将pos之后的数据向前移动一位iterator it = pos + 1;while (it < finish){*(it - 1) = *it;it++;}finish--; //finish向前移动一位，有效数据减一return pos; //返回被删除数据的下一个数据的迭代器}void clear(){finish = start;}private:iterator start; //指向数据块的开始iterator finish; //指向有效数据的末尾iterator end_of_storage; //指向存储容量的末尾};
}

END

对以上内容有异议或者需要补充的，欢迎大家来讨论！