什么网站可以直接做word,阿里巴巴国际平台,江西建设信息网站,店面装修设计图片什么是vector
vector是一个封装了动态大小数组的顺序容器跟任意其它类型容器一样#xff0c;它能够存放各种类型的对象。
模拟实现
实现前的准备
在实现vector之前#xff0c;为了和库里的区分开需要将实现的vector放在一个自定义的命名空间里。而且vector需要实现成模版…什么是vector
vector是一个封装了动态大小数组的顺序容器跟任意其它类型容器一样它能够存放各种类型的对象。
模拟实现
实现前的准备
在实现vector之前为了和库里的区分开需要将实现的vector放在一个自定义的命名空间里。而且vector需要实现成模版的方式所以需要我们传模版参数模版参数也就是顺序容器所存的数据类型。而且根据库里的vector有三个关键的成员变量分别指向顺序容器的起始位置数据容量位置空间容量位置。
namespace cr
{templateclass Tclass vector{public:private:iterator _start;iterator _finish;iterator _endofstorage;};
} 迭代器的相关实现
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;
}
这里要提醒的就是,_finish指向的是最后一个有效数据的下一个位置_endofstorage指向的是对象的最大容量位置处的下一个位置。 下标引用operator[]
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}
这里需要注意的是不要忘记断言 容器大小
size_t capacity() const
{return _endofstorage - _start;
}
size_t size() const
{return _finish - _start;
}
为了保证const对象调用该函数时也可以正常通过所以对该函数进行const修饰。 析构函数
~vector()
{delete[] _start;
} 扩容reserve
void reserve(size_t n)
{if (n capacity()){size_t sz size();T* tmp new T[n];if (sz ! 0){memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;//勿忘}_start tmp;_finish _start sz;_endofstorage _start n;}
} 这里进行扩容时一定要注意判断空间大小关系尤其是要注意三个指针的指向问题在此之前记录好原空间中有效数据的个数因为执行new操作都是异地扩容所以_start存的地址肯定发生改变如果此时通过_start求得的_finish就一定会出错所以需要提前记录好位置关系。但是该函数不一定正确 尾插数据push_back void push_back(const T x)
{if (_finish _endofstorage)reserve(size() 0 ? 4 : capacity() * 2);*_finish x;_finish;
} push_back需要注意的地方就是当空间大小为0时需要扩的大小以及_finish。这里来验证一下自内置类型的数据结果 再看看string类的数据结果引发了异常: 读取访问权限冲突。 其实这里的问题哦就是reserve的实现出了问题 当空间不够时会发生扩容就会调用memcpy函数memcpy是库里的而且我们知道memcpy内部就是通过值拷贝将_start解引用进行拷贝给tmp_start是一个string类的指针所以此时拷贝好的数据相当于是浅拷贝指向如下 然后调用析构函数将_start空间内存释放但是_start内部数据是string类所以会先调用string的析构函数释放string得空间所以此时就是报错所在tmp内的string同样也销毁了。 修改reverse函数 void reserve(size_t n)
{if (n capacity()){size_t sz size();T* tmp new T[n];if (sz ! 0){//memcpy(tmp, _start, sizeof(T) * sz);for (int i 0; i sz; i){tmp[i] _start[i];//如果T是string调用std::string的赋值重载}delete[] _start;//勿忘}_start tmp;_finish _start sz;_endofstorage _start n;}
} 这种拷贝的方式就有效避免了浅拷贝的问题如果模版参数T是string类的话tmp[i]的类型就是string所以此时的赋值就会调用string的赋值重载operator进行深拷贝所以就不会出问题。 改变有效数据个数resize
void resize(size_t n, const T x T())//匿名对象
{if (n size()){reserve(n);while (_finish ! _endofstorage){*_finish x;_finish;}}else{_finish _start n;}}
这里要注意的就是T x给的缺省值T()T()其实就是调用匿名对象的构造函数然后在调用拷贝构造给x对象而编译器会优化成直接的构造。匿名对象具有常性不能同一块空间不加const出了该行就自动析构const引用可以延长匿名对象的生命周期。但是如果是内置类型这样写也是没问题的其实内置类型也是可以看做有构造函数的。就如下测试 构造函数 vector(size_t n0,const T valT()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);while (n--){push_back(val);}
} 拷贝构造 vector(const vectorT v):_start(new T[v.capacity()]),_finish(_start),_endofstorage(_startv.capacity())
{for (auto ch : v){*_finish ch;//如果T是string调用std::string的赋值重载_finish;}
} 通过迭代器区间初始化的构造函数 //在一个类模版里面还可以继续写模版函数
templateclass InputIterator
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{while (first ! last){push_back(*first);first;}
} 这里迭代器区间的构造函数是需要实现成模版类型的因为库里面的STL说明不同的容器可以通过迭代器区间进行初始化只不过有点不兼容的可以进行强制类型转换 但是当执行到构造函数时 cr::vectorint vv(3, 1); 会报错非法的间接寻址 原因当我们调用构造函数时会优先找最匹配的构造函数进行调用所以此时以上的三种构造函数就会调用迭代器区间构造函数而不是第一种
vector(size_t n0,const T valT())//一般构造
vector(InputIterator first, InputIterator last)迭代器区间构造 调用第一种时会发生int类型到size_t类型的转换而第三种构造函数会直接调用因为第三种构造有模版参数而对于两个参数3,1都是int类型所以此时模版形参InputIterator就是替换成int型所以此时第三种更匹配。 解决方法 将第一个构造函数的形参改变成int类型再生成一个构造函数形成重载 vector(int n, const T val T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n);while (n--){push_back(val);}
} 赋值重载operator
vectorT operator(vectorT v)
{swap(_start, v._start);swap(_finish, v._finish);swap(_endofstorage, v._endofstorage);return *this;
}
这里是要一个返回值的主要是避免连等的情况abc; 在某位置插入数据insert void insert(iterator pos, T x)
{assert(pos _start pos _finish);if (_finish _endofstorage);{reserve(_startnullptr?4:capacity() * 2);}iterator end _finish-1;while (end pos){*(end 1) *end;end--;}*pos x;_finish;
} 以上代码其实是有问题的如下测试 调试时你会发现是在insert内部出了问题 而且会在下面代码不断循环 while (end pos)
{*(end 1) *end;end--;
} 所以问题极可能出现在上面的代码段 此时pos依旧是nullptr就相当于pos指向的依旧是原空间的地址插入数据扩容时空间都发生了变化所以再拿原空间的指针和新空间的指针比较就不妥。 修改代码其实就是记录pos位置和_start之间的差距好在扩容到新空间时将差距补上 void insert(iterator pos, T x)//insert使用之后迭代器失效最好不要使用
{assert(pos _start pos _finish);//不要忘记断言if (_finish _endofstorage);{size_t len pos - _start;reserve(_startnullptr?4:capacity() * 2);//异地扩容改变了_start可能导致pos成为野指针pos _start len;}iterator end _finish-1;while (end pos){*(end 1) *end;end--;}*pos x;_finish;
} 虽然修改了代码编译起来也没问题但是如果你执行下列操作还是跑不通 此时是断言处出问题了其实这种情况属于迭代器失效因为你插入数据时发生了扩容了所以同上面一样it指针指向的是原空间的首个位置所以就会错误 解决方法每次插入数据是重新调用迭代器v.begin()或v.end()来获得迭代器的位置。 在某位置删除数据erase void erase(iterator pos)
{assert(pos _finish pos _start);iterator end pos 1;while (end _finish){*(end - 1) *end;end;}_finish--;
} 这里和inssert是不同的erase不会发生扩容所以也不存在迭代器失效但是这erase要注意的就是每次删除一个数据时位置会发生挪动所以一般在刷题时一定要注意这个小细节。 而VS下的erase是并不是这样实现的VS下的erase也只能使用一次用完了该指针也就是失效了。尽管进行it还是--来改变it再使用也是不可以的。 所以可以借鉴insert的用法 但是VS下的erase其实是有返回值的 其实返回的就是你删除的那个数据的下一个位置但是位置会发生挪动所以返回的也就是pos位置 如有解释不当欢迎大家留言
