STL之list容器

list的介绍

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

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

3.vector的优点：支持随机访问，间接的就支持了排序/二分查找/堆排序等

               缺点：1.头部和中部的插入效率低，需要挪动数据

                          2.插入数据空间不够需要增容，增容需要开新空间，拷贝数据，释放旧空间

    list的优点：没有增容代价，且任意位置插入都是0（1）；

              缺点：不支持随机访问，得从头开始遍历查找到后面的元素

所以list和vector是互补的存在

注意：forward_list是单向链表

list的常见函数接口

构造函数:

 

与vector类似

第一个构造空的，第二个构造4个结点，每个都是100，第四个拷贝构造函数

第三个不用记，直接使用第四个去拷贝就行

Capacity接口 ：

根据前面的vector和string的学习，相信大家都很熟悉了

empty():判断是否为空

size():返回结点数

相比之下，list没有capacity()，因为它是来一个结点就开一个

 Modifiers接口：

push_front():头插

pop_front():头删 

push_back():尾插

pop_back():尾删

insert():在pos位置插入val

erase()：删除pos位置的元素

swap():交换两个list中的元素

clear()：清空元素，clear 会遍历链表，为每个节点调用析构函数，并释放节点所占用的内存。

resize():在这里不常用，与之前容器的resize一样

Element access接口：

返回头部和尾部元素

operations接口

splice()：转移链表 

sort():排序

reverse():逆置链表

iterator接口：

重点谈迭代器

从支持操作接口的角度分迭代器类型

单向（forward_list）   双向（list）  随机（vector）

it只能++                  it能++--             it能++--也能it+=5，直接跳几个

从使用场景的角度分迭代器类型

（正向迭代器+反向迭代器）+（const修饰迭代器+普通迭代器） 

迭代器失效：

可简单的将迭代器理解成指针（后面会有讲解迭代器如何实现），迭代器失效即迭代器所指向的结点无效，即该结点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除结点的迭代器，其他迭代器不会受影响

int array[]={1,2,3,4,5};
list<int> li(array,array+sizeof(array)/sizeof(array[0));
auto it=li.begin();
while(it!=li.end())
{it=li.erase(it);it++;
}

每次删除都会导致迭代器失效（vector里面我已经详细说明）所以每次删除返回迭代器都要更新it

 简单模拟实现list

June: 这里包含我的c++和Linux及数据结构https://gitee.com/taifanshu/day2.git注意：这里面要深刻体会const迭代器的实现，如何使用模板实现传参