东莞网站建设 熊掌号,百度下载安装app,莱芜论坛24小时主题帖,公司注册类型List list简介list基本框架list构造函数list_node结构体的默认构造list类的默认构造 push_back()iteartor迭代器迭代器里面的其他接口const迭代器通过模板参数实现复用operator-() insert()erase()clear()析构函数迭代器区间构造拷贝构造operator() list简介
- list可以在… List list简介list基本框架list构造函数list_node结构体的默认构造list类的默认构造 push_back()iteartor迭代器迭代器里面的其他接口const迭代器通过模板参数实现复用operator-() insert()erase()clear()析构函数迭代器区间构造拷贝构造operator() list简介
- list可以在常数范围内在任意位置进行插入和删除的序列式容器并且容器可以双向迭代。
- list底层是一个带头双向链表结构通过指针连接前一个和后一个元素。
- list支持在任意位置进行插入、删除元素效率更好。
- list不支持随机访问list基本框架
namespace xty
{//带头双向循环链表templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _data;};templateclass Tclass list{typedef list_nodeT node;private:node* _head;//头指针};
}list构造函数
我们实现一个无参构造函数但是在这之前我们需要做一些准备工作先实现一个申请list_node的构造函数在struct类里面实现。
list_node结构体的默认构造 //带头双向循环链表templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _data;//在创建list_node变量时自动调用构造list_node(const T val T()):_prev(nullptr),_next(nullptr),_data(val){}};为什么不使用class而使用struct呢 因为我们想达到这样一个目的想要让别人自由的访问自己的成员函数不做任何限制就用struct。而list_nodelist是要经常使用的因此使用struct修饰list_node比较方便。
list类的默认构造
仅仅申请一个空的头结点next都指向头 list(){//两种申请方法都可以//_head new list_nodeT_head new node;_head-next _head;_head-prev _head;//_head-_data已经在new的时候调用构造了}
push_back()
先记录一下尾结点插入更简单。 void push_back(const T x){//留记录尾结点node* tail _head-_prev;node* new_node new node(x);//传入x值tail-_next new_node;new_node-_next _head;_head-_prev new_node;new_node-_prev tail;}iteartor迭代器
整体框架 //iteartortemplateclass Tstruct __list_iterator{typedef list_nodeT node;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}T operator*(){return _node-_data;}//返回相应的迭代器__list_iteratorT operator(){_node _node-_next;return *this;}//是位置是否相等不是内容是否相等。bool operator!(__list_iteratorT x){return _node ! x._node;}};templateclass Tclass list{typedef list_nodeT node;public://迭代器重命名typedef __list_iteratorT iterator;public://仅仅申请一个空的头结点next都指向头list(){//两种申请方法都可以//_head new list_nodeT_head new node;_head-_next _head;_head-_prev _head;//_head-_data已经在new的时候调用构造了了}iterator begin(){iterator it(_head-_next);return it;}iterator end(){return iterator(_head);}语法细节理解
为什么把iterator和list进行单独封装写一块不好吗 首先list只会用到迭代器的begin()和end()函数。其他的像其实都是通过迭代器的对象调用的并不是list的对象调用的。把iterator从list中抽离出来不仅可以减少list的复杂性还能让人更加清楚迭代器其实也是一个模板它能被抽离出来用以实现各种数据结构的迭代而list内部的begin和end接口千篇一律。这样就达到的封装的目的所以还是分开写的好逻辑更清晰更容易维护。struct __list_iterator结构体里面为什么要写构造函数呢 在c里struct也被当做是类类里有构造函数很正常还可以有拷贝构造呢只不过struct默认是public的。这样我们在声明该类型的变量时函数会自动调用构造函数使该结构体的数据自动是被初始化过的。 xty::listint::iterator it lt.begin(); //调用对象需要用list//xty::listint::iterator it(lt.begin()); //调用对象需要用listwhile (it ! lt.end()){cout *it endl;it;}写了构造函数之后第二种声明方式也是可以的。而第一种方式其实调用的是拷贝构造函数但是编译器给优化成了拷贝构造我们没有写拷贝构造编译器会调用默认的拷贝构造是一个浅拷贝。但是我们不是经常说浅拷贝会造成析构问题这里为什么不会因为我们没有写析构函数而且析构函数。为什么不写析构函数呢因为没有什么可以析构的函数的结点是list里的内容不需要迭代器的析构函数管因此我们不写析构函数。
迭代器返回的是迭代器的类型。注意_list_iterator是类名_list_iterator才是类型list里面的begin要返回迭代器类型然而怎么由指针转化成迭代器类型呢要利用迭代器的构造函数来返回。
迭代器里面的其他接口 bool operator(const __list_iteratorT x){return _node x._node;}//i__list_iteratorT operator(int){__list_iteratorT tem(*this);_node _node-_next;return tem;}__list_iteratorT operator--(){_node _node-_prev;return *this;}__list_iteratorT operator--(int){__list_iteratorT tem(*this);_node _node-_prev;return tem;}语法细节理解
注意迭代器传进来的参数基本上都是迭代器如果不更改最好加上const和。如果命名空间冲突注意在函数声明和定义的时候也要加上空间名。
void Print(xty::listint lt);我们发现__list_iterator 有点长我们重命名一下。 //iteartortemplateclass Tstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT self;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}T operator*(){return _node-_data;}//返回相应的迭代器self operator(){_node _node-_next;return *this;}//是位置是否相等不是内容是否相等。bool operator!(const __list_iteratorT x){return _node ! x._node;}bool operator(const __list_iteratorT x){return _node x._node;}//iself operator(int){self tem(*this);_node _node-_next;return tem;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tem(*this);_node _node-_prev;return tem;}};const迭代器
要实现const迭代器只需要再写一个const类即可。 记住是指针可以修改但是内容不可以修改因此不能在this那加const。 //迭代器重命名typedef __list_iteratorT iterator;typedef const__list_iteratorT const_iterator;public:const_iterator begin()const{const_iterator it(_head-_next);return it;}const_iterator end()const{return const_iterator(_head);}list里面的迭代器修改仅仅需要typedef一下然后将构造函数改成所需要的const类型即可。 而我们需要再实现一个const类型的iterator templateclass Tstruct const__list_iterator{typedef list_nodeT node;typedef const__list_iteratorT self;node* _node;//成员变量//构造函数const__list_iterator(node* x):_node(x){}const T operator*() //值不仅可以修改{return _node-_data;}//返回相应的迭代器self operator() //指针可以修改{_node _node-_next;return *this;}//是位置是否相等不是内容是否相等。bool operator!(const self x)const{return _node ! x._node;}bool operator(const self x)const{return _node x._node;}//iself operator(int) //指针可以修改{self tem(*this);_node _node-_next;return tem;}self operator--() //指针可以修改{_node _node-_prev;return *this;}self operator--(int) //指针可以修改{self tem(*this);_node _node-_prev;return tem;}};问题代码写完之后我们发现实际上只有operator*()的返回值加了const其他的地方没有改因此我们利用模板参数赋用解决问题。
通过模板参数实现复用 templateclass T,class Refstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT,Ref self;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}Ref operator*(){return _node-_data;}...}templateclass Tclass list{typedef list_nodeT node;public://迭代器重命名typedef __list_iteratorT, T iterator;typedef __list_iteratorT,const T const_iterator;public://仅仅申请一个空的头结点next都指向头list(){//两种申请方法都可以//_head new list_nodeT_head new node;_head-_next _head;_head-_prev _head;//_head-_data已经在new的时候调用构造了了}}通过增加类模板参数这种问题被很巧妙的解决了。请好好体会
operator-()
当我们遇到自定义类型数据链表时访问数据就会比较麻烦。 struct AA{int _a1;int _a2;AA(int a1 0, int a2 0):_a1(a1), _a2(a2){}};void test_aa(){xty::listAA lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));lt.push_back(AA(4, 4));xty::listAA::iterator it lt.begin();while (it ! lt.end()){cout (*it)._a1 : (*it)._a2 endl;it;}}如上例子所示cout方式在这里很是别扭因为it是迭代器我们能不能通过重载-来访问这样的数据呢 显然是可以的如下 T* operator-(){return (_node-_data);}所以我们通过如下方式打印链表的数据 xty::listAA::iterator it lt.begin();while (it ! lt.end()){//cout (*it)._a1 : (*it)._a2 endl;cout it-_a1 : it-_a2 endl;it;}但是这个代码是不是有一点别扭没看出来的话我再打印一次 //两种打印方式一样cout it-_a1 : it-_a2 endl;cout it.operator-()-_a1 : it.operator-()-_a2 endl;解释之所以出现这样的原因是因为编译器自动把两个连续的-优化成一个-防止观感上的差异这样设计能让人立马看出这个其实是在访问AA的数据。 为了适应const和非const两种迭代器我们再设计一个模板参数。如下实例 //iteartortemplateclass T,class Ref, class Ptrstruct __list_iterator{typedef list_nodeT node;typedef __list_iteratorT,Ref,Ptr self;node* _node;//成员变量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;public:
insert() //在pos位置前插入,返回插入位置的迭代器iterator insert(iterator pos, const T x){node* new_node new node(x);node* cur pos._node;node* prev cur-_prev;prev-_next new_node;new_node-_prev prev;new_node-_next cur;cur-_prev new_node;return iterator(cur);}erase()
返回删除元素的下一个位置的迭代器。 iterator erase(iterator pos){//不能删头assert(pos._node!_head);node* cur pos._node;node* prev cur-_prev;prev-_next cur-_next;cur-_next-_prev prev;delete cur;return iterator(prev-_next)}注意删除元素后pos位置的数据就被删除了会产生迭代器失效问题如果再使用pos需要重新赋值。
clear()
清空list的内容可以借助迭代器和erase()来删除。 void clear(){iterator it begin();while (it ! end()){it erase(it);//erase(it);}}析构函数
结合clear()来编写。 ~list(){clear();delete _head;_head nullptr;}迭代器区间构造
因为迭代器区间构造也需要一个头结点所以我们方便复用又定义了一个初始化函数具体改动如下 list(){empty_init();//两种申请方法都可以//_head new list_nodeT//_head new node;//_head-_next _head;//_head-_prev _head;//_head-_data已经在new的时候调用构造了了}void empty_init(){_head new node;_head-_next _head;_head-_prev _head;}templateclass Iteratorlist(Iterator first, Iterator last){empty_init();while (first ! last){push_back(*first);first;}}拷贝构造
提供了两种方法第一种方法效率较低第二种利用swap提高了效率。 lt2(lt)//list(const listT lt)//{// empty_init();// for (auto e : lt)// {// push_back(e);// }//}void swap(listT tem){std::swap(_head, tem._head);}list(const listT lt){empty_init();//初始化thislistT tem(lt.begin(), lt.end());swap(tem);}operator()
实现较为简单。
//注意这里不能传引用listT operator(listT lt){swap(lt);return *this;} 最后一个问题
const listint lt;这行代码能调用构造函数吗 答案是肯定的因为变量在最开始是没有const属性的定义好了以后才有const属性。否则const都没法定义出来了。
