成都网站制作成都,重庆网红景点排名,互联网金融,建个网站花钱做百度推广vector的模拟实现 一. vector的模拟实现1.0 与string的区别1.1 实现内容实现方法 二. vector模拟中重点讲解内容#xff08;坑#xff09;2.1 erase的使用问题2.2 resize的特殊写法2.3 operator 2.4 reserve 三. 整体代码 一. vector的模拟实现
我们知道#xff1a; 在STL中… vector的模拟实现 一. vector的模拟实现1.0 与string的区别1.1 实现内容实现方法 二. vector模拟中重点讲解内容坑2.1 erase的使用问题2.2 resize的特殊写法2.3 operator 2.4 reserve 三. 整体代码 一. vector的模拟实现
我们知道 在STL中我们上次学了string 但其实准确来说string并不算是STL中的成员。 因为string出现的比STL要早 所以string的设计相比于STL中其他的容器要麻烦的多。
但是今天带来的vector可以说是是完完全全的STL中的容器。
这里可能还有人不知道容器是什么东西。 容器准确来说是用来处理数据的 就比如我们之前学习进程的时候在管理文件的时候 文件文件内容文件属性 本质都是数据所以我们能看到很多的链表和顺序表的成分在。
而之后我们要学习的算法 作用则是:处理数据 存储数据处理数据可以说是组成了程序
1.0 与string的区别
为什么这里要讲string和vector的区别
因为string和vector一样实际上就是一个顺序表
但是还是有很大的区别
而vector通过模板的功能来实现能存储多种类型的数据
string相当于将char类型的数据拎出来为它拓宽了很多接口的同时为了兼容C语言保留了很多字符串的特殊点。 所以 i. string只能存储char类型 ii. string保留了末尾是’\0’的成分
而vector则是全新的对象不需要兼容C语言。 i. 所以vector能存储各种类型 ii. 同时末尾不用添加’\0’
1.1 实现内容
我们模拟实现vector的目的 是为了更好的了解vector来帮助我们更好的使用和学习。
所以这里就挑几个比较重要的接口进行实现 做到一个比较基础的vector。 这个就是大致的实现内容。
因为这个和string的实现实在是太像了所以就选几个比较重点的讲
其他未讲到的会后面会放在整体代码中。
实现方法
这里不同于string的capacity和data实现方法
这里vector用的是三个指针成员变量的实现方法但是实际上没有相差多少用string的同样可以实现。
class vector
{
public:
private:iterator _start;iterator _finish;iterator _eofstorage;
};这里的 _start就是开辟数组的开始指针 _finishi:就是开辟数组最后一个元素的指针 _eofstorage:数组开辟空间的空间的最后位置的地址
这个实现方法区别其实不重要用string的实现方法依旧可以实现。
二. vector模拟中重点讲解内容坑
2.1 erase的使用问题
erase 这个函数的功能是 删除指定位置的元素。
int main()
{std::vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);std::vectorint::iterator begin v1.begin();v1.erase(begin);for (auto i : v1){std::cout i;}
}具体就是这样使用。
接下来就来演示erase的一个非常经典的错误用法。
这里用的是STL中的vector因为官方的使用中这个问题也是十分常见的。
#includeiostream
#includevector
#includevector.h
int main()
{std::vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);std::vectorint::iterator begin v1.begin();v1.erase(begin);while (begin ! v1.end()){std::cout *begin;begin;}
}这里能发现程序崩掉了。
这是我们发现 这里我们把begin迭代器指定的内容删除后 然后继续使用了begin迭代器。
但是按照我们的道理来讲 这个begin的指向的方向应该还是老方向。 erase之后各类元素会向前面补位begin应该指向新补位的2了。
按道理来说这个begin应该是可以继续使用的。
因为在vs中这个问题算是迭代器失效 在使用迭代器对象进行insert与erase之后。 vs会默认该迭代器无法继续使用
我们知道STL不同编译器下是不同的因为官方给了一个STL的最基本的设定具体的修改和实现方法是取决于公司自己
所以在linux中可能就不会判断这个迭代器失效的效果。
这里我们来试一下。 还是同样的代码
这里能发现在linux中能进行访问。
但是这样的话为什么vs要禁止用户使用呢 这里就要讲下允许使用这个的坏处了。
这里我们在linux中用这个测试一道题 删除数组中的所有偶数 这里结果我们发现少删除了一个2。 这里其实仔细观察一下我们就能发现问题所在。 这里就能发现it删除完还会进行一次会略过连续的偶数。
这里掠过算是比较ok一点的错误了但是如果想象一下最后一位是偶数这样的话会直接掠过数组的最后一位直接向后面遍历非常容易导致越界访问。
这里其实要解决也是很简单。 只要在其中加一个else就可以了。
但是这样虽然能解决问题但是大大限制了它的平台可移植性。
所以这个情况也是开发者所在意的。 这里能发现erase有一个iterator 的返回值。 这个iterator是用来返回下一个位置的值的。 所以这里需要去接受一下返回值才能继续用这个begin变量。
2.2 resize的特殊写法
void resize(int n, const T val T())
{if (n size()){_finish _start n;}else{reserve(n);while (_finish ! _start n){*_finish val;_finish;}}
}这个是resize的函数实现。 我们知道 reserve开辟空间插入数据时不扩容 resize开空间初始化为指定值
但是resize初始化为指定值的时候指定值有多种不同的类型。
但是有时候如果用户不输入初始化的值该怎么办
void resize(int n, const T val T())这个第二个参数const T valT(); 这个可以说是一个新写法这个前面是类型
valT();是缺省值。 那这个T() 其实就是调用T类型的构造函数的的意思。
那这样我们大致就能明白是什么意思了 如果用户没有给初始化值那就去调用vector类型T的构造函数
2.3 operator
这里的operator和string的的一样要注意深浅拷贝的问题。
所以同样可以用到swap深拷贝函数。
void check_capacity(){if (_finish _eofstorage){if (_start NULL)reserve(4);elsereserve(capacity() * 2);}}2.4 reserve
void reserve(int n)
{if (n capacity()){int oldsize capacity();T* new_vec new T[n];if (_start ! nullptr){for(int i0;ioldsize;i){new_vec[i]_start[i];}delete _start;}_start new_vec;_finish _start oldsize;_eofstorage _start n;}
}这个是完成版的reserve void reserve(int n){if (n capacity()){int oldsize capacity();T* new_vec new T[n];if (_start ! nullptr){memcpy(new_vec, _start, oldsize*sizeof(T));delete _start;}_start new_vec;_finish _start oldsize;_eofstorage _start n;}}这个是改版前的reserve函数
这里发现只有一个地方发生了了改变。
if (_start ! nullptr)
{memcpy(new_vec, _start, oldsize*sizeof(T));delete _start;
}这里乍一看好像没有什么问题。
但是我们仔细想想如果vector的类型是一个自定义类型具有地址成员变量。
那memcpy对new_vec与_start进行改变时就会这个是浅拷贝无法进行深拷贝就会发生严重的问题
所以就改成了
for(int i0;ioldsize;i){new_vec[i]_start[i];}这里使用赋值重载来进行深度拷贝。 就没有这样的问题了
三. 整体代码
#includestring.h
#includeassert.h
#includeiostream
namespace my_vector
{templatetypename Tclass vector {public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr),_finish(nullptr),_eofstorage(nullptr){}vector(const vectorT v){_eofstorage_finish_startnullptr;for(int i0;iv.size();i){push_back(v[i]);}}vector(int n,const T data){_startnullptr;_finishnullptr;_eofstoragenullptr;resize(n,data);}templateclass alliteratorvector(alliterator first,alliterator end){_finishnullptr;_startnullptr;_eofstoragenullptr;while(first!end){push_back(*first);first;} }~vector(){delete _start;_start _finish _eofstorage nullptr;}void check_capacity(){if (_finish _eofstorage){if (_start NULL)reserve(4);elsereserve(capacity() * 2);}}vectorT operator (const vectorT v){if(this!v){ std::swap(_start,v._start);std::swap(_finish,v.finish);std::swap(_eofstorage,v._eofstorage);}return *this;}void push_back(const T data){check_capacity();insert(size(), data);}void reserve(int n){if (n capacity()){int oldsize capacity();T* new_vec new T[n];if (_start ! nullptr){for(int i0;ioldsize;i){new_vec[i]_start[i];}delete _start;}_start new_vec;_finish _start oldsize;_eofstorage _start n;}}iterator begin(){return _start;}iterator end(){return _finish;}size_t size() const{return _finish - _start;}void insert(int pos,const T data){assert(pos 0 pos size());check_capacity();T* end _finish;while (end _startpos){*end *(end - 1);end--;}_start[pos] data;_finish;}void erase(int pos){assert(pos 0 pos size());T* end _startpos;while (end _finish){*end *(end 1);end;}_finish--;}size_t capacity() const{return _eofstorage - _start;}T operator[](int pos){assert(pos size());return _start[pos];}const T operator[](int pos) const{assert(pos size());return _start[pos];}void pop_back(){erase(_finish - _start);}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}void resize(int n,const T valT()){if (n size()){_finish_start n;}else{reserve(n);while(_finish!_startn){*_finishval;_finish;}}}private:iterator _start;iterator _finish;iterator _eofstorage;};
}
