【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];// 开辟新空间给临时指针tmp
if (_start)// _start不为空时
{
// 拷贝数据：从memcpy开始，拷贝size()个数据
memcpy(tmp, _start, sizeof(T) * size());// 拷贝的数据个数？？？？？？？
delete[] _start;// 释放旧空间
}
_start = tmp;// 指向新空间
_finish = _start + size();
_end_of_storage = _start + n;
}
}
但是这段代码还存在很多的漏洞！主要是下面的两个方面：
-
内存管理方面
- 浅拷贝与内存泄漏
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的状态已被改变，会导致数据不一致和潜在资源泄漏。
-
逻辑方面
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。
开始进行修改：
_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;
}
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++;
}
}
};
-
reserve函数的修改- 内存管理方面
- 针对浅拷贝和内存泄漏问题，不再使用
memcpy，而是使用copyObjects函数。这个函数通过placement new逐个正确地构造新对象，避免了浅拷贝。 - 对于异常安全问题，使用
try - catch块来捕获new T[n]可能抛出的异常。如果内存分配失败，函数直接返回，不改变容器的当前状态。
- 针对浅拷贝和内存泄漏问题，不再使用
- 逻辑错误方面
- 在计算要拷贝的元素数量时，先保存
size()的结果（size_t oldSize = size();），避免了在容器结构改变过程中size()结果可能出现的错误。在更新_finish时，使用保存的旧大小来正确设置新的_finish位置。
- 在计算要拷贝的元素数量时，先保存
- 内存管理方面
-
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接口
-
先分类情况：
-
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++;
}
}
}
- 关于默认参数
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;
}
