电子商务网站系统设计,世界十大搜索引擎排名,wordpress 反广告插件,wordpress 删除重复vector引入 vector的实现主要依靠三个成员变量:start,finish和end_of_storage 其中#xff1a; [start]指向容器中的起始位置 [finish]指向容器中最后一个有效数据的下一个位置 [end_of_storage]指向容器中现有容量的位置 通过这三个指针#xff0c;就使得vector的size… vector引入 vector的实现主要依靠三个成员变量:start,finish和end_of_storage 其中 [start]指向容器中的起始位置 [finish]指向容器中最后一个有效数据的下一个位置 [end_of_storage]指向容器中现有容量的位置 通过这三个指针就使得vector的size() finish - start capacity end_of_storage - start. 成员函数 [函数模板] 为了使我们的vector实用性更好我们需要使用函数模板。 [迭代器] 构造函数 上面是vector的构造函数每个构造函数的使用如下 我们根据这里提供的接口自己实现构造函数。 [默认构造] [迭代器构造] 左边是迭代器构造函数的实现右边是调用迭代器构造发现确实是调用了迭代器构造。 需要注意的地方为什么迭代器要使用模板 因为我们不知道传进来的是什么类型就需要用模板来接收保证泛型编程。 [拷贝构造函数] 下面有两种拷贝构造函数的实现都是错误的因为这是浅拷贝。 浅拷贝会导致两个vector指向同一个地址空间。 对v1的操作同时也是对v的操作了。 浅拷贝对内置类型没有影响因为不会对堆上的内容进行析构。 例如下面这样 但是浅拷贝对自定义类型影响很大会导致析构的的时候析构两次导致崩溃 //1.4 拷贝构造 -- 用v来初始化thisvector(const vectorT v){//注意不能使用memcpy,memcpy是浅拷贝_start new T[v.capacity()]; //开辟一块新的空间for (size_t i 0; i v.size(); i){_start[i] v[i];}_finish _start v.size();_end_of_storage _start v.capacity();}对拷贝构造函数进行测试 [赋值运算符重载函数] 需要注意的地方有两个 1. 判断一下不能自己给自己赋值 2. 要先释放掉原来的空间 vectorT operator(const vectorT v){//防止自己给自己赋值if (this ! v){//1.释放掉原来的空间delete[] _start;_start new T[v.capacity()];for (int i 0; i v.size(); i){_start[i] v[i];}_finish _start v.size();_end_of_storage _start v.capacity();}return *this;}对赋值运算符重载函数进行测试 n个值构造因为涉及调用resize()函数所以放在后面写。 扩容函数 实现reserve()函数 reserve()函数实现逻辑是什么 [reserve()函数] 这样写会出现什么问题 我们用如下代码对reserve()进行测试。 测试结果如下 这是因为在计算新空间的_finish的时候调用的是size()函数。 先看看size()函数是如何实现的 因此改进的方式是在_start指向新空间之前将size()的内容存储下来。 void reserve(size_t n){if (n capacity()){//不进行任何操作}else{//先将size()的内容存储下来int sz size();//这里的扩容是开辟一块空间将旧的内容拷贝的新空间上T* tmp new T[n]; if (_start){for (int i 0; i size(); i){tmp[i] _start[i];}//释放掉以前的空间delete[] _start;}//让_start指向新开辟的空间_start tmp;_finish _start sz;_end_of_storage _start n;}}运行测试 resize()函数] 实现resize()函数可以分为三种情况 1.n _finish 2.n _finish n _end_of_storage 3.n _end_of_storage 其实前两种可以合并成一种。因为他们都不需要对vector进行扩容。 后面的一种需要对vector进行扩容可以使用reserve()函数进行复用。 resize()函数的具体实现 void resize(size_t n, const T value T()){if (n size()){_finish _start n;}else{//1.扩容reserve(n);//2.将内容插入到vector中while (_finish ! _start n){*_finish value;_finish;}}}测试 测试n个值构造的时候出现报错非法的间接寻址 首先弄明白什么是非法的间接寻址 只有指针和迭代器可以解引用内置类型不能解引用。而如果对内置类型解引用就会出现非法的间接寻址。 为什么明明我们调用的是n个值的构造函数确走到了迭代器初始化 这就要提一下最匹配的问题了。因为我们传递的是int类型但是n个值的构造函数却是size_t类型。所以不是最匹配就会走到迭代器构造函数这里来。 因此解决办法就是调用最匹配的构造函数对原来的构造函数进行重载即可。 修改 [pop_back()函数] 函数实现 不需要将删除的元素置空只用挪动_finish指针以后有新的操作时直接对原数据进行覆盖 对函数进行测试 [pop_back()函数]
void push_back(const T x)
{if (_finish _end_of_storage){size_t newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);}*_finish x;_finish;
}[insert()函数]迭代器失效问题
_finish是最后一个元素的下一个位置。我们要插入值就需要找到最后一个元素并且将这些元素一个一个往后挪动直到空出pos的位置插入value
实现逻辑如下
void insert(iterator pos, const T val){assert(pos _start pos _finish);//1.判断扩容逻辑if (_finish _end_of_storage){int newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);}//2.将pos后的内容往后移动auto end _finish - 1; //_finish指向的是最后一个元素的下一个位置while (end pos){*(end 1) *end;--end;}//3.将val插入到vector中*pos val;_finish;}当没有扩容时对函数进行测试 一旦前面进行扩容 插入的数是随机数。 这就是内部迭代器失效的问题。
为什么会出现迭代器失效的问题 从刚刚的测试可以看出迭代器失效应该是和是否扩容有关的我们从调试的角度来看看。 扩容之前_start和pos的内容 扩容之后_start因为使用reserve()进行异地扩容位置就会发生改变而pos没有改变位置。会导致后面的pos和end无法比较 通过图示更直观的理解 解决办法就是让pos和_start一起走。计算出pos和_start之间的偏移量在_start换到新的地址之后根据偏移量计算出pos的新位置。 代码 void insert(iterator pos, const T val){assert(pos _start pos _finish);//1.判断扩容逻辑if (_finish _end_of_storage){//1.1计算出pos和_start的偏移量int n _start - pos;int newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);//1.2扩容完之后根据偏移量找到新pos的位置pos _start n;}//2.将pos后的内容往后移动auto end _finish - 1; //_finish指向的是最后一个元素的下一个位置while (end pos){*(end 1) *end;--end;}//3.将val插入到vector中*pos val;_finish;}运行结果 解决完内部迭代器失效问题之后还存在外部迭代器失效的情况。 什么是外部迭代器失效 用自己写的vector看看会出现什么结果 对迭代器解引用是随机值这就代表迭代器失效了。 为什么会失效 因为我们调用insert()插入值之后迭代器的位置会改变因此就失效了。 如何解决外部迭代器失效的问题呢 1.在insert()函数中返回迭代器 2.在调用insert()之后接收改变后的迭代器 必须要接收迭代器不然还是会出现迭代器失效的问题。 iterator insert(iterator pos, const T val){assert(pos _start pos _finish);//1.判断扩容逻辑if (_finish _end_of_storage){//1.1计算出pos和_start的偏移量int n _start - pos;int newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);//1.2扩容完之后根据偏移量找到新pos的位置pos _start n;}//2.将pos后的内容往后移动auto end _finish - 1; //_finish指向的是最后一个元素的下一个位置while (end pos){*(end 1) *end;--end;}//3.将val插入到vector中*pos val;_finish;//返回迭代器return pos;}[erase()函数]迭代器失效问题
删除的逻辑
iterator erase(iterator pos){assert(pos _start pos _finish);auto it pos 1;while (it ! _finish){*(it - 1) *it;it;}--_finish;return pos;}测试 元素访问
[operation[]函数] T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}[迭代器] iterator begin(){return _start;}iterator end(){return _finish;}const_itertator begin() const{return _start;}const_itertator end() const{return _finish;}容量
[size()函数] size_t size() const{return _finish - _start;}[capacity()函数] size_t capacity() const{return _end_of_storage - _start;}代码
模拟实现vector的全部代码
#pragma once
#includeiostream
#includeassert.h
using std::cout;
using std::cin;
using std::endl;namespace zyy
{templateclass Tclass vector{typedef T* iterator;typedef const T* const_itertator;public://1.1默认构造vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){}//1.2 n个值构造 -- 这里使用匿名对象是因为不知道要构造的对象是什么类型vector(size_t n, const T value T()){resize(n, value);}//防止出现 非法的间接寻址 问题vector(int n, const T value T()){resize(n, value);}//1.3 用迭代器初始化template class InputIterator //这里使用模板的原因是可能有很多类型的迭代器,string,int, double等vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){while (first ! last){push_back(*first);first;}}//1.4 拷贝构造 -- 用v来初始化this//vector(const vectorT v)//{// //注意不能使用memcpy,memcpy是浅拷贝// _start new T[v.capacity()]; //开辟一块新的空间// for (size_t i 0; i v.size(); i)// {// _start[i] v[i];// }// _finish _start v.size();// _end_of_storage _start v.capacity();//}// 拷贝构造vector(const vectorT v){_start new T[v.capacity()]; //开辟一块和容器v大小相同的空间memcpy(_start, v._start, sizeof(T) * v.size());//将容器v当中的数据一个个拷贝过来_finish _start v.size(); //容器有效数据的尾_end_of_storage _start v.capacity(); //整个容器的尾}//vector(const vectorT v)//{// _start v._start;// _finish _start v.size(); //容器有效数据的尾// _end_of_storage _start v.capacity(); //整个容器的尾//}//赋值运算符重载函数vectorT operator(const vectorT v){//防止自己给自己赋值if (this ! v){//1.释放掉原来的空间delete[] _start;_start new T[v.capacity()];for (int i 0; i v.size(); i){_start[i] v[i];}_finish _start v.size();_end_of_storage _start v.capacity();}return *this;}~vector(){delete[] _start;_start nullptr;_finish nullptr;_end_of_storage nullptr;}//迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_itertator begin() const{return _start;}const_itertator end() const{return _finish;}//operator[]T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}//2.操作函数//2.1尾插void push_back(const T val){if (_finish _end_of_storage){int newCapacity capacity() 0 ? 4 : 2 * capacity();reserve(newCapacity);}*_finish val;_finish;}void pop_back(){assert(_finish _start);--_finish;}iterator insert(iterator pos, const T val){assert(pos _start pos _finish);//1.判断扩容逻辑if (_finish _end_of_storage){//1.1计算出pos和_start的偏移量int n _start - pos;int newCapacity capacity() 0 ? 4 : capacity() * 2;reserve(newCapacity);//1.2扩容完之后根据偏移量找到新pos的位置pos _start n;}//2.将pos后的内容往后移动auto end _finish - 1; //_finish指向的是最后一个元素的下一个位置while (end pos){*(end 1) *end;--end;}//3.将val插入到vector中*pos val;_finish;//返回迭代器return pos;}iterator erase(iterator pos){assert(pos _start pos _finish);auto it pos 1;while (it ! _finish){*(it - 1) *it;it;}--_finish;return pos;}//2.2 扩容函数将vector的容量扩大到nvoid reserve(size_t n){if (n capacity()){//不进行任何操作}else{//先将size()的内容存储下来int sz size();//这里的扩容是开辟一块空间将旧的内容拷贝的新空间上T* tmp new T[n]; if (_start){for (int i 0; i size(); i){tmp[i] _start[i];}//释放掉以前的空间delete[] _start;}//让_start指向新开辟的空间_start tmp;_finish _start sz;_end_of_storage _start n;}}void resize(size_t n, const T value T()){if (n size()){_finish _start n;}else{//1.扩容reserve(n);//2.将内容插入到vector中while (_finish ! _start n){*_finish value;_finish;}}}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void print(){for (int i 0; i size(); i){cout _start[i] ;}cout endl;}private:T* _start nullptr;T* _finish nullptr;T* _end_of_storage nullptr;};
}总结
在模拟实现vector中需要注意的地方 拷贝构造函数必须使用深拷贝不能使用memcpy()函数因为memcpy()函数是浅拷贝。浅拷贝对内置类型没有什么影响但是对自定义类型可能会导致析构两次的错误。 在对vector进行扩容时主要的思想是开辟一块新的空间然后将原来的空间的内容拷贝到新的空间中。需要重新计算_finish和_end_of_storage_finish _start size()。 如果调用size()函数就会导致访问出现问题。具体原因是size()函数的实现逻辑是_finish - _start。 在扩容之后_start指向了新的空间_finish还在原来的空间使用_finish - _start会导致访问越界。因此解决办法就是在_start指向新空间时先用sz接收size()的返回值在后续修改_finish时就不会调用函数导致访问越界了。 当进行insert()插入时可能会出现迭代器失效的问题。 主要原因是在插入过程中如果遇到扩容的情况就会导致_start指向了新的空间但是传入的pos还指向原来的空间在扩容之后再进行插入就会出现pos访问越界。 做法和size()是一样的先保存一下pos到_start的偏移量在_start指向新空间之后使用偏移量找到pos在新空间的位置。 外部迭代器失效的问题。在进行插入或者删除值之后如果不对原来的迭代器进行更新并且再次访问该迭代器时就会出现迭代器失效问题。具体表现在访问迭代器为随机值。 解决办法为1.insert()和erase()函数都返回迭代器并且在自己调用的时候接收迭代器做到对迭代器的更新。
