【C++】STL---vector的模拟实现(超级详细，万字详解)-创新互联
文章目录
前言
vector的成员属性
构造函数
size函数
cacpcity函数
begin和end函数
reserve函数
insert函数
新闻名称：【C++】STL---vector的模拟实现(超级详细，万字详解)-创新互联
网址分享：http://scyanting.com/article/dgoejj.html
- 前言
- vector的成员属性
- 构造函数
- size函数
- cacpcity函数
- begin和end函数
- reserve函数
- insert函数
- push_back函数
- []操作符重载
- 析构函数
- 拷贝构造函数
- 赋值操作符重载
- erase函数
- pop_back
- 反向迭代器
- 反向迭代器模板
- 反向迭代器的构造函数
- ++运算符重载
- - -运算符重载
- *引用操作符重载
- ！=操作符重载
- ==操作符重载
- rbegin函数
- rend函数
- ->重载
- 总结
前言
vector 是一个顺序容器，简单来说就是一个可以扩容的数组。它的数据在内存中是连续存储的。这也就意味着它支持随机访问(下标访问)，而这篇文章将会带着大家模拟实现一个vector的容器。
vector的成员属性
vector是一个顺序容器，那么我们需要给它分配空间。那么我们可以用三个迭代器来指向，_start迭代器指向第一个位置，_finish指向有效数据的下一个位置，而_endofstorage指向开辟空间大小的最后一个位置。
代码:
templateclass vector
{public:
//普通迭代器
typedef T* iterator;
//const迭代器
typedef const T* const_iterator;
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
}; 构造函数
接下来我们就要给vector初始化，这里用2种初始化方式，一种是普通初始化。而一种是迭代器区间初始化。
普通初始化：什么也不干，迭代器初始化成空指针。
迭代器区间初始化：把迭代器区间的所有值一一加到当前的vector对象种。
普通初始化代码：
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{ }迭代器区间初始化：
//迭代器区间初始化
templatevector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{while (first != last)
{ //把迭代器数据依次插入当前对象
push_back(*first);//尾部插入数据的函数，在下面实现
++first;
}
} size函数
size函数返回vector的长度，也就是已经存放的数据个数，我们直接返回_finish - _start的值即可。
size_t size()
{return _finish - _start;
}
如果是const对象，我们也要返回一个长度
size_t size()const
{return _finish - _start;
}cacpcity函数
cacpcity函数返回vector的容量，也就是能存放的数据的大个数，我们直接返回_endofstorage - _start的值即可。
size_t cacpcity()
{return _endofstorage - _start;
}如果是const对象，我们也要返回
size_t cacpcity()const
{return _endofstorage - _start;
}begin和end函数
begin 获取 迭代器开始位置，end 获取迭代器结束位置。
直接返回_start 和 _finish
iterator begin()
{ return _start;
}
iterator end()
{ return _finish;
}当我们的容器是const的时候，我们需要返回const迭代器。所以还需要对begin和end函数进行函数重载。
iterator begin()
{ return _start;
}
iterator end()
{ return _finish;
}
const_iterator begin()const
{ return _start;
}
const_iterator end()const
{ return _finish;
}
reserve函数
reserve函数是用来改变容量的，但是对于缩容我们不做处理，reserve只做增容处理。
我们可以分以下步骤:
- 开辟一块指定大小的空间(只增容)。
- 把原_start空间的数据拷贝到新空间。
- 更新_finish。
- 释放原来的_start。
- 更新_start 和 _endofstorage
代码:
void reserve(size_t n)
{//n比当前容量大
if (cacpcity()< n)
{ //开辟n个空间
T* tmp = new T[n];
//拷贝
for (int i = 0; i< size(); i++)
{*(tmp + i) = *(_start + i);
}
//更新_finish
_finish = tmp + size();
//销毁旧空间
delete[] _start;
//更新
_start = tmp;
_endofstorage = _start + n;
}
}
insert函数
insert函数是在容器指定位置插入一个数据，而实现insert后我们可以复用insert实现push_back尾插函数。
而这个指定位置，我们用迭代器来表示。插入完后，我们返回插入数据的迭代器位置，方便迭代。
指定位置插入
iterator insert(iterator pos, const T& val)
{ //pos必须在 _start - _finish之间
assert(pos >= _start && pos<= _finish);
//判断空间是否足够
if (_finish == _endofstorage)
{ size_t len = pos - _start;
//空间不够，增容，是0增容4，不是0增容2倍
reserve(cacpcity() == 0 ? 4 : 2 * cacpcity());
pos = _start + len;
}
//把pos - finish 的位置都往后移动
iterator end = _finish;
while (end >pos)
{ *(end) = *(end - 1);
--end;
}
*pos = val;
++_finish;
//返回pos迭代器
return pos;
}push_back是一个尾插函数，而我们前面实现过insert，所以可以直接复用。
void push_back(const T& val)
{ //复用insert
insert(end(), val);
}我们要支持下标访问，可以重载[]操作符，给定一个下标，返回_start+下标的解引用的引用即可。
T& operator[](const T& val)
{ return *(_start + val);;
}如果是const对象，那么我们不允许修改[]的值。
const T& operator[](const T& val)const
{ return *(_start + val);;
}直接释放_start的空间即可。
~vector()
{ delete[] _start;
_start = _finish = _endofstorage = nullptr;
}我们可以用 被拷贝对象的迭代区间实例化一个对象，再把当前对象与这个对象进行交换。
然后出了函数，实例化的对象会被自动析构。
void swap(vector& v)
{ std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector(const vector& v)
{ vectortmp(v.begin(), v.end());
//交换
swap(tmp);
} 直接用拷贝构造构造一个，然后和当前对象交换。
vector& operator=(const vectorv)
{ vector v2(v);
swap(v2);
return *this;
} eraser函数是在指定位置删除，我们依旧通过迭代器的方式删除。删除后，返回原来下标的迭代器。
代码:
iterator erase(iterator pos)
{ //pos必须在start - finish区间，且 size不能为空
assert(size() >0);
assert(pos >= _start && pos< _finish);
int len = pos - _start;
//从pos的下一个位置开始，往前覆盖
iterator begin = pos + 1;
while (begin != _finish)
{ *(begin - 1) = *begin;
++begin;
}
_finish--;
return pos;
}pop_back是一个尾删函数，也就是删除最后一个数据，我们可以复用erase
void pop_back()
{ erase(end() - 1);
}end是指向最后一个数据的下一个位置，所以 -1 就是最后一个数据。
反向迭代器反向迭代器我们需要再有一个类来封装它，目的是为了让它具有复用性。不仅让它可以在 vector中使用，在list里也可以复用 。
反向迭代器模板我们可以用模板来接收，目的是为了让它既能生成普通反向迭代器，也可以生成带有const的反向迭代器。iterator是传过来的普通迭代器，Ref是返回解引用后的值，Ptr是返回指针。
templateclass _reverse_iterator
{typedef _reverse_iteratorself;
public:
private:
iterator reverse_iterator;
}; 反向迭代器其实就是正向迭代器封装，只是++操作变–，–操作变++
_reverse_iterator(iterator it)
:_it(it)
{}
反向迭代器的++是普通迭代器的- -
//前置++
self& operator++()
{--_it;
return *this;
}
//后置++
self operator++(int)
{self tmp(*this);
--_it;
return tmp;
}反向迭代器的- - 是正向迭代器的++
//前置--
self& operator--()
{++_it;
return *this;
}
//后置--
self operator--(int)
{self tmp(*this);
++_it;
return tmp;
}根据官方的stl，解引用返回的其实是它反向迭代器的前一个位置。
因为起始位置是在最后一个数据的下一个位置。
所以返回它的前一个位置即可
Ref operator*()
{iterator tmp = (*this)._it;
return *(--tmp);
}然后我们在主类里面加上模板。
typedef _reverse_iteratorreverse_iterator;
typedef _reverse_iteratorconst_reverse_iterator; 
比较地址相不相等，直接返回结果即可。
bool operator!=(const self& it)
{return _it != it._it;
}
bool operator!=(const self& it)const
{return _it != it._it;
}一样，直接返回结果即可。
bool operator==(const self& it)
{return _it == it._it;
}
bool operator==(const self& it)const
{return _it == it._it;
}rbegin函数返回最后一个数据的下一个位置，也就是_finish，那我们就用_finish实例化一个反向迭代器。
reverse_iterator rbegin()
{ return reverse_iterator(_finish);
}对于const容器，我们返回const的反向迭代器
const_reverse_iterator rbegin()const
{ return const_reverse_iterator(_finish);
}rend函数就是第一个元素，我们用_start实例化反向迭代器然后返回。
reverse_iterator rend()
{ return reverse_iterator(_start);
}
const 容器返回const的反向迭代器
const_reverse_iterator rend()const
{ return const_reverse_iterator(_start);
}如果我们vector存的是一个对象类型，我们还需要支持->访问。所以重载->操作符。
Ptr operator->()
{ return &operator*();;
}我们->也要返回前一个地址，而*操作符返回的是解引用后的值，我们对这个值取地址即可。
全部代码:
vector.h全部代码:
#pragma once
#include
#include#include"reverse_iterator.h"
using namespace std;
namespace wyl
{templateclass vector
{public:
//普通迭代器
typedef T* iterator;
//const迭代器
typedef const T* const_iterator;
//反向迭代器
typedef _reverse_iteratorreverse_iterator;
typedef _reverse_iteratorconst_reverse_iterator;
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{}
//迭代器区间初始化
templatevector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{ while (first != last)
{ //把迭代器数据依次插入当前对象
push_back(*first);
++first;
}
}
~vector()
{ delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
void swap(vector& v)
{ std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
vector(const vector& v)
{ vectortmp(v.begin(), v.end());
//交换
swap(tmp);
}
T& operator[](const T& val)
{ return *(_start + val);
}
vector& operator=(const vectorv)
{ vector v2(v);
swap(v2);
return *this;
}
const T& operator[](const T& val)const
{ return *(_start + val);;
}
size_t size()
{ return _finish - _start;
}
size_t size()const
{ return _finish - _start;
}
size_t cacpcity()
{ return _endofstorage - _start;
}
size_t cacpcity()const
{ return _endofstorage - _start;
}
void reserve(size_t n)
{ //n比当前容量大
if (cacpcity()< n)
{ //开辟n个空间
T* tmp = new T[n];
//拷贝
for (int i = 0; i< size(); i++)
{*(tmp + i) = *(_start + i);
}
//更新_finish
_finish = tmp + size();
//销毁旧空间
delete[] _start;
//更新
_start = tmp;
_endofstorage = _start + n;
}
}
指定位置插入
iterator insert(iterator pos, const T& val)
{ //pos必须在 _start - _finish之间
assert(pos >= _start && pos<= _finish);
//判断空间是否足够
if (_finish == _endofstorage)
{ size_t len = pos - _start;
//空间不够，增容，是0增容4，不是0增容2倍
reserve(cacpcity() == 0 ? 4 : 2 * cacpcity());
pos = _start + len;
}
//把pos - finish 的位置都往后移动
iterator end = _finish;
while (end >pos)
{ *(end) = *(end - 1);
--end;
}
*pos = val;
++_finish;
//返回pos迭代器
return pos;
}
iterator erase(iterator pos)
{ //pos必须在start - finish区间，且 size不能为空
assert(size() >0);
assert(pos >= _start && pos< _finish);
int len = pos - _start;
//从pos的下一个位置开始，往前覆盖
iterator begin = pos + 1;
while (begin != _finish)
{ *(begin - 1) = *begin;
++begin;
}
_finish--;
return pos;
}
void pop_back()
{ erase(end() - 1);
}
iterator begin()
{ return _start;
}
iterator end()
{ return _finish;
}
const_iterator begin()const
{ return _start;
}
const_iterator end()const
{ return _finish;
}
//反向迭代器
reverse_iterator rbegin()
{ return reverse_iterator(_finish);
}
const_reverse_iterator rbegin()const
{ return const_reverse_iterator(_finish);
}
reverse_iterator rend()
{ return reverse_iterator(_start);
}
const_reverse_iterator rend()const
{ return const_reverse_iterator(_start);
}
void push_back(const T& val)
{ //复用insert
insert(end(), val);
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
void a(const vector& v)
{for (int i = 0; i< v.size(); i++)
{ //v[i] = 10;
cout<< v[i]<< " ";
}
}
void test1()
{vectorv;
v.push_back(1);
cout<< v.size()<< ","<< v.cacpcity()<< endl;
v.push_back(2);
cout<< v.size()<< ","<< v.cacpcity()<< endl;
v.push_back(3);
cout<< v.size()<< ","<< v.cacpcity()<< endl;
v.push_back(4);
v.push_back(5);
cout<< v.size()<< ","<< v.cacpcity()<< endl;
vector::iterator it = v.begin();
//while (it != v.end())
//{//
// cout<< *it<< " ";
// ++it;
//}
for (int i = 0; i< v.size(); i++)
{ v[i] = 10;
cout<< v[i]<< " ";
}
a(v);
}
void test2()
{vectorv;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
//v.erase(v.begin());
//v.erase(v.end()-1);
vectorv2 = v;
vector::reverse_iterator rit = v2.rbegin();
while (rit != v2.rend())
{
cout<< *rit<< " ";
++rit;
}
}
struct Date
{int _year;
int _month;
int _day;
Date(int year = 1,int month = 1,int day = 1)
:_year(year)
,_month(month)
,_day(day)
{}
};
void b(const vector& v)
{vector::const_reverse_iterator rit = v.rbegin();
while (rit != v.rend())
{ cout<< rit->_year<< " "<< rit->_month<< " "<< rit->_day<< endl;
++rit;
}
}
void test3()
{vectorv;
v.push_back(Date(2022, 1, 1));
v.push_back(Date(2022, 2, 1));
v.push_back(Date(2022, 3, 1));
b(v);
}
}
反向迭代器封装的类的全部代码
reverse_iterator.h
#pragma once
templateclass _reverse_iterator
{typedef _reverse_iteratorself;
public:
_reverse_iterator(iterator it)
:_it(it)
{}
//前置++
self& operator++()
{--_it;
return *this;
}
//后置++
self operator++(int)
{self tmp(*this);
--_it;
return tmp;
}
//前置--
self& operator--()
{++_it;
return *this;
}
//后置--
self operator--(int)
{self tmp(*this);
++_it;
return tmp;
}
Ref operator*()
{iterator tmp = (*this)._it;
return *(--tmp);
}
Ptr operator->()
{return &operator*();
}
bool operator!=(const self& it)
{return _it != it._it;
}
bool operator!=(const self& it)const
{return _it != it._it;
}
bool operator==(const self& it)
{return _it == it._it;
}
bool operator==(const self& it)const
{return _it == it._it;
}
private:
iterator _it;
}; 主main函数文件代码
test.cpp
#include"vector.h"
void vectorTest()
{//wyl::test1();
wyl::test3();
}
int main()
{vectorTest();
}代码是跟着博客边写，边测，没问题才写上博客的。而后续还会为大家更新更多关于stl的知识，以及一些容器的模拟实现。而反向迭代器具有复用性，也就是这次实现了，下次模拟实现其他容器时可以直接带进去用。实际中vector的使用频率也很高，手动实现一次vector对学习stl的帮助也非常大。后续会持续为大家更新关于C/C++，数据结构以及linux操作系统等知识，如果觉得讲的还可以，可以三连关注一下。如果哪里有写的不对的地方，也欢迎大家指出。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
新闻名称：【C++】STL---vector的模拟实现(超级详细，万字详解)-创新互联
网址分享：http://scyanting.com/article/dgoejj.html
