C++初阶：适合新手的手撕vector（模拟实现vector）
上次讲了常用的接口：C++初阶：容器（Containers）vector常用接口详解
今天就来进行模拟实现啦
文章目录
- 1.基本结构与文件规划
- 2.空参构造函数（constructor)
- 4.基本函数（size(),capacity(),resize(),reserve())
- 4.增删改查(push_back,pop_back,insert,erase)
- 5.在实现Insert和erase时迭代器失效问题
- 6.重载[]
- 7. 完善构造函数
- 7.1vector (size_type n, const value_type& val = value_type());
- 7.2利用迭代器进行构造
- 7.3拷贝构造
- 8.重载=
- 9.析构函数
1.基本结构与文件规划
- vector.h头文件：包含类的全部(函数的声明与定义)
- test.cpp源文件：进行调用test函数，测试和完善功能
基本结构，先看一下源码：
namespace MyVector
{
template <class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;//先定义好迭代器
//各种函数
private:
iterator _start;
iterator _finish;
iterator _endOfStorage;
};
}
_start：指向动态数组的起始位置的指针，即第一个元素的位置。_finish：指向动态数组中最后一个元素之后的位置的指针。在这个实现中，_finish指针始终指向当前元素范围的末尾，也就是下一个要插入元素的位置。_endOfStorage：指向动态数组分配的内存空间的末尾之后的位置的指针。在这个实现中，_endOfStorage指针指向当前分配的内存空间的末尾，当需要扩充容量时，会通过比较_finish和_endOfStorage的位置来判断是否需要重新分配更大的内存空间
2.空参构造函数（constructor)
vector()
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)//直接使用初始化列表
{}
都初始化为空指针
#3.迭代器（iterator）(begin(),end())
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
进行const的重载
4.基本函数（size(),capacity(),resize(),reserve())
void reserve(size_t n)
{
if (n > capacity())
{
int old_size = size();//保存一下长度，方便后续给_finish移到新的位置
T* tmp = new T[n];
if (_start != nullptr)//vector里存东西了
{
for (size_t i = 0; i < size(); ++i)
{
tmp[i] = _start[i];//_start本质是指针
}
}
delete[] _start;
_start = tmp;
_finish = _start + old_size;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& x = T())
{
if (n > size())
{
reserve(n);//<capacity 的话，也没有进行处理
while (_finish != _start + n)
{
*_finish = x;
++_finish;
}
}
else
{
_finish = _start + n;//小于长度时，直接移动finish
}
}
size_t size()
{
return _finish - _start;
}
size_t capacity()
{
return _endOfStorage - _start;
}
reserve函数：
reserve函数用于保留至少能容纳n个元素的内存空间。如果当前的容量小于n，则会分配新的内存空间，并将原来的元素复制到新的内存空间中。- 首先，它会创建一个新的大小为
n的临时数组tmp，然后将原始数组中的元素复制到临时数组中。- 接着，释放原始数组的内存空间，将
_start指针指向新分配的内存空间，同时更新_finish和_endOfStorage的位置。
resize函数：
resize函数用于改变数组的大小，使其包含n个元素，并使用值x进行初始化。- 如果
n大于当前的大小，它会调用reserve函数以确保数组有足够的容量，然后将数组的大小增加到n，并使用值x进行初始化。- 如果
n小于当前的大小，它会直接将_finish指针移动到新的位置，从而改变数组的大小。
size函数：
size函数用于返回数组中元素的个数，即_finish和_start之间的距离。
capacity函数：
capacity函数用于返回数组的容量，即_endOfStorage和_start之间的距离
怎么来理解：const T& x = T()
实现给出各种类型的默认值，在这里为了妥协，其实内置类型也有构造函数在 C++ 中。内置类型（如 int、float、double 等）也有默认构造函数。默认构造函数对于内置类型来说，其实就是不带参数的构造函数，它会将变量初始化为默认值
T()表示创建一个类型T的临时对象，并进行值初始化。这里假设T是一个类或者结构体，那么这个语句会调用T的默认构造函数来创建一个临时对象。const T& x表示创建一个类型为T的常量引用x。这里的引用是T类型的引用，而且是常量引用，意味着x引用的对象是不可修改的。const T& x = T()将这个临时对象绑定到常量引用x上。这样做的好处是可以避免不必要的拷贝，同时也可以确保x引用的对象是不可修改的。
使用如下来测试
void test1()
{
vector<int> v;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.resize(10);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.resize(5);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
4.增删改查(push_back,pop_back,insert,erase)
void push_back(const T& x)
{
if (_finish == _endOfStorage)
{
int newcapacity = capacity() == 0 ? 2 : 2 * capacity();
reserve(newcapacity);
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(size() > 0);
--_finish;
}
iterator insert(iterator pos, const T& x)//在pos前插入
{
assert(pos < _finish&& pos >= _start);
if (_finish == _endOfStorage)
{
size_t site = pos - _start;
int newcapacity = capacity() == 0 ? 2 : 2 * (capacity());
reserve(newcapacity);
pos = _start + site;//pos到新空间的位置上
}
iterator end = _finish - 1;
while (end >= pos)//开始整体向后退
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)//删pos处
{
assert(pos < _finish&& pos >= _start);
assert(size() > 0);
//开始向前移动
iterator start = pos + 1;
while (start < _finish)
{
*(start - 1) = *start;
start++;
}
_finish--;
return pos;//返回删除的位置
}
使用test2函数看功能是否正常
void test2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);//尾插3个
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.pop_back();//尾删一个
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.insert(v.begin(), 0);//头插一个0
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.begin());//头删
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
5.在实现Insert和erase时迭代器失效问题
当使用迭代器遍历容器时，如果在遍历的过程中对容器进行了结构性的修改（例如插入、删除元素，重新分配内存等操作），可能会导致迭代器失效。迭代器失效意味着该迭代器不再指向有效的元素或容器的结尾，因此继续使用失效的迭代器可能会导致未定义行为。
迭代器失效的原因主要有以下几种：
- 插入操作：当在容器中插入元素时，可能会导致容器内部的元素发生移动或重新分配内存，这会导致原先的迭代器失效。因为插入元素后，原先的迭代器可能不再指向正确的位置。
- 删除操作：当在容器中删除元素时，可能会导致容器内部的元素发生移动，也会导致原先的迭代器失效。因为删除元素后，原先的迭代器可能指向了一个已经被删除的元素，或者指向了不正确的位置。
- 重新分配内存（扩容时）：某些容器在元素数量达到一定阈值时会进行内存的重新分配，这会导致原先的迭代器失效。因为重新分配内存后，原先的迭代器可能指向了无效的内存地址。
- 容器的清空：当对容器进行清空操作时，所有的元素都被移除，迭代器也会失效。
迭代器失效可以大致分为两类：
- 结构性变化导致的失效：这类失效包括扩容时申请了新空间、插入或删除元素导致元素位置改变等情况。在这种情况下，原先的迭代器可能会指向已经被移动或者删除的元素，或者指向了新分配的内存空间，导致迭代器失效。
- 数据变化导致的失效：这类失效包括使用了
memmove、std::copy等函数对容器内部元素进行移动或复制的情况。这些函数可能会导致容器内部的元素发生移动，导致原先的迭代器指向的位置发生变化，从而导致迭代器失效。
void test3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//删除偶数
vector<int>::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it=v.erase(it);//这里不能只是v.erase(it); 删除后
}
else
{
it++;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
在使用
erase函数删除元素后，erase函数会返回指向被删除元素之后的元素的迭代器，而不是原先被删除元素的迭代器。如果使用v.erase(it);，则会导致it迭代器失效，因为它指向的元素已经被删除，而it没有更新。因此，为了确保迭代器的有效性，需要将返回的迭代器赋值给it，以便在下一次循环中继续使用正确的迭代器。
6.重载[]
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
7. 完善构造函数
7.1vector (size_type n, const value_type& val = value_type());
vector(size_t n, const T& val= T())
{
resize(n, val);
}
vector(int n, const T& val = T())//适用于 vector<int> v(5,1)
{
resize(n, val);
}
7.2利用迭代器进行构造
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
为什么使用模版：
因为可能使用其他类型的迭代器来进行初始化
7.3拷贝构造
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endOfStorage(nullptr)//先利用初始化列表进行初始化
{
reserve(v.capacity());
for (const auto& e : v)
{
push_back(e);
}
}
8.重载=
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endOfStorage, v._endOfStorage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
注意这里的参数不是常量引用，而是按值传递的。这是因为在赋值操作符中我们会调用
swap函数，按值传递可以保证传入的参数会被复制一份，避免对原对象的修改。在函数体内，我们调用了swap函数，将当前对象和传入的对象进行内容交换，然后返回*this，即当前对象的引用。
9.析构函数
~vector()
{
delete[] _start;
_start = _finish = _endOfStorage = nullptr;
}
好啦，今天就到这里啦，感谢大家支持！！！