做中东服装有什么网站,制作网页总结,专业网站建设设计公司,刷网站流量有用吗一、常用接口
reverse逆置 sort排序#xff08;默认升序#xff09; 仿函数greaterint merge合并#xff0c;可以全部合并#xff0c;也可以一部分合并 unique#xff1a;去重#xff08;先排序#xff0c;再去重#xff09; remove#xff1a;删除e值#…一、常用接口
reverse逆置 sort排序默认升序 仿函数greaterint merge合并可以全部合并也可以一部分合并 unique去重先排序再去重 remove删除e值而不是erase的pos位置删 splice粘接其实就是transform转移 把某个位置i转移到当前链表的某个position之前 list的sort效率很低底层用归并但是数据访问很低因为是链表 vectror的sort更好一些因为是连续的空间
二、迭代器封装问题 原生指针就是天生的迭代器但是前提是物理空间是连续的 为什么 因为解引用就是该数据就是下一个数据 但是如果空间是不连续的就会出问题
例如list的原生指针就不能作为迭代器因为不符合预期 因为list的原生指针式list*但是list*是错误的因为不是连续的空间 解引用list*就是在原来地址位置向后移动一个list类型大小的距离指向该位置 但是因为不是连续的空间所以移动后的list*并不是下一个节点的地址 那怎么办呢 改造一下 我们用一个类去封装这个原生指针然后用这个类去控制这个原生指针 重载list为移动到下一个节点的位置 需要处理的是这个部分
用类封装一个原生指针这个原生指针也是一个模板 然后重定义这个原生指针为iterator 也就是说这个itrator就是一个原生指针 这个原生指针也是一个模板 那么当我们传入任意类型时原生指针模板就会自动推导出其对应的指针 只是这个指针取了一个别名叫做iterator即迭代器 这就充分利用了类型的内涵 也就是说此处的迭代器底层还是一个指针 但是这个指针的行为不符合我们的预期 所以我们需要封装重载行为
指针是内置类型 前置和后置是如何判断的呢 因为函数重载只看参数列表返回值不影响 所以在后置的重载参数列表加一个占位参数int 这样就会区别两个函数 迭代器比较就是比较指针指针就是地址。地址相等迭代器相等否则不等 iterator的特点是不管底层是什么 三、list模拟实现原码
insert 参数为iterator 找到当前的节点 记录前后插入即可
erase参数pos也是iterator指针 删除节点后当前节点的指针1iterator失效 所以要更新iterator 返回下一个节点的指针
pop_back删除--end() end是head是头节点
resize尾删和尾插
#pragma once
#includeassert.h
#includeiostream
using namespace std;namespace myspace
{//节点template class Tstruct list_node{list_node(const T val 0):_date(val), _next(nullptr), _prev(nullptr){}list_nodeT* _next;list_nodeT* _prev;T _date;};//迭代器template class T, class Ref, class ptrstruct list_iterator{typedef list_nodeT node;typedef list_iteratorT, Ref, ptr self;//模板推导list_iterator(node* node):_node(node){}//itself operator(){_node _node-_next;return *this;}//itself operator(int){self tmp _node;_node _node-_next;return tmp;}//--itself operator--(){_node _node-_prev;return *this;}//it--self operator--(int){self tmp _node;_node _node-_prev;return tmp;}//operatorT operator*(){return _node-_date;}T* operator-(){return _node-_date;}bool operator(const self it){return _node it._node;}bool operator!(const self it){return _node ! it._node;}node* _node;};//反向迭代器template class T, class Ref, class ptrstruct list_reverse_iterator{typedef list_nodeT node;typedef list_reverse_iteratorT, Ref, ptr self;//模板推导list_reverse_iterator(node* node):_node(node){}//itself operator(){_node _node-_prev;return *this;}//itself operator(int){self tmp _node;_node _node-_prev;return tmp;}//--itself operator--(){_node _node-_next;return *this;}//it--self operator--(int){self tmp _node;_node _node-_next;return tmp;}//operatorT operator*(){node* tmp _node-_prev;_node _node-_prev;return tmp-_date;}T* operator-(){node* tmp _node-_prev;_node _node-_prev;return tmp-_date;}bool operator(const self it){return _node it._node;}bool operator!(const self it){return _node ! it._node;}node* _node;};//一般对象的iterator和const对象的const_iterator//由于两者对应的实现不同因此一般的方式是写两个类//但是二者的区别只有*引用和-引用两者的不同//所以如果要书写两个类显的臃肿//所以可以使用模板//在需要的地方使用模板推导template class Tclass list{typedef list_nodeT node;public:typedef list_iteratorT, T, T* iterator;//一般对象的iteratortypedef list_iteratorT, const T, const T* const_iterator;//const对象的iteratortypedef list_reverse_iteratorT, T, T* reserve_iterator;//reserve_iteratorvoid empty_init(){node* newnode new node;newnode-_next newnode;newnode-_prev newnode;this-_head newnode;_size 0;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}bool empty(){return size() 0;}size_t size(){return _size;}list(){empty_init();}//lt1(lt2)//需要重新搞出一个新的list//(this指针就是lt1)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}~list(){clear();delete _head;_head nullptr;}iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}reserve_iterator rbegin(){return _head;}reserve_iterator rend(){return _head-_next;}//void swap(const listT lt)//{// std::swap(_head,lt._head);// std::swap(lt._size, _size);//}void push_back(const T val){insert(_head, val);}void push_front(const T val){insert(begin(), val);}void pop_back(){erase(_head-_prev);}void pop_front(){erase(begin());}void insert(iterator pos, const T val){node* tmp new node(val);node* next pos._node;node* prev pos._node-_prev;prev-_next tmp;tmp-_prev prev;next-_prev tmp;tmp-_next next;_size;}iterator erase(iterator pos){if (_size 0)return nullptr;node* cur pos._node;node* next cur-_next;node* prev cur-_prev;next-_prev prev;prev-_next next;delete cur;pos nullptr;--_size;return next;}private:node* _head;size_t _size;};//打印const对象void print(const listint clt){listint::const_iterator it clt.begin();while (it ! clt.end()){cout *it ;}cout endl;}//正常的增删改void test1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.insert(lt.begin(), 10);//lt.erase(lt.begin());lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}void test2(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.clear();listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout lt.size() endl;cout endl;}void test3(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;cout lt.empty() endl;}void test4(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);//listint::const_iterator it lt.begin();//while (it ! lt.end())//{// cout *it ;// it;//}cout endl;cout lt.empty() endl;}void print_list(const listint clt){//const对象的迭代器//const_iterator迭代器是一个单独的对象//为了区别于一般对象单独搞了一个const_iterator类//这个const_iterator类的目的在于可以正常进行遍历但是不能对内部的内容进行修改//因为实现方法不同一个类无法实现因此可以考虑使用模板listint::const_iterator it clt.begin();while (it ! clt.end()){//*it 10;cout *it ;it;}cout endl;}void test5(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_front(100);//lt.erase(lt.end());lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_front();listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}void test6(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint lt2(lt);listint lt3;lt3.push_back(10);lt3.push_back(11);lt3.push_back(12);lt3.push_back(13);//lt3.swap(lt2);listint::iterator it lt3.begin();while (it ! lt3.end()){cout *it ;it;}cout endl;}void test7(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::reserve_iterator rlt lt.rbegin();while (rlt ! lt.rend()){cout *rlt ;}cout endl;}}
四、相关细节
什么时候用struct什么时候用class 数据都是共有的时候就可以使用struct
模拟实现的时候需要定义一个自己的命名空间防止和库内冲突 将指针类型设置为模板因为要支持不同数据的list
typedef ListNodeT node #意为将节点设置为模板 但是为了便于理解我们编写代码的时候还是使用node便于理解 但是实际上这个node其实是一个模板我们用了一个typedef宏替换实现的 创建一个新节点的时候也是直接new node 这样就会直接开辟一个新空间节点出来一个模板类型的空间节点
模板的理解很简单 就是多了一个templateclass T而已 然后将对应的东西设置为T再typedef就是了 例如我要将list的节点设置为模板那么 typedef ListNodeT node 节点设置为模板ListNodeT 换名字typedef ListNodeT node 不要把模板看的这么复杂 也不要吧typedef看的太复杂 list中at会检查越界[]不会检查
