4.2.6

2、list迭代器3、list的构造4、list常用接口的实现4.1

list

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

list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。

list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单效。

与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。

与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

1.2

list中的接口比较多此处类似只需要掌握如何正确的使用然后再去深入研究背后的原理已达到可扩展的能力。

2、list迭代器

此处我们可暂时将迭代器理解成一个指针该指针指向list中的某个节点。

list我们都知道它不是连续的空间是我们将下一个位置的地址保存起来通过地址走到下一个因此我们需要重载一些运算符。

--前置后置

这里我们为list节点创建一个类后面直接使用这个类就可以了再写一个缺省的构造函数为后面开节点提供便利。

templateclass

T()):_pPre(nullptr),_pNext(nullptr),_val(val){}ListNodeT*

_pPre;ListNodeT*

nullptr):_pNode(pNode){}ListIterator(const

Self

value_type())构造的list中包含n个值为val的元素list()构造空的listlist(const

list

last){push_back(*first);first;}

iterator

函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数

size_t

函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list

position

position位置的元素swap交换两个list中的元素clear清空list中的有效元素

4.2.1

1、我们先new一个节点newnode并赋值为x这里就会去调用list节点类里面的构造函数

prev,

直接在尾部前插入即可。

end()返回的就是头结点头结点是哨兵位节点因此在end()前插就是尾插。

void

尾删也是复用erase代码就是删掉列表的最后一个节点erase(–end())。

void

}这里为什么–end()这里end()返回的是头结点因为要删除尾结点所以需要–end()才是真正的尾结点。

4.2.7

list的swap交换只要交换两个链表的头结点就可以因为是链式存储的更换头指针即可。

库中提供的交换直接复用就可以。

void

对于链表的clear我们需要释放掉每一个有效节点因此我们遍历一遍并复用erase。

void

前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。

因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。

int

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator

lt.begin();while

lt.end()){//这里如果先删掉了再去更新迭代器已经被失效影响了lt.erase(it);it;}return

}改正

lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator

lt.begin();while

lt.end()){//这里如果先删掉了再去更新迭代器已经被失效影响了lt.erase(it);}return

}6、list与vector对比

vector与list都是STL中非常重要的序列式容器由于两个容器的底层结构不同导致其特性以及应用场景不同其主要不同如下

vectorlist底

问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素效率O(N)插

除任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为O(1)空

率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭

效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使

景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问