【C++】vector类的模拟实现

✨ Blog’s 主页: 白乐天_ξ( ✿＞◡❛)
🌈 个人Motto：他强任他强，清风拂山冈！
🔥 所属专栏：C++深入学习笔记
💫 欢迎来到我的学习笔记！

本篇文章参考博客：【C++】透过STL源码深度剖析及模拟实现vector-CSDN博客

一、框架建立

注意：模板是不能分离到两个文件的，会出现链接错误！

在上一篇文章【链接：】我们就已经知道了迭代器的原貌就是原生指针类型，因此我们也将_start、_finish、_end_of_storage定义成了三个迭代器类型。

// 定义一个类域
namespace Harper
{template<class T>class vector {// typedef重定义迭代器：typedef T* iterator;typedef const T* const_iterator;// 主要的接口函数：// ...private:// 主要成员函数：iteartor _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}

二、迭代器

迭代器我们这里实现的是const版本和非const版本的，反向版本的迭代器比较复杂，在这里就不实现了。

// 普通对象
iterator begin()
{return _start;
}
iterator end()
{return _finish;// 这里的end是指数据结束位置，而_end_of_storage是指空间结束位置		}
}// const对象
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}

三、容量

3.1 size、capacity

容量相关接口有size()、capacity()。

// 容量
size_t size()// 数据开始到结束的大小（总长）
{return _finish - _start;// ???
}
size_t capacity()
{return _end_of_storage - _start;// ???
}

画图示意：

• size就相当于这个容器的数据个数，即_finish和 _start两个迭代器之间的距离。在此之前我们已经知道迭代器的底层就是指针，计算两个指针之间的数据个数只需要两个指针相减即可。
• capacity表示整个容器的容量，即_end_of_storage - _start。

3.2 reserve

• 首先在reserve函数中传入一个size_t类型的参数n，函数开始进行判断：如果传入的n值大于当前的容量（通过capacity()函数获取 ），才会执行扩容逻辑。
• 在扩容逻辑内部，定义了一个类型为T*的临时指针tmp，使用new T[n]根据类型参数T开辟新的空间。如果原空间的起始指针_start不为空，就使用memcpy函数将元空间的数据（从start开始，拷贝size()个T类型大小的数据）拷贝到新空间tmp中，然后释放原空间（delete[] _start）。
• 最后更新成员变量，将_start指向新空间tmp，_finish更新为_start + size()。

// 扩容
void reserve(size_t n)
{if (n > capacity()){T* tmp = new T[n];// 开辟新空间给临时指针tmpif (_start)// _start不为空时{// 拷贝数据：从memcpy开始，拷贝size()个数据memcpy(tmp, _start, sizeof(T) * size());// 拷贝的数据个数？？？？？？？delete[] _start;// 释放旧空间}_start = tmp;// 指向新空间_finish = _start + size();_end_of_storage = _start + n;}
}

但是这段代码还存在很多的漏洞！主要是下面的两个方面：

1. 内存管理方面

   • 浅拷贝与内存泄漏

memcpy(tmp, _start, sizeof(T) * size());和delete[] _start;

• 如果T是复杂对象（如包含指针成员），memcpy执行浅拷贝，只复制指针值。例如，T是一个包含动态分配数组指针的类。
• 假设T类有一个int*成员指向动态分配的整数数组。当使用memcpy拷贝时，只是复制了这个指针的值，新对象和原对象的这个指针成员会指向同一块内存。
• 然后执行delete[] _start释放原对象内存，新对象中的指针就成为悬空指针。后续使用这个悬空指针会导致未定义行为，并且原对象管理的数组内存被释放，新对象无法正确管理，造成内存泄漏。

• 异常安全

T* tmp = new T[n];

• 当new T[n]分配内存失败（如系统内存不足），函数没有处理这种情况。
• 若内存分配失败，函数会直接抛出异常。如果之前已经执行了if (_start)中的部分代码（如memcpy），原空间_start的状态已被改变，会导致数据不一致和潜在资源泄漏。

2. 逻辑方面

   • size()函数调用

memcpy(tmp, _start, sizeof(T) * size());

• 在memcpy操作中使用size()确定拷贝字节数。
• 若size()依赖内部状态（如_finish和_start关系），在reserve函数改变容器内部结构时（如重新赋值_start之前）调用size()可能得到错误结果。

• 成员变量更新（空指针异常）

_finish = _start + size();

调试可以发现，_finish的出现了问题，值为0X0000000，那么出错的地方应是在它的前面执行的代码上。调试进入扩容就可以将问题锁定在_finish = _start + size();这一句代码上。

• 在更新_finish时，_finish = _start + size();可能不正确。
• 因为size()结果在扩容前后含义或计算方式可能改变，扩容后size()可能未正确更新，导致_finish计算错误，影响后续操作（如push_back依赖_finish的逻辑）。
• 说明：之前我们使用_finish - _start来计算size()，执行这句话的时候start已经发生变化了，因为我们开辟了一块新空间，但是这是_finish的值还是醉意开始的nullptr，那么size()计算出来的大小即为-_start，此时再和_start去做一个结合，抵消了就是0。

开始进行修改：

1. _finish的修改更新

• 解决办法一：更新_finish：使用新开辟的空间tmp进行更新，在用tmp去更新_start，这样就不会出现问题了。

_finish = tmp + size();
_start = tmp;
_end_of_storage = _start + n;

• 解决办法二：我们可以在每次没开始扩容之前我们都可以去事先保存一下这个 size()，后面的更新顺序就不需要发生变动了，在加的时候加上sz即可。

if (n > capacity())
{// 先保存一下原先的size()size_t sz = size();T* tmp = new T[n];		// 开一块新空间if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;
}

2. memcpy的修改

memcpy(tmp, _start, sizeof(T) * size());

我们此前已经知道在VS下对于每个string对象的大小都是固定的28Byte，即使是通过不同的构造形式构造出来的对象也是一样的。

在这里就发生了一个浅拷贝问题，导致delete[] _start处发生了一个并发修改问题。

在扩容的时候，我们去开辟了一块新的空间，使用memcpy()函数将数据原封不动地拷贝到另一块空间，再去做一个扩容。因为这个memcpy()原封不动拷贝的问题，就使得新空间和旧空间虽然是两块独立的空间，但是呢每个对象中的_str都和另一个对象指向了那一块同样的空间。

在接下来执行这句代码时，就会先去调用当前对象的析构函数将每一块空间中的内容先清理掉，然后再去调用delete释放掉整块空间。因为没量过对象所指向的空间都是同一块的，是所以在释放的时候就会造成同时修改的问题。

delete[] _start;

总结：vector是深拷贝，但是vector空间上存的对象是string的数组，使用memcpy()导致string对象的浅拷贝。

解决办法：换一个拷贝逻辑即可，不用memcpy了，而是使用下面这种方式来拷贝：

for (size_t i = 0; i < size(); i++)
{tmp[i] = _start[i];
}

下面就是完整的实现：

void reserve(size_t n)
{if (n > capacity()){// 先保存一下原先的size()size_t sz = size();T* tmp = new T[n];// 开一块新空间if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}

3.3 push_back接口

• 在push_back函数中，接受一个const T&类型的参数x。首先判断_finish是否等于_end_of_storage，如果相等，表示当前空间已满。
• 若空间已满，计算新的容量newCapacity，如果当前容量为 0，则新容量设为 4，否则新容量为当前容量的 2 倍。然后调用reserve函数进行扩容。
• 最后将参数x赋值给_finish指向的位置，并将_finish指针后移一位。

void push_back(const T& x)
{if (_finish == _end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;_finish++;
}

push_back函数漏洞：

• 与reserve交互（相关代码行：reserve(newCapacity);、*_finish = x;和_finish++;）
  • 当push_back调用reserve扩容时，如果reserve因内存分配失败等未正确完成扩容。
  • push_back没有错误处理，继续执行*_finish = x;和_finish++;操作，可能导致访问无效内存或破坏容器内部状态。

3.4 修改后的代码（MyContainer类）

#include <iostream>
#include <cstring>// 假设这是一个简单的模板类表示容器
template <typename T>
class MyContainer 
{
private:T* _start;T* _finish;T* _end_of_storage;// 辅助函数，用于正确地拷贝对象void copyObjects(T* dest, T* src, size_t num) {for (size_t i = 0; i < num; ++i) {new(dest + i) T(src[i]); // 使用placement new来正确构造对象}}
public:// 构造函数MyContainer() : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}// 析构函数~MyContainer() {clear();}// 释放容器中的所有对象并释放内存void clear() 	{if (_start) {T* cur = _start;T* end = _finish;for (; cur!= end; ++cur) {cur->~T(); // 调用对象的析构函数}delete[] _start;_start = _finish = _end_of_storage = nullptr;}}size_t size() const {return static_cast<size_t>(_finish - _start);}size_t capacity() const {return static_cast<size_t>(_end_of_storage - _start);}void reserve(size_t n){if (n > capacity()) {T* tmp = nullptr;try {tmp = new T[n];} catch (...) 	{// 如果内存分配失败，直接返回，不改变容器状态return;}size_t oldSize = size();copyObjects(tmp, _start, oldSize);clear();_start = tmp;_finish = _start + oldSize;_end_of_storage = _start + n;}}void push_back(const T& x) {if (_finish == _end_of_storage) {size_t newCapacity = capacity() == 0? 4 : capacity() * 2;reserve(newCapacity);}if (_start) {new(_finish) T(x);_finish++;}}
};

1. reserve函数的修改

   • 内存管理方面
     • 针对浅拷贝和内存泄漏问题，不再使用memcpy，而是使用copyObjects函数。这个函数通过placement new逐个正确地构造新对象，避免了浅拷贝。
     • 对于异常安全问题，使用try - catch块来捕获new T[n]可能抛出的异常。如果内存分配失败，函数直接返回，不改变容器的当前状态。
   • 逻辑错误方面
     • 在计算要拷贝的元素数量时，先保存size()的结果（size_t oldSize = size();），避免了在容器结构改变过程中size()结果可能出现的错误。在更新_finish时，使用保存的旧大小来正确设置新的_finish位置。

2. push_back函数的修改

   • 在调用reserve后，添加了if (_start)的判断，确保_start不为空（即reserve成功执行）后再进行push_back的操作。这避免了在reserve失败时执行可能导致错误的操作。

// 改成一层模板，实例化，编译器自动推导传入参数的类型
template<class T>
void print_vector(const vector<T>& v)// const对象的迭代器，不能调用非const的成员函数
{// 打印输出v的内容vector<int>::const_iterator it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v)// 支持了迭代器就支持了范围for{cout << e << " ";}
}

3.5 resize接口

1. 先分类情况：

   • n < _finish的情况

     • 当n小于当前容器中的元素个数（即_finish与_start之间的距离）时，直接将_finish指针移动到_start + n的位置，这意味着截断容器，使容器中的元素数量变为n。

   • n > _finish && n <= _end_of_storage和n > _end_of_storage的情况

     • 这两种情况进行了合并处理。首先调用reserve函数检查是否需要扩容。如果n大于当前的_end_of_storage（容器容量），reserve函数会进行扩容操作以满足新的容量需求。
     • 在确保容量足够后（如果需要扩容已经完成扩容），通过循环将val（默认值或者传入的值）赋给从_finish开始到_start + n之间的元素，同时移动_finish指针，直到_finish到达_start + n的位置，从而将容器的元素数量调整为n。

void resize(size_t n, const T& val = T())
{if (n < size()){_finish = _start + n;}else{// 先使用reserve()去检查一下是否需要扩容reserve(n);while (_finish != _start + n){*_finish = val;_finish++;}}
}

2. 关于默认参数T()

const T& val = T()

功能解释：

• 在resize函数的参数const T& val = T()中，T()是一个默认缺省参数。由于形参val的类型是模板参数类型，采用自动推导形式。
• T()在这里是一个匿名对象，它根据T的类型生成相应的默认值。不能简单地给0作为默认值，因为T的类型不一定是整型，通过T()可以根据不同的类型生成合适的默认值。

四、元素访问

下标 +[]形式：

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

五、修改操作

5.1 push_back接口

• 扩容在VS编译器下呈现1.5倍的增长趋势，但是在g++编译器下是2倍扩容趋势，在这里扩容使用reserve来实现。

void push_back(const T& x)
{if (_finish == _end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;_finish++;
}

5.2 insert接口

在pos位置插入元素x。

void insert(iterator pos, const T& x)

• 断言检查：
  • 首先assert断言pos为合法的迭代器，即pos在_start和_finish之间（包含两端）。
  • 这是因为pos是指向容器内部有效空间的迭代器（类似于地址），不同于string类中基于无符号整数的我只表示，这里不可能为0。
• 扩容逻辑：
  • 如果容器已满（_finish == _end_of_storage），则复用push_back中的扩容逻辑。
  • 按照规则（容量为 0 时新容量设为 4，否则为当前容量的 2 倍）计算新容量并调用reserve函数进行扩容。
• 数据挪动与插入：
  • 确定要挪动数据的范围，将_finish - 1作为末尾迭代器end。通过循环从后往前将元素依次后移一位（*(end + 1) = *end），直到end到达pos的位置。这样做可以避免覆盖数据。
  • 然后将元素x插入到pos位置（*pos = x），最后将_finish指针向后移动一位，表示容器中的元素数量增加了一个。

void insert(iterator pos, const T& x)
{assert(pos >= _start && pos <= _finish);// 1.首先考虑扩容逻辑if (_finish == _end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}// 2.挪动数据iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;
}

那么在push_back中就可以复用insert接口了。

void push_back(const T& x)
{/*if (_finish == _end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish = x;_finish++;*/insert(end(), x);
}

六、默认成员函数

6.1 构造函数

6.1.1 基于resize复用的有参构造函数

• 自定义vector类中的有参构造函数vector(size_t n, const T& val = T())通过复用resize函数来初始化容器。例如创建Harper::vector<int> v(10, 0);时，构造函数内部调用v.resize(10, 0)。

// 有参构造
vector(size_t n, const T& val = T())
{resize(n, val);
}

• 对于vector类中的_start、_finish、_end_of_storage这三个私有成员变量，它们在定义时被初始化为nullptr，避免内置类型未初始化的问题。

6.1.2 基于迭代器区间的构造函数

• 原理与实现细节

  • 下面的函数是通过迭代器区间初始化vector的构造函数原型。

template<class InputIterator> vector(InputIterator first, InputIterator last)

• 举例：

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

• 可以用已存在的vector对象结合迭代器区间初始化新的vector对象。

Harper::vector<int> v2(v.begin(), v.end());

• 也可用于string对象迭代器或数组指针的初始化。

string s("abcdef"); 
Harper::vector<int> v2(s.begin(), s.end());int a[] = {1, 2, 3, 4}; 
Harper::vector<int> v2(a, a + 4);

6.1.3 构造函数调用歧义及解决

• 当执行bit::vector<int> v5(10, 1);时，会出现 “非法的间接寻址” 问题。这是因为模板参数自动类型推导时，传入的10和1是int类型，而原有的有参构造函数第一个形参为size_t类型，不会优先匹配该构造函数，而是可能错误匹配到迭代器区间构造函数（其参数为模板类型，匹配度更高）。
• 通过重载有参构造函数，新增vector(int n, const T& val = T())版本：

vector(int n, const T& val = T()) 
{resize(n, val);
}

• 这样就与原vector(size_t n, const T& val = T())形成重载关系，避免了调用歧义。同时，若要调用size_t类型的构造函数，可在参数后加u，如bit::vector<int> v6(10u, 6);。

6.2 拷贝构造函数

• 最初的拷贝构造函数vector(vector<int>& v)实现中存在浅拷贝问题，在调试时可发现。
• 最初的代码如下：

vector(vector<int>& v) 
{_start = new T[v.capacity()];memcpy(tmp, v._start, sizeof(T) * v.size());_finish = tmp + v.size();_end_of_storage = tmp + v.capacity();
}

• 当vector对象存储string数组时，memcpy会导致浅拷贝问题。
• 正确的深拷贝实现方式是逐个拷贝元素：

vector(vector<T>& v) 
{_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++) {_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}

• 也可复用reserve和push_back接口实现拷贝构造函数：

vector(vector<int>& v) 
{// 根据v的capacity()去开出对应的空间reserve(v.capacity());for (size_t i = 0; i < v.size(); i++) {push_back(v[i]);}
}

6.3 赋值重载函数

• 赋值重载函数const vector<T>& operator=(vector<T> v)利用swap接口实现。通过传值传参，先调用拷贝构造函数创建临时对象，然后用swap交换临时对象和当前对象内容。临时对象出作用域后自动销毁。以下是代码：

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

• 在调试时可看到调用赋值重载函数前会先调用拷贝构造函数。

6.4 析构函数

• 析构函数~vector()用于释放容器占用的空间，将资源归还给操作系统。代码如下：

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