模板wordpress演示站怎么做,电商美工,福永外贸网站建设,帝国cms如何做微网站#x1f31f;#x1f31f;作者主页#xff1a;ephemerals__
#x1f31f;#x1f31f;所属专栏#xff1a;C、STL
目录
前言
一、vector底层刨析
二、模拟实现
1. 属性、迭代器以及函数声明
2. 功能实现
交换两个容器的内容
构造函数
拷贝构造
赋值重载
析构…
作者主页ephemerals__
所属专栏C、STL
目录
前言
一、vector底层刨析
二、模拟实现
1. 属性、迭代器以及函数声明
2. 功能实现
交换两个容器的内容
构造函数
拷贝构造
赋值重载
析构函数
下标引用operator[ ]
容量接口
迭代器接口
判空
resize
reserve
插入和删除
insert和push_back
erase和pop_back
3. 程序全部代码
总结 前言 之前我们学习了vector的常用接口及其使用方法 【c丨STL】vector的使用-CSDN博客 本篇文章我们将深入探讨vector的底层实现原理并尝试模拟实现其结构以及一些常用接口。
一、vector底层刨析 之前已经提到vector的底层是动态顺序表我们使用c语言实现顺序表的结构时赋予了它三个成员变量
typedef int SLDataType;//动态顺序表
typedef struct SeqList
{SLDataType* arr;//定义起始指针后续动态开辟内存空间int size;//有效数据的个数int capacity;//数组的空间大小
}SL;
可以看到我们定义了一个起始指针指向分配的内存然后用size和capacity两个变量分别记录元素个数和空间容量。接下来我们再看看SGI版本的STL源码 为了提高程序的兼容性和灵活性源码并没有使用size和capacity等属性而是使用了三个迭代器指针来维护数组。这三个迭代器分别指向数组的不同位置 start指向首元素 finish指向末尾元素的“后一位” end_of_storage指向可用空间的末尾 图示 那么接下来我们在模拟实现vector时将仿照SGI版本的做法通过定义相应的成员变量即三个迭代器来构建其内部结构。 另外由于vector本质上是一个类模板允许我们存储任意类型的数据元素因此在接下来模拟实现vector的过程中我们也将采用类模板来进行定义。由于类模板成员函数的定义和声明分离到两个文件会造成链接错误我们选择在头文件中同时完成这些成员函数的声明与定义。
二、模拟实现
1. 属性、迭代器以及函数声明 首先是属性、迭代器的声明以及我们需要实现的接口
#include iostream
#include algorithm
#include cassert
using namespace std;templateclass T
class Vector
{
public://vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;//迭代器接口iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;//无参构造Vector();//初始化器构造Vector(initializer_listT l);//迭代器区间构造templateclass InputIteratorVector(InputIterator first, InputIterator last);//n个val值构造Vector(size_t n, const T val T());//拷贝构造Vector(const VectorT v);//赋值重载VectorT operator(VectorT v);//析构~Vector();//下标引用T operator[](size_t i);const T operator[](size_t i) const;//容量接口size_t size() const;size_t capacity() const;//判空bool empty() const;//交换void swap(VectorT tmp);//调整大小void resize(size_t n, const T val T());//增容void reserve(size_t n);//插入和删除void push_back(const T x);void pop_back();iterator insert(iterator pos, const T x);iterator erase(iterator pos);
private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;
}; 由于vector和string的数据元素都是采用顺序存储的方式它们在功能实现上存在相似之处。因此建议先阅读string模拟实现之后再来阅读本文否则其中的一些实现过程可能会较难理解。
2. 功能实现 接下来我们将正式开始实现上述接口的功能。
交换两个容器的内容 与之前实现string时相同直接交换它们的成员变量就可以完成数据的交换无需重新开辟空间。 代码实现
//交换
void swap(VectorT tmp)
{std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);
}
构造函数 这里我们实现了四个构造函数的重载分别是无参构造、初始化器构造、迭代器区间构造和n个val值构造
//无参构造
Vector()
{}//初始化器构造
Vector(initializer_listT l)
{reserve(l.size());for (auto e : l){push_back(e);}
}//迭代器区间构造
templateclass InputIterator
Vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}//n个val值构造
Vector(size_t n, const T val T())
{reverse(n);for (size_t i 0; i n; i){push_back(val);}
}
不难发现由于我们在成员变量声明时已经赋初值所以无参构造中什么都不用做。这样无参构造也可以写成如下形式
Vector() default;//强制生成无参构造
我们显示写了构造函数后编译器就不会默认生成无参构造函数。我们用这条语句就可以强制让编译器生成一个无参的构造函数。 其余的构造函数都是通过遍历来访问每个元素并将它们依次尾插到数组中的。push_back、reverse等函数我们之后实现。这里特别注意一下n个val值构造函数如果我们不传val参数则会调用T类型的默认构造函数生成一个匿名对象并赋值给val。
拷贝构造 与初始化器构造的原理相似我们遍历被拷贝数组的每个元素并将它们逐一尾插到当前数组中。
//拷贝构造
Vector(const VectorT v)
{reverse(v.capacity());for (auto e : v){push_back(e);}
}
赋值重载 这里我们使用新式写法string使用过构造新对象然后交换完成赋值操作。
//赋值重载
VectorT operator(VectorT v)
{swap(v);return *this;
}
析构函数
//析构
~Vector()
{if (_start)//避免多次释放{delete[] _start;_start _finish _end_of_storage nullptr;}
}
下标引用operator[ ] 下标引用重载可以让我们像访问数组元素一样访问容器内容。
//下标引用
T operator[](size_t i)
{assert(i size());//防止越界return _start[i];
}
const T operator[](size_t i) const
{assert(i size());return _start[i];
}
容量接口 使用指针减指针的方式来实现容量接口size和capacity功能。
//容量接口
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
迭代器接口 由于string和vector底层都是顺序存储所以它们的迭代器相对简单都是直接使用指针实现。之后我们学习list链表时就会接触到更加复杂的迭代器实现。
//迭代器接口
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}
判空 当start与finish指向同一处时容器即为空。
//判空
bool empty() const
{return _start _finish;
}
resize 如果参数n的值小于当前size则该函数会将size调整为n值并且删除超出的元素。 如果参数n的值大于当前size则会在末尾插入元素至size等于n值。
//调整大小
void resize(size_t n, const T val T())
{if (n size()){_finish _start n;}else{reserve(n);while (_finish _start n){*_finish val;_finish;}}
}
reserve reserve的实现原理与string相似当参数n值大于当前容量时我们才会进行增容操作。这里需要注意由于容量大小由三个迭代器控制所以我们重新开辟空间之前需要记录原来的size便于确定增容之后三个迭代器指向的位置。
//增容
void reserve(size_t n)
{if (n capacity()){size_t old_size size();//记录原来的sizeT* tmp new T[n];if (_start)//如果start是空说明数组为空不拷贝数据{for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish tmp old_size;_end_of_storage tmp n;}
}
插入和删除
insert和push_back insert和push_back负责插入操作。这里需要注意insert实现时的迭代器失效问题。 什么是迭代器失效呢简单的讲由于vector是使用三个迭代器来维护的那么如果它们指向的空间被释放那么就会出现野指针的情况这三个迭代器的相关操作就是无效的这就是迭代器失效。迭代器失效的本质就是你管理的内存已经不属于你了。 insert出现迭代器失效的原因很简单我们在插入数据时如果空间已满就会增容此时分配新的空间然后把内容拷贝过去并释放旧空间。原本我们传入的参数pos指定的插入位置是一个指向旧空间的迭代器旧空间被释放后该迭代器就会失效从而无法插入数据。 解决办法 记录迭代器pos与start的相对距离当增容完成之后根据相对距离更新pos即可。 为什么string在进行插入的时候不会发生迭代器失效呢因为参数pos本身是一个整形代表要插入的下标只要该下标不越界就不会出现失效的情况。当然这只是插入时不会并不是一定不会。如果你在外部定义了一个迭代器当字符串空间被释放后该迭代器也会失效。此时我们对迭代器重新赋值即可。
接下来我们实现insert和push_back的代码
iterator insert(iterator pos, const T x)
{assert(pos _start pos finish);//确保插入位置合法if (_finish _end_of_storage)//空间已满增容{size_t len pos - _start;//记录相对位置reserve(capcaity() 0 ? 4 : 2 * capacity());//增容pos _start len;//更新pos}iterator i _finish - 1;while (i pos)//pos之后元素全体向后移动一位{*(i 1) *i;i--;}*pos x;_finish;return pos;//返回指向新元素的迭代器
}
void push_back(const T x)
{insert(_finish, x);//直接调用insert
}
erase和pop_back erase和pop_back负责删除操作。与insert相同erase也会发生迭代器失效的问题。但是erase不会造成空间容量的改变理论上是不会使迭代器失效的。不过如果有一个迭代器指向末尾元素删除数据之后finish前移该迭代器指向的数据就是非法的就会造成迭代器失效。所以删除vector的任意元素后vs编译器就会认为指向该元素的迭代器失效无法继续使用。 对于这种问题的解决方法也很简单如果我们只是删除一次数据迭代器失效也没关系如果要连续删除则需要更新迭代器。对此我们在erase函数中删除元素后将指向该元素位置的迭代器作为返回值函数外部需要使用该返回值更新迭代器。
erase和pop_back代码实现
iterator erase(iterator pos)
{assert(pos _start pos _finish);//确保删除位置合法auto i pos 1;while (i _finish)//pos之后元素全体前移一位{*(i - 1) *i;i--;}_finish--;return pos;//返回删除位置迭代器
}
void pop_back()
{assert(!empty());//防止空删_finish--;
}
3. 程序全部代码
模拟实现vector的全部代码如下
#include iostream
#include algorithm
#include cassert
using namespace std;templateclass T
class Vector
{
public://vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;//迭代器接口iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}//无参构造Vector(){}//初始化器构造Vector(initializer_listT l){reserve(l.size());for (auto e : l){push_back(e);}}//迭代器区间构造templateclass InputIteratorVector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}//n个val值构造Vector(size_t n, const T val T()){reverse(n);for (size_t i 0; i n; i){push_back(val);}}//拷贝构造Vector(const VectorT v){reverse(v.capacity());for (auto e : v){push_back(e);}}//赋值重载VectorT operator(VectorT v){swap(v);return *this;}//析构~Vector(){if (_start)//避免多次释放{delete[] _start;_start _finish _end_of_storage nullptr;}}//下标引用T operator[](size_t i){assert(i size());//防止越界return _start[i];}const T operator[](size_t i) const{assert(i size());return _start[i];}//容量接口size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}//判空bool empty() const{return _start _finish;}//交换void swap(VectorT tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}//调整大小void resize(size_t n, const T val T()){if (n size()){_finish _start n;}else{reserve(n);while (_finish _start n){*_finish val;_finish;}}}//增容void reserve(size_t n){if (n capacity()){size_t old_size size();//记录原来的sizeT* tmp new T[n];if (_start)//如果start是空说明数组为空不拷贝数据{for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish tmp old_size;_end_of_storage tmp n;}}//插入和删除void push_back(const T x){insert(_finish, x);//直接调用insert}void pop_back(){assert(!empty());//防止空删_finish--;}iterator insert(iterator pos, const T x){assert(pos _start pos finish);//确保插入位置合法if (_finish _end_of_storage)//空间已满增容{size_t len pos - _start;//记录相对位置reserve(capcaity() 0 ? 4 : 2 * capacity());//增容pos _start len;//更新pos}iterator i _finish - 1;while (i pos)//pos之后元素全体向后移动一位{*(i 1) *i;i--;}*pos x;_finish;return pos;//返回指向新元素的迭代器}iterator erase(iterator pos){assert(pos _start pos _finish);//确保删除位置合法auto i pos 1;while (i _finish)//pos之后元素全体前移一位{*(i - 1) *i;i--;}_finish--;return pos;//返回删除位置迭代器}
private:iterator _start nullptr;iterator _finish nullptr;iterator _end_of_storage nullptr;
};
总结 本篇文章我们深入了解了vector的底层原理并成功地模拟实现了它。与传统的动态顺序表不同它采用了三个迭代器来维护数组提高了程序灵活性。也正因如此它的实现难度也有所增大对于细节把控的要求也很高。之后博主会带领大家学习一个新容器--list。如果你觉得博主讲的还不错就请留下一个小小的赞在走哦感谢大家的支持❤❤❤
