用vs2012做网站案例,东凤镇 网站建设,国外外贸网站有哪些问题,中国外包公司排行榜C:vector增删查改模拟实现 前言一、迭代器1.1 非const迭代器#xff1a;begin()、end()1.2 const迭代器#xff1a;begin()、end() 二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现2.1 构造函数2.1.1 无参构造2.1.2 迭代器区间构造2.1.3 n个值构造 2.2 拷贝构造2.3 … C:vector增删查改模拟实现 前言一、迭代器1.1 非const迭代器begin()、end()1.2 const迭代器begin()、end() 二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现2.1 构造函数2.1.1 无参构造2.1.2 迭代器区间构造2.1.3 n个值构造 2.2 拷贝构造2.3 赋值重载3 析构函数 三、容量相关capacity()、size()、reserve()、resize()3.1 capacity()3.2 size()3.3 reserve()3.4 resize() 四、operator[ ]重载五、元素相关insert、erase、push_back、pop_back5.1 insert()5.2 erase()5.2.1 erase迭代器失效 5.3 push_bach()5.4 pop_back() 六、所有代码 前言
提前在这说明下vector增删查改模拟实现的成员变量博主采用SGI版本。下面给出其库中成员变量是哪些后续的模拟实现都基于此。 我们发现库中定义了3个T*的变量。同时3个成员变量的意义如下 一、迭代器
1.1 非const迭代器begin()、end()
typedef T* iterator;iterator begin()
{return _start;
}iterator end()
{return _finish;
}1.2 const迭代器begin()、end()
typedef const T* const_iterator;const_iterator begin()const
{return _start;
}const_iterator end()const
{return _finish;
}二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现
2.1 构造函数
我们先来看看vector库中的构造类型如下 我们知道有三种构造方式下面给出各种的实现方式。
2.1.1 无参构造
vector():_start(nullptr),_finish(nullptr), _endofstorage{}2.1.2 迭代器区间构造
templateclass InputIterator//使用模板是为了当数据类型匹配时就可以使用
vector(InputIterator first, InputIterator last)
{while (first ! last){push_back(*first);first;}
}2.1.3 n个值构造
vector(size_t n, const T value T())
{reserve(n);for (size_t i 0; i n; i){push_back(value);}
}//防止定义vectorint这种类型走迭代区间的构造函数我们在多实现一个以下类型函数
//当使用vectorint类型的去构造时此时调用的构造函数两个参数都是int。所有他会走最匹配的函数即迭代器区间构造生成的构造函数程序会出错。
//而下面给出了现成的最匹配构造函数编译器调用时就不会走模板。
vector(int n, const T value T())
{reserve(n);for (size_t i 0; i n; i){push_back(value);}
}2.2 拷贝构造
拷贝构造我们先调用开好一块空间在依次插入数据即可。
//vector(const vector x) //库中实现模式, 直接使用类名。但C类型不是类名。
//这里各位读者了解下这里直接类名做类型也正确即可但不建议各位这样做。
vector(const vectorT v)
{reserve(v.capacity());//后面会给出实现for (auto e : v){push_back(e);}
}2.3 赋值重载
赋值重载这里我们不要传引用而是直接传参即可。编译器调用拷贝构造生成形参后在调用swap()函数依次交换形参和this即可。
//赋值重载
void swap(vectorT v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endofstorage, v_endofstorage);
}vectorT operator (vectorT tmp)
{swap(tmp);return *this;
} 3 析构函数
~vector()
{delete[] _start;_start _finish _endofstorage nullptr;
}三、容量相关capacity()、size()、reserve()、resize()
3.1 capacity()
size_t capacity()const
{return _endofstorage - _start;
}3.2 size()
size_t size()const
{return _finish - _start;
}3.3 reserve()
由于stl中我们一般不缩容所以先判断reserve的空间大小是否比当前空间容量大。 如果reserve的空间更大所以我们需要先开好目标大小的空间在将原数据拷贝过去最后析构原来空间即可。 但下面这两种实现方式对吗
第一种
void reserve(size_t n)
{if (n capacity()){T* tmp new T[n];if (_start)//如果原来空间有数据拷贝到新空间{memcpy(tmp, _start, sizeof(T) * size());delete[] _start;}//更新_start、_finish、_endofstorage。指向新空间中相应位置_start tmp;_finish _start size();_endofstorage _start n;}
}先说结论上诉这段代码是错的。 在我们调试后会发现_finish的值没有更新。这里大家自行验证下接口 原因(win11画图一直很模糊博主也很无奈各位将就看吧) 第二种 为了解决上诉问题我们可以先记录_finish和_start的偏移量用来代替size()函数。 所以初学者很容易写出以下代码
void reserve(size_t n)
{if (n capacity()){size_t sz size();//记录_finish 和 _start 的偏移量T* tmp new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);delete[] _start;}_start tmp;_finish _start sz;//不能用size()代替sz否则会导致迭代器失效_endofstorage _start n;}
}那这是否正确呢答案是否定的。 我们来看看下面这种场景 实际上对于这种情况可以自己循环依次赋值即可。内置类型直接拷贝数据内置类型调用赋值重载是一种深拷贝。
最终代码如下
void reserve(size_t n)
{if (n capacity()){size_t sz size();//记录_finish 和 _start 的偏移量T* tmp new T[n];if (_start){//memcpy(tmp, _start, sizeof(T) * sz);for (size_t i 0; i sz; i){tmp[i] _start[i];}delete[] _start;}_start tmp;_finish _start sz;//不能用size()代替sz否则会导致迭代器失效_endofstorage _start n;}
}3.4 resize()
resize逻辑还是很简单的。 首先判断resize()的目标大小n和有效数据个数size()谁大。如果有效个数size()更大只需更改_finish即可否则要先进行扩容reserve会将原有数据拷贝到新空间然后从_finish开始向扩充的空间插入新的值。 代码如下
//const会延长匿名对象的生命周期, 匿名对象具有常性
//模板出来后对类进行了升级内置类型也有构造函数
//void resize(size_t n, T val T())
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;}}
}四、operator[ ]重载
T operator[](size_t pos)
{assert(pos size());return _start[pos];
}const T operator[](size_t pos)const
{assert(pos _finish);return _start[pos];
}五、元素相关insert、erase、push_back、pop_back
5.1 insert()
任意位置插入数据首先需判断是否需要扩容。然后将插入位置pos开始往后的数据向后移动最后将新数据插入到pos处即可。 tips
如果发生扩容需要先记录pos和_start之间的偏移量。在将pos位置跟新指向新空间中对应位置。否则会导致迭代器失效
void insert(iterator pos, const T x)
{assert(pos _start);assert(pos _finish);if (_finish _endofstroage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}//挪动数据iterator end _finish - 1;while (end pos){*(end 1) *end;end--;}//插入数据*pos x;_finish;
}5.2 erase()
任意位置删除数据只需要从pos1开始将后续数据全部依次向前移动覆盖最后更新_finish即可。
iterator erase(iterator pos)
{assert(pos _start);assert(pos _finish);iterator it pos 1;while (it _finish){*(it - 1) *it;it;}--_finish;return pos;
}5.2.1 erase迭代器失效
void testvector4()
{vectorint v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(6);auto it v.begin();while (it v.end()){if (*it % 2 0){v.erase(it);}it;}for (auto e : v){cout e ;}cout endl;
}上述代码本意是将偶数全部删除结果本该是1 、5。但结果却是 为什么呢 这是因为我们删除元素后后续数据会补上空缺。所以当使用erase后迭代器会失效。上述结果是g的实现机制在vs2019下上述代码会直接报错。原因在于vs2019对erase后的空间做强制检查不允许访问。为此stl库给出的解决方案是接受删除位置的下一个元素的返回值。这也是为什么整个模拟实现中只有erase函数具有返回值,并接收返回值。 正确删除偶数方法
void testvector4(){//std::vectorint v;vectorint v;v.push_back(1);v.push_back(2);v.push_back(2);v.push_back(4);v.push_back(5);v.push_back(6);auto it v.begin();//迭代器失效/*while (it v.end()){if (*it % 2 0){v.erase(it);}it;}*/while (it v.end()){if (*it % 2 0){it v.erase(it);}else{it;}}for (auto e : v){cout e ;}cout endl;}5.3 push_bach()
头插复用insert函数即可。
void push_back(const T x)
{//if (_finish _endofstroage)//{// reserve(capacity() 0 ? 4 : capacity() * 2);//}插入数据//*_finish x;//_finish;insert(_finish, x);
}
5.4 pop_back()
复用erase尾删
void pop_back()
{erase(--end());
}六、所有代码
vector增删查改模拟实现gitee链接
