高端网站建设推来客地址,成都旅游必去的地方,宁波网站推广优化公司怎么样,扁平网站配色目录
前言#xff1a;
1.创建节点
2.普通迭代器的封装
3.反向迭代器的封装
为什么要对正向迭代器进行封装#xff1f;
4.const迭代器
5.构造函数
6.拷贝构造
7.赋值重载
8.insert
9.erase
10.析构
11.头插头删#xff0c;尾插尾删
12.完整代码简单测试
总结
1.创建节点
2.普通迭代器的封装
3.反向迭代器的封装
为什么要对正向迭代器进行封装
4.const迭代器
5.构造函数
6.拷贝构造
7.赋值重载
8.insert
9.erase
10.析构
11.头插头删尾插尾删
12.完整代码简单测试
总结 前言
模拟实现list本篇的重点就是由于list是一个双向循环链表结构所以我们对迭代器的实现不能是简单的指针的--了因为我们知道链表的存储不一定是连续的所以直接--是链接不起来节点的所以我们要对迭代器也就是对节点的指针进行封装。结尾会附上完整的代码。 1.创建节点 templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _data;list_node(const T x T())//这里不给缺省值可能会因为没有默认构造函数而编不过:_prev(nullptr),_next(nullptr),_data(x){}};注意给缺省值这样全缺省就会被当做默认构造了不会因为没有默认构造而报错。
我们实现的list是带哨兵位的它同时是迭代器的end因为是双向循环的list。 2.普通迭代器的封装 templateclass T,class Ref,class Ptrstruct _list_iterator{typedef list_nodeT node;typedef _list_iteratorT, Ref, Ptr self;node* _node;//对迭代器也就是节点的指针进行封装因为list迭代器是不能直接的_list_iterator(node* n):_node(n){}Ref operator*()//返回的必须是引用不然改变不了外面的对象的成员,要支持对自己解引用改变值就要用应用{return _node-_data;}Ptr operator-(){return (_node-_data);//返回地址再解引用直接访问数据}self operator(){_node _node-_next;return *this;}self operator(int){self tmp(*this);//默认的拷贝构造可以因为没有深拷贝_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}};注意list是双向迭代器可以--不能- 这里对迭代器的实现就如我们开始所说的 迭代器的实现就是使用节点的指针实现的而我们不能直接对list创建出的节点进行--所以要进行一层封装然后再对节点指针初始化。
重载解引用时要注意返回的是引用不然对自己解引用的时候返回值如果是临时的是改变不了内部的data的。
对于箭头的解引用是为了支持这样的场景
struct AA{int _a1;int _a2;AA(int a10,int a20):_a1(a1),_a2(a2){}};void test_list2(){listAA lt;lt.push_back(AA(1,1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));listAA::iterator it lt.begin();while (it ! lt.end()){//cout (*it)._a1 (*it)._a2endl;cout it-_a1 it-_a2 endl;//面对这样的类型需要重载-,.也可以访问但是有点别扭it;}cout endl;}迭代器遇到箭头返回对象的地址也就是节点数据的地址再解引用找到成员。或者说node中的data就是存放的是对象也就是用来初始化的数据然后重载的-拿到对象的地址再-去访问里面的成员变量_a1。
对于前置后置与--前置就返回对象的引用是传引用返回后置需要进行拷贝给一个临时的对象再对调用对象--返回的是tmp也就是没有改变的对象是传值返回。注意区分前置后置后置要加上参数int。 3.反向迭代器的封装
namespace my_iterator
{templateclass Iterator,class Ref,class Ptrstruct ReverseIterator{typedef ReverseIteratorIterator,Ref,Ptr self;Iterator _cur;ReverseIterator(Iterator it):_cur(it){}Ref operator*(){Iterator tmp _cur;//因为要--而解引用是不能改值的所以用tmp改并返回--tmp;return *tmp;}Ptr operator-(){return operator*();//this-operator*()}self operator(){--_cur;//直接的--就能直接改了所以可以直接返回原对象--(this-_cur)return *this;}self operator--(){_cur;return *this;}bool operator!(const self s){return _cur ! s._cur;}};
}
第一个模版参数就是任意类型的迭代器区间因为我们实现反向迭代器需要现有正向迭代器。
一样的不能直接--所以进行一层封装此时_cur就指向传的迭代器的位置。
对解引用的重载一样是要返回引用不然返回的是一个临时的变量对自己解引用就没用了也只有返回的是引用才能修改。例如我们要传的是begin那反向迭代器就应该从哨兵位开始所以要先对传过来的迭代器进行--。
箭头就是返回当前位置迭代器的地址所以是直接复用上面的。
--与正向的迭代器相反而_cur的类型就是传过来的迭代器类型--会调用传过来迭代器类型的重载。 为什么要对正向迭代器进行封装 4.const迭代器 typedef list_nodeT node;
public:typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;typedef ReverseIteratoriterator,T,T* reverse_iterator;typedef ReverseIteratoriterator, const T, const T* const_reverse_iterator;const_iterator begin() const//本身const迭代器是让迭代器指向的内容不能修改但是这样用const修饰迭代器本身也不能修改了{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);} 提供const版本供const修饰的对象调用防止权限的放大。
那为什么提供完const版本了const版本已经可以供普通迭代器与const迭代器使用还单独提出来这个版本和因为const迭代器还需要迭代器也就是节点指针指向的内容不能修改。例如it是const类型迭代器的对象*it就可以it也可以但是*it就不可以。 5.构造函数 void empty_Init(){_head new node;_head-_next _head;_head-_prev _head;}list(){empty_Init();}templateclass Iteratorlist(Iterator first, Iterator end){empty_Init();//别忘加上哨兵位没有哨兵位识别不了endwhile (first ! end){push_back(*first);first;//这里的first会调用重载的因为传过来的是一个迭代器}}哨兵位是空的不放数据但是哨兵位是正向迭代器的end要加上。
默认无参构造就只有哨兵位提供的迭代器的构造也要有哨兵位。
first不用担心first是迭代器类型的所以会调用迭代器的。 6.拷贝构造 //传统的拷贝构造//list(const listT lt)//{// empty_Init();// for (auto e : lt)// {// push_back(e);//this-push_back(e)// }//}void swap(listT tmp)//要使用库中的swap而库中的swap就不带const况且交换的是头节点const修饰的就不能修改指向{std::swap(_head, tmp._head);}//现代的拷贝构造list(const listT lt){empty_Init();listT tmp(lt.begin(), lt.end());//为什么还要多一个变量因为下面swap的参数没有const而拷贝构造要加constswap(tmp);//this-swap(tmp)}拷贝构造直接使用库中的swap交换头节点也就是哨兵位的指向就行因为链表后面的关系都通过头节点找到所以也就相当于都交换了。
注意库中swap的参数 7.赋值重载 listT operator(listT lt)//参数不能使用引用使用引用再使用swap交换原来赋值的值就被改了{swap(lt);return *this;}一样是使用库中的swap但是赋值的参数不能是引用例如L1L3用引用再加上使用swap交换头节点的指向L3就被改了我们要求的是赋值是不能改变赋过来的对象的内置类型也是ab。 8.insert void insert(iterator pos,const T x){node* cur pos._node;node* prev cur-_prev;node* newnode new node(x);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;}链接节点即可注意插入的值可能是任意类型所以要用模版参数并且带上const与引用防止是内置类型的值是const传过来权限放大。
插入pos位置也就是在pos前和pos位置之间插入。 9.erase iterator erase(iterator pos){assert(pos ! end());node* cur pos._node;node* prev cur-_prev;node* next cur-_next;prev-_next next;next-_prev prev;delete pos._node;return iterator(next);}注意删除完返回删除数据的下一个迭代器位置。
删除就是找前找后删除节点链接前后。
_node是new出来的注意配套使用。 10.析构
void clear()
{iterator it begin();while (it ! end()){it erase(it);//删除后返回的是下一个数据的位置所以循环就走起来了}
}~list()
{clear();delete _head;_head nullptr;
}
注意迭代器的erase删除后返回的是删除数据的下一个迭代器位置所以用it接收就不怕迭代器失效了同时循环也走起来了。 11.头插头删尾插尾删 void push_back(const T x){/*node* tail _head-_prev;node* newnode new node(x);tail-_next newnode;newnode-_prev tail;_head-_prev newnode;newnode-_next _head;*/insert(end(), x);}void push_front(const T x){insert(begin(),x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}直接复用即可。 12.完整代码简单测试
封装的反向迭代器
#pragma oncenamespace my_iterator
{templateclass Iterator,class Ref,class Ptrstruct ReverseIterator{typedef ReverseIteratorIterator,Ref,Ptr self;Iterator _cur;ReverseIterator(Iterator it):_cur(it){}Ref operator*(){Iterator tmp _cur;//因为要--而解引用是不能改值的所以用tmp改并返回--tmp;return *tmp;}Ptr operator-(){return operator*();}self operator(){--_cur;//直接的--就能直接改了所以可以直接返回原对象return *this;}self operator--(){_cur;return *this;}bool operator!(const self s){return _cur ! s._cur;}};
}
#pragma once
#include my_iterator.h#include iostream
#include assert.h
#include listusing namespace my_iterator;
using namespace std;namespace my_list
{templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _data;list_node(const T x T())//这里不给缺省值可能会因为没有默认构造函数而编不过:_prev(nullptr),_next(nullptr),_data(x){}};templateclass T,class Ref,class Ptrstruct _list_iterator{typedef list_nodeT node;typedef _list_iteratorT, Ref, Ptr self;node* _node;//对迭代器也就是节点的指针进行封装因为list迭代器是不能直接的_list_iterator(node* n):_node(n){}Ref operator*()//返回的必须是引用不然改变不了外面的对象的成员,要支持对自己解引用改变值就要用应用{return _node-_data;}Ptr operator-(){return (_node-_data);//返回地址再解引用直接访问数据}self operator(){_node _node-_next;return *this;}self operator(int){self tmp(*this);//默认的拷贝构造可以因为没有深拷贝_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const self s){return _node ! s._node;}bool operator(const self s){return _node s._node;}};templateclass Tclass list{typedef list_nodeT node;public:typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;typedef ReverseIteratoriterator,T,T* reverse_iterator;typedef ReverseIteratoriterator, const T, const T* const_reverse_iterator;void empty_Init(){_head new node;_head-_next _head;_head-_prev _head;}list(){empty_Init();}templateclass Iteratorlist(Iterator first, Iterator end){empty_Init();//别忘加上哨兵位没有哨兵位识别不了endwhile (first ! end){push_back(*first);first;//这里的first会调用重载的因为传过来的是一个迭代器}}//传统的拷贝构造//list(const listT lt)//{// empty_Init();// for (auto e : lt)// {// push_back(e);//this-push_back// }//}void swap(listT tmp)//要使用库中的swap而库中的swap就不带const况且交换的是头节点const修饰的就不能修改指向{std::swap(_head, tmp._head);}//现代的拷贝构造list(const listT lt){empty_Init();listT tmp(lt.begin(), lt.end());//为什么还要多一个变量因为下面swap的参数没有const而拷贝构造要加constswap(tmp);//this-swap(tmp)}listT operator(listT lt)//参数不能使用引用使用引用再使用swap交换原来赋值的值就被改了{swap(lt);return *this;}void clear(){iterator it begin();while (it ! end()){it erase(it);//删除后返回的是下一个数据的位置所以循环就走起来了}}~list(){clear();delete _head;_head nullptr;}iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);//哨兵位就是end}const_iterator begin() const//本身const迭代器是让迭代器指向的内容不能修改但是这样用const修饰迭代器本身也不能修改了{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}void push_back(const T x){/*node* tail _head-_prev;node* newnode new node(x);tail-_next newnode;newnode-_prev tail;_head-_prev newnode;newnode-_next _head;*/insert(end(), x);}void push_front(const T x){insert(begin(),x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos,const T x){node* cur pos._node;node* prev cur-_prev;node* newnode new node(x);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;}iterator erase(iterator pos){assert(pos ! end());node* cur pos._node;node* prev cur-_prev;node* next cur-_next;prev-_next next;next-_prev prev;delete pos._node;return iterator(next);}private:node* _head;};void print_list(const listint lt){listint::const_iterator it lt.begin();//不能直接这样写传递过来的this指针也是const listint*,权限放大了,要提供const版本while (it ! lt.end()){cout *it ;it;}cout endl;}void test_list1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();//调用默认的拷贝构造是浅拷贝但是可以让it也指向begin的位置while (it ! lt.end()){cout *it ;it;}cout endl;for (auto e : lt){cout e ;}cout endl;print_list(lt);}struct AA{int _a1;int _a2;AA(int a1 0, int a2 0):_a1(a1), _a2(a2){}};void test_list2(){listAA lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));listAA::iterator it lt.begin();while (it ! lt.end()){//cout (*it)._a1 (*it)._a2endl;cout it-_a1 it-_a2 endl;//面对这样的类型需要重载-,.也可以访问但是有点别扭it;}cout endl;}void test_list3(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);auto pos lt.begin();pos;lt.insert(pos, 20);for (auto e : lt){cout e ;}cout endl;lt.push_back(100);lt.push_front(1000);for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout e ;}cout endl;}void test_list4(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;lt.clear();for (auto e : lt){cout e ;}cout endl;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(40);for (auto e : lt){cout e ;}cout endl;}void test_list5(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout e ;}cout endl;listint lt2(lt);for (auto e : lt2){cout e ;}cout endl;listint lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);for (auto e : lt3){cout e ;}cout endl;lt2 lt3;for (auto e : lt2){cout e ;}cout endl;}void test_list6(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();//调用默认的拷贝构造是浅拷贝但是可以让it也指向begin的位置while (it ! lt.end()){(*it) * 2;cout *it ;it;}cout endl;listint::reverse_iterator rit lt.rbegin();while (rit ! lt.rend()){cout *rit ;rit;}cout endl;/*for (auto e : lt){cout e ;}cout endl;print_list(lt);*/}}总结
重点在迭代器与反向迭代器的的封装其它的内容与其它的容器大致相同。
