C++笔记9•list•

容器之list

1.list的介绍

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

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

(3).优缺点

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

list 最大的 缺陷 ：不支持任意位置的随机访问，比如：要访问 list的第5 个元素，必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置，在这段位置上迭代需要线性的时间开销。

2. list的使用

list官方文档介绍：

构造函数、拷贝构造、析构函数、迭代器、容量空间、增删查改接口

3.list迭代器失效 

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

注意： list迭代器的实现 与string和vector不一样，list的迭代器是将指针封装在一个结构体中，传统的只用一个指针来表示list迭代器，不足以实现list迭代器的功能，只要还是因为list是个链表，里面是一个个节点组成的，需要从堆上申请，造成 在逻辑上是连续的，在物理结构上不⼀定连续。  传统的指针++操作，就直接到下一个指针了，但是list如果单纯++，是不能指向下一个指针的，需要进行运算符重载来实现这个功能。

void TestListIterator()
{
 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 auto it = l.begin();
 while (it != l.end())
 {
 // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
 l.erase(it); 
 ++it;
 }
}

//解决方案：
void TestListIterator()
{
 int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 list<int> l(array, array+sizeof(array)/sizeof(array[0]));
 auto it = l.begin();
 while (it != l.end())
 {
 // erase()函数执行后，it所指向的节点已被删除，因此it无效，erase()返回值是个迭代器 返回下一个节点的迭代器。在下一次使用it时，必须先给其赋值
 it=l.erase(it); 
 }
}

※注意：防止迭代器失效解决办法：在使用前，对迭代器重新赋值即可。