网站流量查询工具,免费户型图设计软件,外包建设网站,网站建设及推广服务公司目录 listlist概念 list 中的迭代器list迭代器知识const迭代器写法list访问自定义类型 附录代码 list
list概念 list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。list的底层是双向链表结构#xff0c;双向链表中每个元素… 目录 listlist概念 list 中的迭代器list迭代器知识const迭代器写法list访问自定义类型 附录代码 list
list概念 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向 其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高 效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率 更好。与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list 的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间 开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素) list 中的迭代器
有兴趣的可以直接跳转附录代码中里面几乎涵盖了所有的问题答案.
list迭代器知识 迭代器原理就是对原生指针的封装帮助我们更好的使用指针来对节点的内容进行访问。 迭代器目前学习的进度来看是分成普通迭代器和const迭代器。在对list的模拟实现过程中发现了许多新的迭代器知识点。
const迭代器写法
由于对迭代器封装后的代码重命名为typedef __list_iteratorT iterator; 所以下意识会认为const迭代器应该是这个样子的//typedef __list_const_iteratorT const_iterator; 实际上这是有问题的 因为const迭代器修饰的应该节点内部的数据不可以被修改而迭代器本身是可以前后移动来遍历链表。 而 const_iterator所表达的意思是T* const但是我们想要的是const T*。 这两者的区别便是前一个T* const可以修改节点内部数据信息但因为不可以修改地址所以不能遍历链表而后一个const T*不可以修改数据信息但是可以遍历链表。 要想办法实现const T* list中的const迭代器实际上是保证对信息不可修改所以只需要对读取信息的操作赋予控制是否为const属性的操作即为T* operator*()确保在某些时刻是const属性。所以可以在模板上对其进行特殊化操作 templateclass T, class Ref templateclass T, class Refstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT, Ref self;node* _node;__list_iterator(node* n):_node(n){}Ref operator*()//T* operator(){return _node-_data;}};templateclass Tclass list{typedef list_nodeT node;public:typedef __list_iteratorT, T iterator;//使用普通迭代器就更改Ref就好了typedef __list_iteratorT, const T const_iterator;在需要const迭代器时候传递const T而需要普通迭代器就直接传递T,这样不仅解决的繁琐的复用问题还能够满足使用。 list访问自定义类型 迭代器要么是原生指针要么是自定义类型对原生指针的封装在模拟指针的行为。 而访问自定义类型不能使用解引用操作而是使用访问操作符-,所以list库对访问自定义类型也做了对应的设置即重载operator-
但是因为要访问自定义类型就一棒子大打死就只能使用operator-来进行访问内部的函数大可以直接访问而复用又太过于繁琐了所以又新增了特殊的模板类控制是访问自定义类型还是访问内部函数 templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;node* _node;__list_iterator(node* n):_node(n){}Ptr operator-(){return _node-_data;}templateclass Tclass list{typedef list_nodeT node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;}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-_a2 ;it;}cout endl;}因此不仅仅可以访问是否为const属性的信息还可以控制访问是否为自定义类型的参数 附录代码
#pragma once#includeiostream
#includeassert.h
using namespace std;
namespace lby
{templateclass Tstruct list_node //节点的类//struct默认为公有不打算对内容进行限制就用struct{list_nodeT* _next;list_nodeT* _prev;T _data;list_node(const T x T()):_next(nullptr), _prev(nullptr), _data(x){}};//迭代器要么是原生指针要么是自定义类型对原生指针的封装在模拟指针的行为templateclass T, class Ref, class Ptr//使用普通迭代器就更改Ref就好了struct __list_iterator//封装的是迭代器而迭代器的本质是用一个类去封装这个 node*,即指针指向这个链表的头节点{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;node* _node;//注意节点的指针不属于迭代器只是让迭代器封装之后的一系列操作不支持释放释放是链表的事情迭代器只能使用节点不能释放节点__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 x)//传递的是迭代器中的x{return _node ! x._node;}bool operator(const self x){return _node x._node;}};/*templateclass Tstruct __list_const_iterator//封装的是迭代器而迭代器的本质是用一个类去封装这个 node*,即指针指向这个链表的头节点{typedef list_nodeT node;typedef __list_const_iteratorT self;node* _node;//注意节点的指针不属于迭代器只是让迭代器封装之后的一系列操作不支持释放释放是链表的事情迭代器只能使用节点不能释放节点__list_const_iterator(node* n):_node(n){}const T 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 x)//传递的是迭代器中的x{return _node ! x._node;}bool operator(const self x){return _node x._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 __list_const_iteratorT const_iterator;//typedef const iterator const_itrator;//绝对不可以这种方式const修饰的是地址 -- T* const而不是const T*iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}//iterator begin() const//这里有个问题既然是const指针那就应该是常量但是为什么你还能改变指向的位置//{// return iterator(_head-_next);//因为const指针修饰的是*this即this指针指向的内容它指向的内容是_head这个的指针// //即为修饰的是_head这个指针本身也就是说_head本身不能被改变它指向的内容是可以改变的// //但是与我们的预期不符因为const迭代器他是只读操作不允许改变内容如果他内容是可以改变的我为什么要使用const迭代器呢const迭代器与普通迭代器区别是const迭代器本身是可以修改的(可以前后移动去访问)但是const迭代器指向的内容是不可以修改的-- 要const T*不要T* const //}//iterator end() const//{// return iterator(_head); //}const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head new node;_head-_next _head;_head-_prev _head;}list(){empty_init();}templateclass Iteratorlist(Iterator first, Iterator last){empty_init();//先构造头节点while (first ! last){push_back(*first);//push_back 的前提是有哨兵位的头节点所以需要先构造头节点first;}}void swap(listT t){std::swap(_head, t._head);}list(const listT lt)//lt2(lt1){/*empty_init();//正常写法for (auto e : lt){push_back(e);}*/empty_init();listT tmp(lt.begin(), lt.end());//借助模板类进行复制后交换swap(tmp);}//lt1 lt3 listT operator(listT lt)//(listT lt)不能引用传引用因为会将原来的lt进行修改{swap(lt);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){it erase(it);//erase(it);//这个地方析构的值是返回的迭代器对象是it的拷贝不是it}}void push_back(const T x){//node* tail _head-_prev;//node* new_node new node(x);//需要node(list_nodeT)的构造函数//tail-_next new_node;//new_node-_prev tail;//new_node-_next _head;//_head-_prev new_node;insert(end(), x);}void push_front(const T x){insert(begin(), x);}void insert(iterator pos, const T x)//链表的迭代器插入数据不会失效因为pos指针指向的位置是不变的{node* cur pos._node;node* prev cur-_prev;node* new_node new node(x);prev-_next new_node;new_node-_prev prev;new_node-_next cur;cur-_prev new_node;}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator erase(iterator pos)//由于pos指针位置被析构了所以迭代器失效了{assert(pos ! end());node* prev pos._node-_prev;node* next pos._node-_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();while (it ! lt.end()){//(*it) * 2;//const不可修改cout *it ;it;}cout endl;}void test_list1(){const listint l;//const对象在定义时最开始不会赋给常值因为要初始化否则没办法进行初始化之后才会赋给const属性//const对象在定义的一瞬间不会给const属性listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;for (auto p : lt){cout p ;}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)._a2 ;cout it-_a1 , it-_a2 ;//由于函数重载了 - 所以本来应该是it--_a1,编译器优化了设置变成了it-_a1;//it.operator-()-_a1,it.operator-()返回的是T*T*-_a1就可以访问it;}cout endl;}void test_list3(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto p : lt){cout p ;}cout endl;auto pos lt.begin();pos;lt.insert(pos, 100);for (auto p : lt){cout p ;}cout endl;lt.push_front(200);lt.push_front(300);for (auto p : lt){cout p ;}cout endl;lt.push_back(400);lt.push_back(500);for (auto p : lt){cout p ;}cout endl;lt.pop_back();lt.pop_front();for (auto p : lt){cout p ;}cout endl;lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();for (auto p : lt){cout p ;}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 p : lt){cout p ;}cout endl;lt.clear();for (auto p : lt){cout p ;}cout endl;lt.push_back(10);lt.push_back(2);lt.push_back(30);lt.push_back(1);for (auto p : lt){cout p ;}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 p : lt){cout p ;}cout endl;listint lt2(lt);for (auto e : lt2){cout e ;}cout endl;}
}
