模拟实现vector
- 1.vector基本概念
- 2.vector()默认构造函数
- 3.size()成员函数+迭代器
- 4.capacity()成员函数
- 5.empty()成员函数
- 6.reverse()成员函数
- 7.push_back()成员函数
- 8.pop_back()成员函数
- 9.operator[ ]成员函数
- 10.resize()成员函数
- 11.insert()成员函数
- 12.erase()成员函数
- 13.swap()成员函数
- 14.operator=()赋值重载函数
- 15.vector其他的构造函数
- 16.vector拷贝构造函数
- 17.~vector()析构函数
- 18.vector模拟实现完整代码
🌟🌟hello，各位读者大大们你们好呀🌟🌟
🚀🚀系列专栏：【C++的学习】
📝📝本篇内容：vector基本概念；vector()默认构造函数；size()成员函数+迭代器；capacity()成员函数；empty()成员函数；reverse()成员函数；push_back()成员函数；pop_back()成员函数；operator[ ]成员函数；resize()成员函数；insert()成员函数；erase()成员函数；swap()成员函数；operator=赋值重载函数；vector其他构造函数；vector拷贝构造函数；~vector()析构函数；vector模拟实现完整代码
⬆⬆⬆⬆上一篇：C++STL之vector
💖💖作者简介：轩情吖，请多多指教(> •̀֊•́ ) ̖́-
1.vector基本概念
上一节我们讲了vector的概念以及常用的接口，这一节我们讲一下它的实现，它的底层其实就只有三个成员变量：_start,_finish,_end_of_storage。_start指向目前使用空间的头，_finish指向目前使用空间的尾，_end_of_storage指向目前可用空间的尾。通过这个三个指向就可以完成我们vector的实现，可以看一下下面的图来简单理解一下
//基本结构
#include <iostream>
using namespace std;
namespace lnb
{
template<class T>
class vector
{
public:
typedef T* iterator;//迭代器类型，指针本身就可以做迭代器类型
private:
iterator _start;//指向目前使用空间的头
iterator _finish;//指向目前使用空间的尾
iterator _end_of_storage;//指向目前可用空间的尾
};
}
2.vector()默认构造函数
vector()//默认构造函数
:_start(nullptr),//全部设为nullptr指针
_finish(nullptr),
_end_of_storage(nullptr)
{}
这是默认的构造函数，不需要传任何参数，把指针全部设为nullptr即可。后续的其他构造函数，建立在其他的成员函数上写会更方便，先继续往后看
3.size()成员函数+迭代器
iterator begin()//迭代器的开始
{
return _start;
}
iterator end()//迭代器的结束
{
return _finish;
}
size_t size()const//vector的大小
{
return end() - begin();
}
这边在实现size()的基础上顺便把迭代器的开始和结束也一起实现了，这样再写size()可以看上去更加的简便
我们的迭代器是前闭后开的，也就是整个实际范围从begin()开始，直到end()-1，迭代器end()所指的是“最后一个元素的下一个位置”
4.capacity()成员函数
typedef const T* const_iterator;
const_iterator begin()const//针对于const类型的对象
{
return _start;
}
const_iterator end()const//针对于const类型的对象
{
return _finish;
}
size_t capacity()const//vector容量大小
{
return _end_of_storage - begin();
}
capacity()也是同样的道理，同时也把const迭代器给一起实现了，这边主要是capacity()被const类型修饰了，那么调用的begin()就需要也是被const修饰的，capacity()理解见下图
5.empty()成员函数
bool empty()const//判空
{
return begin() == end();
}
这个函数是用来判断vector是否为空的，我们直接使用了_start和_finish，因为当它们都为nullptr空时才会相同
6.reverse()成员函数
void reverse(size_t n)//预留空间，提前扩容用的
{
if (n > capacity())//保证n是大于现有空间的
{
size_t old_size = size();
//1.先开辟新空间
T* new_start = new T[n];//这边暂时不处理异常
//2.将数据拷贝到新空间去
for (int i = 0; i < size(); i++)
{
//这边不能使用memcpy这种直接内存拷贝的函数
new_start[i] = _start[i];
}
//3.释放空间
delete[] _start;
//4.修改指向
_start = new_start;
_finish = new_start + old_size;
_end_of_storage = new_start + n;
}
}
reverse主要是为了提前预留空间，来防止后续添加元素造成的多次扩容从而效率低下，具体的流程：先开辟新的空间→拷贝旧的数据到新空间→释放旧空间→修改指向。其中最需要注意的是拷贝元素的过程，不能直接使用内存拷贝函数，我们看下面的图来理解一下
在我们的代码中，如果通过memcpy拷贝完后，需要把旧的空间给释放掉，那么此时我们新的new_start中的string对象中的_str就是野指针，它指向的是一片已经释放的空间
因此我们需要使用循环赋值才能改变这个情况，当使用循环赋值后，会自动调用string的赋值重载函数，这样str指向的空间就不是同一个了。_start即使是释放掉旧的空间，那它也只是释放的是自己的string元素
7.push_back()成员函数
void push_back(const T& val)//尾插
{
if (_finish==_end_of_storage)
{
//我们扩容以2倍增长
reverse(capacity() == 0 ? 2 : capacity() * 2);
}
*_finish = val;
_finish++;
}
我们的尾插也非常的方便，只不过是要注意一下空间够不够，不够就需要进行扩容
8.pop_back()成员函数
我们先来看一下下面的代码，尾删这样写对吗
//!!!error code
void pop_back()//尾删
{
assert(!empty());//保证有数据
_finish--;
}
对于内置类型确实没有问题，但是对于string这种就不行了，会造成内存泄露，因此我们需要将其进行释放
void pop_back()//尾删
{
assert(!empty());//保证有数据
_finish->~T();//需要调用对应元素的析构，不然会造成内存泄露
_finish--;
}
9.operator[ ]成员函数
T& operator[](size_t n)//像数组一样去访问
{
assert(n < size());
return _start[n];
}
//针对const类型的vector
const T& operator[](size_t n)const
{
assert(n < size());
return _start[n];
}
10.resize()成员函数
void resize(size_t n,const T& val=T())
{
//要分三种情况,真正有作用的就两种情况
if (n >size())
{
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
else if(n<size())
{
size_t distance = size()-n;//计算出多了多少元素
for (int i = 0; i < distance; i++)
{
_finish->~T();//这边要记得释放，不然对于自定义类型会内存泄露
_finish--;
}
}
else
{
return;
}
}
我们的resize要分三种情况，分别是大于等于小于n，大于n的需要减少vector的大小；小于n的需要增大vector的大小，用val来填充；而等于n什么都不用做
11.insert()成员函数
iterator insert(iterator position, const T& val)//插入
{
//迭代器失效问题，因此需要保存迭代器位置
size_t pos = position-_start;
//1.先查看是否需要扩容
if (_finish == _end_of_storage)
{
reverse(capacity() == 0 ? 2 : capacity() * 2);
position= _start + pos;//扩容后position不在原来的空间了
}
//2.先进行元素的移动，将插入位置留出
iterator end = _finish-1;
while (end >= position)
{
*(end + 1) = *end;
end--;
}
//3.放入元素
*position = val;
_finish++;
return position;
}
我们可以看一下下图来理解一下它整体的逻辑以及移动的过程
12.erase()成员函数
//删除
iterator erase(iterator position)
{
iterator begin = position+1;
while (begin < end())
{
*(begin - 1) = *begin;
begin++;
}
_finish--;
return position;
}
这个函数也很简单，只需要往前移动元素覆盖即可
13.swap()成员函数
void swap(vector<T>& v)//交换两个对象
{
//调用库中的swap来进行交换
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
通过调用库中的swap函数来交换对象中的三个指针，这样就做的效率非常高，只进行交换成员变量即可完成对象之间的交换，std::swap()如下
14.operator=()赋值重载函数
//赋值重载--一个新奇的写法如下
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
可以看到我们的赋值重载写的非常的简洁，注意参数没有使用&，它其实是利用了被拷贝的对象，对其进行了拷贝构造，在函数体内又进行了交换，这样我们的目的就达成了，而被交换后的对象v会在出函数前析构，就把原来要拷贝的对象的资源释放掉了
15.vector其他的构造函数
//T()是匿名对象，对于int这种内置类型，值为0
vector(size_t n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
for(int i=0;i<n;i++)
{
push_back(val);
}
}
//通过迭代器构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);//直接调用其他函数来完成功能
first++;
}
}
这里主要是讲一下第二个构造函数，可以发现它本质上是个模板函数，我们的vector是个模板类，在我们的模板类里面可以套模板函数的
16.vector拷贝构造函数
//拷贝构造函数
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
//1.先开辟新空间
_start = new T[v.capacity()];
//2.拷贝数据，和reverse一样，不能使用memcpy
for (int i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
//3.修改指向
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
//拷贝构造的另一种写法
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
vector<T> tmp(v.begin(),v.end());
swap(tmp);
}
在上面的代码中一共提供了两种写法，第二种更加简便，它的道理和operator=中的一样。第一种写法就是最老的写法，通过开辟空间，拷贝数据，修改指向来完成拷贝构造，但是如果一不注意使用内存拷贝就会造成浅拷贝，因此第一种写法需要注意一下细节,它和reverse中的情况其实差不多，我们可以再来讲一下
假设我们vector的元素是一个string，又或者是一个vector呢？我们来看图理解一下，当两个vector中的string中的_str指向相同的空间时会发生什么呢？在析构的时候，old_vector底层会释放开辟的空间，而空间中的是string类型，也需要调用它的析构函数，在string的析构中会把_str指向的空间释放掉，到这也什么问题，但是当new_vector释放时呢，它也会需要释放_str指向的空间，但是已经释放过一次了呀，这时候又释放就会造成程序崩溃。
所以说使用memcpy这种函数来拷贝，其实本质上也是一种浅拷贝，因此我们需要使用循环赋值才能改变这个情况，当使用循环赋值后，会自动调用string的赋值重载函数，这样str指向的空间就不是同一个了。
我们的string::operator=()并不是简单的拷贝，而是会进行开辟新的空间
17.~vector()析构函数
~vector()
{
delete[] _start;
_start = _finish = _end = nullptr;
}
18.vector模拟实现完整代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cassert>
using namespace std;
namespace lnb
{
template<class T>
class vector
{
public:
typedef T* iterator;//迭代器类型，指针本身就可以做迭代器类型
typedef const T* const_iterator;
vector()//默认构造函数
:_start(nullptr),//全部设为nullptr指针
_finish(nullptr),
_end_of_storage(nullptr)
{}
iterator begin()//迭代器的开始
{
return _start;
}
iterator end()//迭代器的结束
{
return _finish;
}
const_iterator begin()const//针对于const类型的对象
{
return _start;
}
const_iterator end()const//针对于const类型的对象
{
return _finish;
}
size_t size()const//vector的大小
{
return end() - begin();
}
size_t capacity()const//vector容量大小
{
return _end_of_storage - begin();
}
bool empty()const//判空
{
return begin() == end();
}
void reverse(size_t n)//预留空间，提前扩容用的
{
if (n > capacity())//保证n是大于现有空间的
{
size_t old_size = size();
//1.先开辟新空间
T* new_start = new T[n];//这边暂时不处理异常
//2.将数据拷贝到新空间去
for (int i = 0; i < size(); i++)
{
//这边不能使用memcpy这种直接内存拷贝的函数
new_start[i] = _start[i];
}
//3.释放空间
delete[] _start;
//4.修改指向
_start = new_start;
_finish = new_start + old_size;
_end_of_storage = new_start + n;
}
}
void push_back(const T& val)//尾插
{
if (_finish == _end_of_storage)
{
//我们扩容以2倍增长
reverse(capacity() == 0 ? 2 : capacity() * 2);
}
*_finish = val;
_finish++;
}
void pop_back()//尾删
{
assert(!empty());//保证有数据
_finish--;
_finish->~T();//需要调用对应元素的析构，不然会造成内存泄露
}
T& operator[](size_t n)//像数组一样去访问
{
assert(n < size());
return _start[n];
}
//针对const类型的vector
const T& operator[](size_t n)const
{
assert(n < size());
return _start[n];
}
//拷贝构造函数
/*vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
//1.先开辟新空间
_start = new T[v.capacity()];
//2.拷贝数据，和reverse一样，不能使用memcpy
for (int i = 0; i < v.size(); i++)
{
_start[i] = v[i];
}
//3.修改指向
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}*/
//拷贝构造的另一种写法
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//T()是匿名对象，对于int这种内置类型，值为0
vector(size_t n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
//通过迭代器构造
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);//直接调用其他函数来完成功能
first++;
}
}
//赋值重载--一个新奇的写法如下
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
void swap(vector<T>& v)//交换两个对象
{
//调用库中的swap来进行交换
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
~vector()
{
delete[]_start;
_start = _finish = _end_of_storage = nullptr;
}
void resize(size_t n, const T& val = T())
{
//要分三种情况,真正有作用的就两种情况
if (n > size())
{
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
else if (n < size())
{
size_t distance = size() - n;//计算出多了多少元素
for (int i = 0; i < distance; i++)
{
_finish->~T();//这边要记得释放，不然对于自定义类型会内存泄露
_finish--;
}
}
else
{
return;
}
}
iterator insert(iterator position, const T& val)//插入
{
//迭代器失效问题，因此需要保存迭代器位置
size_t pos = position - _start;
//1.先查看是否需要扩容
if (_finish == _end_of_storage)
{
reverse(capacity() == 0 ? 2 : capacity() * 2);
position = _start + pos;//扩容后position不在原来的空间了
}
//2.先进行元素的移动，将插入位置留出
iterator end = _finish - 1;
while (end >= position)
{
*(end + 1) = *end;
end--;
}
//3.放入元素
*position = val;
_finish++;
return position;
}
//删除
iterator erase(iterator position)
{
iterator begin = position + 1;
while (begin < end())
{
*(begin - 1) = *begin;
begin++;
}
_finish--;
return position;
}
private:
iterator _start;//指向目前使用空间的头
iterator _finish;//指向目前使用空间的尾
iterator _end_of_storage;//指向目前可用空间的尾
};
}
🌸🌸模拟实现vector的知识大概就讲到这里啦，博主后续会继续更新更多C++的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪
