提供建站服务的网络公司的比较,企业信用信息查询系统官网(全国),免费的WORDPRESS主题响应式,青岛做模板网站的公司前言#xff1a;
有了前面的string库的介绍#xff0c;在这里我就不再介绍vector库了#xff0c;而是直接模拟实现了。
vector库的概念和作用#xff1a;
vector库是针对于数组的数据类型的容器#xff0c;它有点类似我们曾经实现过的顺序表#xff0c;你完全可以按照…前言
有了前面的string库的介绍在这里我就不再介绍vector库了而是直接模拟实现了。
vector库的概念和作用
vector库是针对于数组的数据类型的容器它有点类似我们曾经实现过的顺序表你完全可以按照顺序表去理解vector,针对顺序表我们自然少不了增删查改的功能所以接下来让我们模拟实现一下vector库。
模拟实现过程
1.私有成员变量的设置
在这里我们这样设置我们的私有成员变量由于文档中C/C库的函数大部分是用迭代器实现的故我们模拟的时候也使用迭代器去操作,故成员如下
private:iterator _start;iterator _finish;iterator _endofstorage;其中_start指向顺序表开头_finish指向顺序表的数字的结尾而_endofstorage则控制容量指向容量的结尾 但是我们C中是没有所谓的iterator的但是我们知道iterator的本质是指针故我们对类型重命名如下
typedef T* iterator;
typedef const T* const_iterator;2.构造函数 析构函数 拷贝构造函数
私有成员建立好后我们下一个便是构建基本的三个函数构造析构拷贝构造。 首先是构造函数
vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}这里就是常规的全让指针为空因为我们会在调整容量的位置去为这三个成员变量赋值 析构函数
~vector()
{delete[] _start;_start _finish _endofstorage nullptr;
}这里需要注意的点就是我们是需要在堆区上动态开辟空间的故我们的析构函数是必须显式实例化的要让析构函数释放掉我们的堆区空间。 拷贝构造函数
vector(const vectorT s):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{for (auto ch : s){push_back(ch);}
}再拷贝构造这里我使用了遍历尾插的方式或许你会说直接memcpy不是更好么但是我们的顺序表不仅仅要存储内置类型有时也要存储自定义类型而memcpy对应的是一种浅拷贝一旦涉及到指针的问题就会有多次释放的危险故我们在这里采取尾插的方式即自定义类型会调用其赋值运算符重载内置类型则直接赋值这样就很好的避免了多次释放的问题。
3.赋值运算符重载
void swap( vectorT tmp)
{std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_endofstorage, tmp._endofstorage);
}
vectorT operator( vectorT tmp)
{swap(tmp);return *this;
}我在这里采取的现代写法和string一样采用一个变量tmp来打工的方式将值转给*this,大体的写法概念不变我这里不过多赘述了。
4.size长度 capacity容量
size用来返回顺序表的长度而capacity用来返回顺序表的容量
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _endofstorage - _start;
}5.首尾迭代器返回
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}
const_iterator begin()const
{return _start;
}
const_iterator end()const
{return _finish;
}在这里我们写了两个版本一个是可读可写版本一个是可读不可写版本分别返回不同的迭代器
6.下标访问操作符[]重载
其基本和我们字符串的写法区别不大
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}
const T operator[](size_t pos) const
{assert(pos size());return _start[pos];
}同样也是两个版本可改与不可改
7.扩容(本次实现的重点)
扩容是我们本次实现的重点在这里牵扯到一个很关键的问题迭代器失效。 何为迭代器失效呢 先看下面的代码
void reserve(size_t n)
{if (n capacity()){T* tmp new T[n];if (_start){int i 0;for (i 0; i size(); i){tmp[i] _start[i];}delete _start;}_start tmp;_finish _start size();_endofstorage _start capacirty();}
}这段代码就涉及到严重的迭代器失效的问题问题出在我们的delete被销毁后我们对应的size()和capacity()本质上指向的是之前的被销毁的数组的地址这样我们使用函数是得不到正确的长度的因为迭代器此时的地址是无效的这便是我们所谓的迭代器失效你可以看这张图理解 所以我们可以这样去修改程序
void reserve(size_t n)
{size_t sz size();if (n capacity()){T* tmp new T[n];if (_start){int i 0;for (i 0; i size(); i){tmp[i] _start[i];}delete _start;}_start tmp;_finish _start sz;_endofstorage _start n;}
}即先用一个变量将长度存储起来而不是再用失效的迭代器返回长度和容量在这里就是sz来存储这样我们就不会出现我们的长度是错误的问题了。
7.改变数组长度 void resize(size_t n, const T x T())//改变数组长度{ //注意,内置类型是可以调用构造函数的在模板这个章节是支持的在这里别忘了加一个const因为我们的缺省值是常量不加const引用权限会放大if (n capacity()){_finish _start n;}else{reserve(n);//剩下来填数据while (_finish _start n){*_finish x;_finish;}}}解决了扩容问题我们其他的都很好解决了这里也是一样我们考虑两种情况即可但是注意依旧用赋值不要用memcpy因为涉及到浅拷贝的问题。
8.尾插 尾删
尾插
void push_back(const T x) //尾插
{if (_finish _endofstorage){reserve(capacity() 0 ? 4 : 2 * capacity());}*_finish x;_finish;
}尾删
void push_pop()
{_finish--;
}没什么好说的顺手就应该写出来。
9.任意插 任意删
任意删 iterator erase(iterator pos){assert(pos _start);assert(pos _finish);iterator cur pos 1;while (cur _finish){*(cur - 1) *cur;cur;}_finish--;return pos;}任意删的思路和我们顺序表的任意删差不多直接覆盖即可强调一下别忘了对我们传入的迭代器进行检验就好。 但是任意删有一个细节就是我们会涉及到迭代器失效的问题即这个位置被删除后再想针对这个位置删除就是出现问题所以我们返回pos即删除后的下一个位置的指针这样就可以一直删不会删除一次就失效了。 任意插
void insert(iterator pos, const T x)//任意插
{assert(pos _start);assert(pos _finish);//这里可以等于,方便尾插if (_finish _endofstorage){size_t range pos - _start;//在这里先存储一个长度变量方便后续迭代器失效时重新指定位置reserve(capacity() 0 ? 4 : 2 * capacity());pos _start range;//由于扩容之后pos失效那样的话pos不在新数组上故我们要存储一个整型方便扩容之后把pos重新带到新数组上来,别忘了任意插也存在扩容后迭代器失效的问题我们的pos也会停留在之前的数组上被销毁之后就丢失了要重新给到新的数组上}iterator end _finish - 1;while (end pos)//这里要等于保证其能在pos的位置之前插而不是正好插入pos位置{*(end 1) *end;end--;}*pos x;_finish;
}在任意插这里我们需要注意一个扩容的问题凡是涉及到扩容和删除的问题当我们使用迭代器去操作的时候就要最好看一看是否涉及到迭代器失效的问题在任意删这里就涉及到了po针对的是被删除的数组的地址但我们扩容后pos的原位置直接失效了故我们需要在扩容后调整pos到新数组的对应位置上即
if (_finish _endofstorage){size_t range pos - _start;//在这里先存储一个长度变量方便后续迭代器失效时重新指定位置reserve(capacity() 0 ? 4 : 2 * capacity());pos _start range;//由于扩容之后pos失效那样的话pos不在新数组上故我们要存储一个整型方便扩容之后把pos重新带到新数组上来,别忘了任意插也存在扩容后迭代器失效的问题我们的pos也会停留在之前的数组上被销毁之后就丢失了要重新给到新的数组上}然后一个常规的插入pos即可这里最关键的便是针对迭代器失效我们应该如何处理。
总结
以上便是我们vector模拟实现的全部内容和string一样我们模拟实现vector最关键的目的是学会一些思路以及熟练的去使用vector这是最关键的。 补充一句WBG加油
