网站建设电销,网站优化关键词怎么做,郑州seo线下培训,wordpress动漫整站实现基本的vector框架
参考的是STL的一些源码#xff0c;实现的vector也是看起来像是一个简略版的#xff0c;但是看完能对vector这个类一些接口函数更好的认识。
我们写写成员变量#xff0c;先来看看STL的成元变量是那些
namespace tjl
{templateclass Tclass … 实现基本的vector框架
参考的是STL的一些源码实现的vector也是看起来像是一个简略版的但是看完能对vector这个类一些接口函数更好的认识。
我们写写成员变量先来看看STL的成元变量是那些
namespace tjl
{templateclass Tclass vector{public:typedef T* iterator;vector():_start(nullptr),_finish(nullptr),_eof(nullptr){}private:iterator _start;//iterator _finish;iterator _eof;//表示的是end_of_storage};}这里的成员变量有些不一样我们也用iterator来表示其实这里就是一个指针但是用迭代器的名称来称呼它还有我们这里加上了模板更加凸显了vector的不一样这样的好处就是我们这个vector这个类就可以去适应各种不同的类型达到一个____效果填一个四字成语。
实现构造函数
构造函数的意义就是来进行初始化因为我们构造函数里面都是会走初始化列表的这个过程的所以我们就可以写成这个样子。
vector():_start(nullptr),_finish(nullptr),_eof(nullptr){}
但是要注意的是我们的库里面的构造函数可不是只有这些大家可以也来查询我们的网站来查看
vector构造函数 我们可以看到他是可以支持迭代器进行构造的也就是说我们这里可以使用任意类型来进行构造
也可以用给值的方式所以vector的作用还是很大的。 析构函数的实现
析构函数的作用就是在我们程序结束的时候对我们的空间进行释放所以我们可以这样写
~vector(){if (_start){delete[]_start;_start _finish _eof nullptr;}}
这里我们可以增加if这个判断因为_start可能是为空的所以我们可以写一个对它进行检查的功能。
实现vector的size和capacity
size_t size()const{return _finish - _start;}size_t capacity const{return _eof - _start;}
我们这里的实现细节其实只要注意的是const因为我们可能是const对象进行调用所以这里可以加上const防止我们的权限进行放大。
实现push_back
这里的实现会有点小细节值的我们注意我们先来想想push_back是在尾部插入数据·就可以了但是我们可不可能如果当我们的空间是满的时候就会遇到需要扩容的问题所以这个时候我们需要先来写一个reserve的函数来进行扩容
reserve函数的实现
因为我们每次扩容的时候到要用到这个函数比如尾插还是随机插入都会用到那我们的思路是那些还有注意事项呢
首先我们得先知道一个问题就是我们当什么时候才是要扩容的时候因为reserve会传一个参数n
表示我们得开多大的空间所以我们需要做的时候就是先判断要不要开这么大的空间。
先来看我们的代码
void reserve(size_t n){if (n capacity()){T* tmp new T[n];size_t pos _finish - _start;if (_start){memcpy(tmp, _start, sizeof(T) * size());delete[]_start;}_start tmp;_finish _start pos;_eof _start n;}}
思路就是我们重新开辟一块空间然后把原来空间的内容拷贝到新内容上这里要注意的是当我们赋值的时候就是给_start和_finish给值的时候要先记录pos位置因为我们扩容的时候是重新开辟的可能存在_finish进行赋值的时候它还是指向空这样就出现空指针的现象了。
那我们实现reserve之后就可以继续来实现push_back函数了。
void push_back(const T val){if (_finish _eof){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish val;_finish;}
先检查空间是不是够如果空间不够我们就需要进行扩容其次就是大家这里要明白一个点为什么我们可以对_finish进行解引用然后直接进行给值原因就是val的类型。 实现operator[] 这个很简单直接一把过了。 const T operator[](size_t pos) const{return _start[pos];}
用[]进行遍历来看看。
void test1()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (int i 0; i v.size(); i){cout v[i] ;}
}
迭代器的实现
iterator begin(){return _start;}iterator end(){return _finish;}
因为迭代器我们必须要给它命名begin和end要不然就不能使用范围for来进行遍历我们现在可以用迭代器来对我们的数据进行遍历也能使用范围for这里两种方式都写出来给大家看看。
void test1(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (int i 0; i v.size(); i){cout v[i] ;}cout endl;for (auto e : v){cout e ;}auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;}
这样有三种方式可以对我们进行遍历了完成迭代器只后需要来处理一些细节问题还是我们权限放大的问题因为当我们用const的对象去调用的时候就不行了这里只需要在写一个const版本的了我们可以先typedef一下。
typedef const T* const_iterator;
这样就表示这个迭代器是const修饰过的迭代器。那它的begin和end就是这样写的。
const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}
不过我们对const的迭代器只能进行读的操作就不能进行写操作了。
迭代器失效问题
这个问题是出现在insert和erase的时候是会出现问题
首先我们实现insert需要注意的细节有哪些
和我们之前遇到的顺序表其实本质是没有多大区别的这里用的是指针而不是数组下标因为这里模拟实现的时候其实我们的迭代器就是原生指针虽然和VS里的不一样Vs里的iterator并不是原生指针所以很好实现我们这里的insert来看看代码吧。
iterator insert(iterator pos, const T val T()){assert(pos begin());assert(pos end());size_t len pos - _start;if (_finish _eof){reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;}
其实这里我就一步到位了但是还是有很多的细节值的我们去注意第一个就是为什么说这里会有迭代器失效的问题首先就是如果我们步扩容的时候迭代器是不会失效的但是扩容之后的pos还是指向原来控空间的因为我们这里的扩容的步骤是开空间然后对我们的内容进行值拷贝释放之前的空间这样pos就是一个野指针所以我们需要做的就是更新pos位置到新的空间上可以先记住pos的相对位置然后更新。所以这里这个坑是没有位置的还有一个需要注意的是我们需要更新外面的pos因为形参的改变是不会影响实参的改变的所以这里的一个重要的步骤就是返回pos的值。 迭代器的失效第一个重要的原因就是这个指针变成野指针了我们需要更新它 第二个原因就是当我们进行insert的时候需要进行返回因为我们在这个函数内改变了但是在外面还是没有进行改变形参的改变是不会影响实参的改变的 我们来进行测试一下
void test2(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout e ;}cout endl;auto pos find(v.begin(), v.end(), 2);v.insert(pos, 100);for (auto e : v){cout e ;}} 发现最后的结果也是正确的这样还要提醒大家我们认为insert和erase之后的迭代器是失效的不再使用虽然我们可以接受pos位置但是最好还是不要使用。
实现erase iterator erase(iterator pos){assert(pos begin());assert(pos end());iterator start pos;while (start _finish){*start *(start 1);start;}_finish--;return pos;}
这个erase也是很简单就是移动进行数据的覆盖就可以解决问题了。我们也来测试一下看看结果是不是对的。
void test3(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout e ;}cout endl;auto pos find(v.begin(), v.end(), 2);v.erase(pos);for (auto e : v){cout e ;}cout endl;}
深浅拷贝问题
先来实现拷贝构造。
拷贝构造的实现可以有现代写法和原始写法我们先来写原始写法那个然后引出我们的深浅拷贝的问题。 vector(const vectorT v){reserve(v.capacity());memcpy(_start, v._start, sizeof(T) * v.size());}
我们这里进行的值拷贝是按照字节的拷贝的如果我们T是内置类型的时候我们的的代码是不会出现问题的但是如果是string或者里面还是一个vectorint的时候代码就会出现问题我们可以先来看看string的结果。
void test4(){vectorstring v;v.push_back(111111);v.push_back(111111);v.push_back(111111);for (auto e : v){cout e ;}cout endl;vectorstring v1(v);for (auto e : v1){cout e ;}}
我们这样写的时候就是会出现错误原因是我们这里的拷贝构造是进行的值拷贝不过如果我们不写这个拷贝构造的时候是不会出现问题的原因string会去调用它自己的拷贝构造。
但是其根本原因还是我们扩容的是进行的是值拷贝和我们没有写拷贝构造造成的问题。现在来修改一下reserve。
void reserve(size_t n){if (n capacity()){T* tmp new T[n];size_t pos _finish - _start;if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i 0; i size(); i){tmp[i] _start[i];}delete[]_start;}_start tmp;_finish _start pos;_eof _start n;}}
然后加上我们的考拷贝构造。
vector(const vectorT v){reserve(v.capacity());for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_eof _start v.capacity();}
这个就是原始的写法这样我们的代码是没有问题的但是这里为什么没有问题的第一个原因就是string是我们库里面的进行赋值的时候会去调用它的赋值重载但是如果我们这里的类型是vectorvectorint又会出现问题我们可以来看看如果我们需要拷贝一个杨辉三角的时候会不会有问题。
下面来演示一下我们可以先把杨辉三角的代码直接先拿过来
class Solution {public:vectorvectorint generate(int numRows) {vectorvectorint vv;vv.resize(numRows, vectorint());//进行初始化//进行的是每行初始化因为这里表示的是顺序表里面是个顺序表for (int i 0; i vv.size(); i)//初始化没列{vv[i].resize(i 1, 0);vv[i][0] vv[i][vv[i].size() - 1] 1;}for (int i 0; i vv.size(); i){for (int j 0; j vv[i].size(); j){if (vv[i][j] 0){vv[i][j] vv[i - 1][j - 1] vv[i - 1][j];}}}return vv;}};
然后进行拷贝一个杨辉三角看看有没有什么问题
void test5(){vectorvectorint v Solution().generate(5);auto v1(v);for (int i 0; i v1.size(); i){for (int j 0; j v1[i].size(); j){cout v1[i][j] ;}cout endl;}} 熟悉的感觉真是太美妙了
那我们其实可以通过调试来看看问题所在的地方。 可以看到什么不一样的地方一个就是我们的外面的大vector是完成了深拷贝里面还是没有为什么其他类型的string就可以因为string有它自己的赋值重载我们这里没有写vector的赋值重载所以才会有这样的问题那我们只需要写一个赋值重载就可以解决问题了。 void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_eof, v._eof);}vectorT operator( vectorT v){swap(v);return *this;}
这样我们的问题就能够很好的解决了。 那我们再来完善一下其他的接口函数就解决了。
pop_back的实现
void pop_back(){erase(--end());}templateclass InputIteratorvector(InputIterator first, InputIterator last){while (first ! last){push_back(*first);first;}}
完整的代码实现
#pragma once
#includeassert.h
namespace tjl
{templateclass Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr),_finish(nullptr),_eof(nullptr){}vector(size_t n, const T val T()):_start(nullptr), _finish(nullptr), _eof(nullptr){reserve(n);while (n--){push_back(val);}}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_eof, v._eof);}vectorT operator( vectorT v){swap(v);return *this;}vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _eof(nullptr){reserve(n);while (n--){push_back(val);}}templateclass inputiteratorvector(inputiterator first, inputiterator last): _start(nullptr), _finish(nullptr), _eof(nullptr){while (first ! last){push_back(*first);first;}}vector(const vectorT v): _start(nullptr), _finish(nullptr), _eof(nullptr){reserve(v.capacity());for (size_t i 0; i v.size(); i){_start[i] v._start[i];}_finish _start v.size();_eof _start v.capacity();}void reserve(size_t n){if (n capacity()){T* tmp new T[n];size_t pos _finish - _start;if (_start){//memcpy(tmp, _start, sizeof(T) * size());for (size_t i 0; i size(); i){tmp[i] _start[i];}delete[]_start;}_start tmp;_finish _start pos;_eof _start n;}}iterator begin(){return _start;}iterator end(){return _finish;}const T operator[](size_t pos) const{return _start[pos];}T operator[](size_t pos) {return _start[pos];}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}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 push_back(const T val){if (_finish _eof){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish val;_finish;}size_t size()const{return _finish - _start;}size_t capacity() const{return _eof - _start;}iterator insert(iterator pos, const T val T()){assert(pos begin());assert(pos end());size_t len pos - _start;if (_finish _eof){reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}*pos val;_finish;return pos;}iterator erase(iterator pos){assert(pos begin());assert(pos end());iterator start pos;while (start _finish){*start *(start 1);start;}_finish--;return pos;}~vector(){if (_start){delete[]_start;_start _finish _eof nullptr;}}private:iterator _start;//iterator _finish;iterator _eof;//表示的是end_of_storage};class Solution {public:vectorvectorint generate(int numRows) {vectorvectorint vv;vv.resize(numRows, vectorint());//进行初始化//进行的是每行初始化因为这里表示的是顺序表里面是个顺序表for (int i 0; i vv.size(); i)//初始化没列{vv[i].resize(i 1, 0);vv[i][0] vv[i][vv[i].size() - 1] 1;}for (int i 0; i vv.size(); i){for (int j 0; j vv[i].size(); j){if (vv[i][j] 0){vv[i][j] vv[i - 1][j - 1] vv[i - 1][j];}}}return vv;}};void test1(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);for (int i 0; i v.size(); i){cout v[i] ;}cout endl;for (auto e : v){cout e ;}auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;}void test2(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout e ;}cout endl;auto pos find(v.begin(), v.end(), 2);v.insert(pos, 100);for (auto e : v){cout e ;}}void test3(){vectorint v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);for (auto e : v){cout e ;}cout endl;auto pos find(v.begin(), v.end(), 2);v.erase(pos);for (auto e : v){cout e ;}cout endl;}void test4(){vectorstring v;v.push_back(111111);v.push_back(111111);v.push_back(111111);for (auto e : v){cout e ;}cout endl;vectorstring v1(v);for (auto e : v1){cout e ;}}void test5(){vectorvectorint v Solution().generate(5);auto v1(v);for (int i 0; i v1.size(); i){for (int j 0; j v1[i].size(); j){cout v1[i][j] ;}cout endl;}}}今天的分享就到这里了我们下次再见
