st简介list基本框架list构造函数list_node结构体的默认构造list类的默认构造

push_back()iteartor迭代器迭代器里面的其他接口const迭代器通过模板参数实现复用operator-()

insert()erase()clear()析构函数迭代器区间构造拷贝构造operator()

list简介

list可以在常数范围内在任意位置进行插入和删除的序列式容器并且容器可以双向迭代。

list底层是一个带头双向链表结构通过指针连接前一个和后一个元素。

list不支持随机访问list基本框架

我们实现一个无参构造函数但是在这之前我们需要做一些准备工作先实现一个申请list_node的构造函数在struct类里面实现。

Tstruct

_data;//在创建list_node变量时自动调用构造list_node(const

val

T()):_prev(nullptr),_next(nullptr),_data(val){}};为什么不使用class而使用struct呢

因为我们想达到这样一个目的想要让别人自由的访问自己的成员函数不做任何限制就用struct。

而list_nodelist是要经常使用的因此使用struct修饰list_node比较方便。

new

_head;//_head-_data已经在new的时候调用构造了}

push_back()

_node;//成员变量//构造函数__list_iterator(node*

x):_node(x){}T

_node-_data;}//返回相应的迭代器__list_iteratorT

operator(){_node

iterator;public://仅仅申请一个空的头结点next都指向头list(){//两种申请方法都可以//_head

new

_head;//_head-_data已经在new的时候调用构造了了}iterator

begin(){iterator

首先list只会用到迭代器的begin()和end()函数。

其他的像其实都是通过迭代器的对象调用的并不是list的对象调用的。

把iterator从list中抽离出来不仅可以减少list的复杂性还能让人更加清楚迭代器其实也是一个模板它能被抽离出来用以实现各种数据结构的迭代而list内部的begin和end接口千篇一律。

这样就达到的封装的目的所以还是分开写的好逻辑更清晰更容易维护。

struct

在c里struct也被当做是类类里有构造函数很正常还可以有拷贝构造呢只不过struct默认是public的。

这样我们在声明该类型的变量时函数会自动调用构造函数使该结构体的数据自动是被初始化过的。

lt.begin();

//调用对象需要用list//xty::listint::iterator

it(lt.begin());

endl;it;}写了构造函数之后第二种声明方式也是可以的。

而第一种方式其实调用的是拷贝构造函数但是编译器给优化成了拷贝构造我们没有写拷贝构造编译器会调用默认的拷贝构造是一个浅拷贝。

但是我们不是经常说浅拷贝会造成析构问题这里为什么不会因为我们没有写析构函数而且析构函数。

为什么不写析构函数呢因为没有什么可以析构的函数的结点是list里的内容不需要迭代器的析构函数管因此我们不写析构函数。

迭代器返回的是迭代器的类型。

注意_list_iterator是类名_list_iterator才是类型list里面的begin要返回迭代器类型然而怎么由指针转化成迭代器类型呢要利用迭代器的构造函数来返回。

bool

operator--(int){__list_iteratorT

tem(*this);_node

注意迭代器传进来的参数基本上都是迭代器如果不更改最好加上const和。

如果命名空间冲突注意在函数声明和定义的时候也要加上空间名。

void

_node;//成员变量//构造函数__list_iterator(node*

x):_node(x){}T

记住是指针可以修改但是内容不可以修改因此不能在this那加const。

//迭代器重命名typedef

const_iterator;public:const_iterator

it;}const_iterator

const_iterator(_head);}list里面的迭代器修改仅仅需要typedef一下然后将构造函数改成所需要的const类型即可。

templateclass

_node;//成员变量//构造函数const__list_iterator(node*

x):_node(x){}const

tem;}};问题代码写完之后我们发现实际上只有operator*()的返回值加了const其他的地方没有改因此我们利用模板参数赋用解决问题。

templateclass

_node;//成员变量//构造函数__list_iterator(node*

x):_node(x){}Ref

const_iterator;public://仅仅申请一个空的头结点next都指向头list(){//两种申请方法都可以//_head

new

_head;//_head-_data已经在new的时候调用构造了了}}通过增加类模板参数这种问题被很巧妙的解决了。

请好好体会

operator-()

endl;it;}}如上例子所示cout方式在这里很是别扭因为it是迭代器我们能不能通过重载-来访问这样的数据呢

operator-(){return

(_node-_data);}所以我们通过如下方式打印链表的数据

lt.begin();while

endl;it;}但是这个代码是不是有一点别扭没看出来的话我再打印一次

//两种打印方式一样cout

endl;解释之所以出现这样的原因是因为编译器自动把两个连续的-优化成一个-防止观感上的差异这样设计能让人立马看出这个其实是在访问AA的数据。

为了适应const和非const两种迭代器我们再设计一个模板参数。

如下实例

T,class

pos){//不能删头assert(pos._node!_head);node*

cur

iterator(prev-_next)}注意删除元素后pos位置的数据就被删除了会产生迭代器失效问题如果再使用pos需要重新赋值。

clear()

因为迭代器区间构造也需要一个头结点所以我们方便复用又定义了一个初始化函数具体改动如下

list(){empty_init();//两种申请方法都可以//_head

new

_head;//_head-_data已经在new的时候调用构造了了}void

empty_init(){_head

last){push_back(*first);first;}}拷贝构造

提供了两种方法第一种方法效率较低第二种利用swap提高了效率。

lt2(lt)//list(const

lt){empty_init();//初始化thislistT

tem(lt.begin(),

lt.end());swap(tem);}operator()

//注意这里不能传引用listT

答案是肯定的因为变量在最开始是没有const属性的定义好了以后才有const属性。

否则const都没法定义出来了。