g3云网站,郑州企业网站,杭州网页设计公司招聘,flash 的网站欢迎来到本期节目- - -
vector类
本期直接先上代码#xff0c;然后以代码为例介绍需要注意的问题. 模拟实现#xff1a;
#pragma once
#includeiostream
#includeassert.h
using namespace std;namespace my_room
{templateclass Tclass vector{p…欢迎来到本期节目- - -
vector类
本期直接先上代码然后以代码为例介绍需要注意的问题. 模拟实现
#pragma once
#includeiostream
#includeassert.h
using namespace std;namespace my_room
{templateclass Tclass vector{public:// Vector的迭代器是一个原生指针typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin()const{return _start;}const_iterator cend() const{return _finish;}
//---------------------------------------------------------------------------------------------//构造和析构//无参默认构造vector() {//由于给了缺省值所以可以给空}//带参构造vector(size_t n, const T value T()) {reserve(n);while (n--){push_back(value);}}//迭代器区间构造templateclass InputIteratorvector(InputIterator first, InputIterator last) {size_t size last - first;reserve(size); //提前开好空间减少扩容次数while (first ! last){push_back(*first);first;}}//拷贝构造vector(const vectorT v) {vectorT tmp(v.cbegin(), v.cend());//直接复用swap(tmp);}//赋值重载拷贝vectorT operator(vectorT v) {swap(v);return *this;}~vector(){delete[] _start; //为空也不影响_start _finish _endOfStorage nullptr;}//----------------------------------------------------------------------------------------------//核心函数void reserve(size_t n){if (n capacity()){size_t old_size size();T* tmp new T[n];for (size_t i 0; i old_size; i){tmp[i] _start[i];}delete[] _start;_start tmp;_finish _start old_size;_endOfStorage _start n;}}void resize(size_t n, const T value T()){reserve(n);if (n size()){_finish _start n;}else{while (_finish ! _start n){*(_finish) value;}}}iterator insert(iterator pos, const T x){assert(pos end());size_t old_posi pos - begin();if (_finish _endOfStorage){size_t n capacity() 0 ? 4 : capacity() * 2;reserve(n);}iterator tail end();pos begin() old_posi;while (tail pos){*tail *(tail - 1);tail--;}*pos x;_finish;return pos;}iterator erase(iterator pos){assert(pos end());iterator begin pos1;while (begin ! _finish){*(begin-1) *begin;begin;}_finish--;return pos;}//----------------------------------------------------------------------------------------------//简单函数size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}bool empty()const{return _start _finish;}T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos)const{assert(pos size());return _start[pos];}void push_back(const T x){insert(end(), x);}void pop_back(){erase(end() - 1);}void swap(vectorT v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}private:iterator _start nullptr; // 指向数据块的开始iterator _finish nullptr; // 指向有效数据的尾iterator _endOfStorage nullptr; // 指向存储容量的尾};
}核心函数
reserve
首先我们看看reserve函数 当我们在实现vector时我们都知道实现异地扩容都要经历这个流程 #mermaid-svg-bNtPFqFhtNgNXWBx {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-bNtPFqFhtNgNXWBx .error-icon{fill:#552222;}#mermaid-svg-bNtPFqFhtNgNXWBx .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-bNtPFqFhtNgNXWBx .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-bNtPFqFhtNgNXWBx .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-bNtPFqFhtNgNXWBx .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-bNtPFqFhtNgNXWBx .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-bNtPFqFhtNgNXWBx .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-bNtPFqFhtNgNXWBx .marker{fill:#333333;stroke:#333333;}#mermaid-svg-bNtPFqFhtNgNXWBx .marker.cross{stroke:#333333;}#mermaid-svg-bNtPFqFhtNgNXWBx svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-bNtPFqFhtNgNXWBx .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-bNtPFqFhtNgNXWBx .cluster-label text{fill:#333;}#mermaid-svg-bNtPFqFhtNgNXWBx .cluster-label span{color:#333;}#mermaid-svg-bNtPFqFhtNgNXWBx .label text,#mermaid-svg-bNtPFqFhtNgNXWBx span{fill:#333;color:#333;}#mermaid-svg-bNtPFqFhtNgNXWBx .node rect,#mermaid-svg-bNtPFqFhtNgNXWBx .node circle,#mermaid-svg-bNtPFqFhtNgNXWBx .node ellipse,#mermaid-svg-bNtPFqFhtNgNXWBx .node polygon,#mermaid-svg-bNtPFqFhtNgNXWBx .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-bNtPFqFhtNgNXWBx .node .label{text-align:center;}#mermaid-svg-bNtPFqFhtNgNXWBx .node.clickable{cursor:pointer;}#mermaid-svg-bNtPFqFhtNgNXWBx .arrowheadPath{fill:#333333;}#mermaid-svg-bNtPFqFhtNgNXWBx .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-bNtPFqFhtNgNXWBx .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-bNtPFqFhtNgNXWBx .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-bNtPFqFhtNgNXWBx .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-bNtPFqFhtNgNXWBx .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-bNtPFqFhtNgNXWBx .cluster text{fill:#333;}#mermaid-svg-bNtPFqFhtNgNXWBx .cluster span{color:#333;}#mermaid-svg-bNtPFqFhtNgNXWBx div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-bNtPFqFhtNgNXWBx :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 异地扩容 申请新空间 拷贝数据 释放旧空间 指向新空间 更新属性 注意
在这其中拷贝数据就需要注意在以往的顺序表中我们可能会用memcpy来拷贝数据当然在内置类型的情况下memcpy不仅不会出错而且比赋值拷贝高效 但是这里是类模板数据类型T可以是自定义类型,就有可能需要深拷贝而memcpy本质上是浅拷贝不满足需求所以使用赋值重载拷贝完成自定义类型的拷贝.
除此之外还需要注意的是更新属性问题
_finish _startsize(); //size()返回的是 (_finish - _start)的值此时_finish指向旧空间_start指向新空间返回的值根本不是有效数据的个数 所以需要在扩容之前记录一个old_size记录数据个数使_finish指向有效数据的末尾. void reserve(size_t n){if (n capacity()){size_t old_size size(); //记录old_size是为了不影响有效数据末尾的正确计算T* tmp new T[n];for (size_t i 0; i old_size; i) {tmp[i] _start[i]; //使用赋值拷贝是为了满足有深拷贝的自定义类型对象}delete[] _start;_start tmp;_finish _start old_size;_endOfStorage _start n;}}resize
接下来瞧瞧resize resize只需要注意该函数会改变有效数据的个数以及有可能会扩容.
void resize(size_t n, const T value T())
{reserve(n); //管他容量够不够直接让reserve去判断.if (n size()){_finish _start n; //直接删除数据}else{while (_finish ! _start n) {*(_finish) value; //添加数据}}
}insert
接下来瞅瞅insert 在实现insert函数时核心逻辑就是移动数据.
iterator insert(iterator pos, const T x)
{assert(pos end()); //注意可以尾插所以取等size_t old_posi pos - begin(); //由于可能需要扩容所以会导致迭代器指向旧空间提前记录相对位置if (_finish _endOfStorage){size_t n capacity() 0 ? 4 : capacity() * 2;reserve(n);}iterator tail end();pos begin() old_posi; //更新迭代器while (tail pos){*tail *(tail - 1); //从后往前挨个 向后移动tail--;}*pos x; //插入数据_finish;return pos;
}erase
最后瞄一下erase
iterator erase(iterator pos)
{assert(pos end()); //_finish没有数据不能取等iterator begin pos1;while (begin ! _finish){*(begin-1) *begin; //从前往后挨个 向前移动begin;}_finish--;return pos;
}迭代器
迭代器 迭代器屏蔽了底层的实现细节使得设计人员无需关心容器对象的内存分配就可以直接使用相应接口达到类似指针的效果. 也就是说迭代器可能是指针也可能是指针的封装. #mermaid-svg-70ofOOdhdLo20YKk {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-70ofOOdhdLo20YKk .error-icon{fill:#552222;}#mermaid-svg-70ofOOdhdLo20YKk .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-70ofOOdhdLo20YKk .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-70ofOOdhdLo20YKk .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-70ofOOdhdLo20YKk .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-70ofOOdhdLo20YKk .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-70ofOOdhdLo20YKk .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-70ofOOdhdLo20YKk .marker{fill:#333333;stroke:#333333;}#mermaid-svg-70ofOOdhdLo20YKk .marker.cross{stroke:#333333;}#mermaid-svg-70ofOOdhdLo20YKk svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-70ofOOdhdLo20YKk .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-70ofOOdhdLo20YKk .cluster-label text{fill:#333;}#mermaid-svg-70ofOOdhdLo20YKk .cluster-label span{color:#333;}#mermaid-svg-70ofOOdhdLo20YKk .label text,#mermaid-svg-70ofOOdhdLo20YKk span{fill:#333;color:#333;}#mermaid-svg-70ofOOdhdLo20YKk .node rect,#mermaid-svg-70ofOOdhdLo20YKk .node circle,#mermaid-svg-70ofOOdhdLo20YKk .node ellipse,#mermaid-svg-70ofOOdhdLo20YKk .node polygon,#mermaid-svg-70ofOOdhdLo20YKk .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-70ofOOdhdLo20YKk .node .label{text-align:center;}#mermaid-svg-70ofOOdhdLo20YKk .node.clickable{cursor:pointer;}#mermaid-svg-70ofOOdhdLo20YKk .arrowheadPath{fill:#333333;}#mermaid-svg-70ofOOdhdLo20YKk .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-70ofOOdhdLo20YKk .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-70ofOOdhdLo20YKk .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-70ofOOdhdLo20YKk .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-70ofOOdhdLo20YKk .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-70ofOOdhdLo20YKk .cluster text{fill:#333;}#mermaid-svg-70ofOOdhdLo20YKk .cluster span{color:#333;}#mermaid-svg-70ofOOdhdLo20YKk div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-70ofOOdhdLo20YKk :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 迭代器类型 输入输出迭代器 随机迭代器 Random-access Iterator 双向迭代器 Bidirectional Iterator 前向迭代器 Forward Iterator Input Iterator Output Iterator 上图中迭代器支持的行为是向下兼容的 假设p1,p2是迭代器i是常量
Iterator描述行为随机迭代器支持随机访问的迭代器p1p1- -p1ip1-ip1p2p1p2p1p2双向迭代器可以向前或者向后移动的迭代器p1p1- -p1p2前向迭代器只能向前移动的迭代器p1p1p2输入迭代器只能向前移动并读取的迭代器p1p1p2输出迭代器只能向前移动并写入的迭代器p1 p1p2
很明显咱们的vector的迭代器是随机迭代器.
迭代器失效 什么是迭代器失效 迭代器所指向的节点无效了既该节点被删除了. vector迭代器失效场景
场景1扩容
void test()
{my_room::vectorint arr;for(int i 0; i 10; i) //存入1到10{arr.push_back(i1);}my_room::vectorint::iterator old_back arr.end()-1; //指向最后一个元素10arr.reserve(1000);cout *old_back endl; //程序崩溃----error代码请勿模仿
}扩容之后old_back指向的空间已经被释放了此时相当于使用野指针. 事实上不一定只能通过直接显示调用reserve导致迭代器失效也可以间接调用reserve发生扩容行为导致迭代器失效; 例如: 使用resize函数可能会扩容,使用insert,push_back函数也可能扩容 总的来说就是底层涉及扩容的行为就需要注意迭代器失效的问题.
场景2删除
void test()
{my_room::vectorint arr;for(int i 0; i 10; i) //存入1到10{arr.push_back(i1);}my_room::vectorint::iterator start arr.begin(); //指向第一个元素1while(start ! arr.end()) //预期删除所有元素{arr.erase(start); //------error代码请勿模仿}cout arr.size(); //看看有没有删完,但实际上在vs中直接报错.
}本来预期的是start一开始指向第一个元素,删除之后,剩下的元素往前移,然后继续删直到删完. 但是实际上删除行为同样也有迭代器失效的风险. 迭代器失效解决方案
我们知道在使用vector时当接口涉及扩容问题或者删除问题时会有迭代器失效的问题. 解决办法就是使用之前对迭代器重新赋值.
void test()
{my_room::vectorint arr;for(int i 0; i 10; i){arr.push_back(i1);}my_room::vectorint::iterator old_back arr.end()-1; arr.reserve(1000);old_back arr.end()-1;cout *old_back endl; //程序正常运行
}void test()
{my_room::vectorint arr;for(int i 0; i 10; i) {arr.push_back(i1);}my_room::vectorint::iterator start arr.begin();while(start ! arr.end()){start arr.erase(start); }cout arr.size(); //程序正常运行
}希望本片文章对您有帮助请点赞支持一下吧
