目录
一、list的介绍
有数据结构作为基础，STL 上手很快，学习成本也低，本文也是讲解 list 常用重点接口，其它有需要再查询文档，重点也是放在 list 的模拟实现上面
- list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代
- list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素
- list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效
- 与其他的序列式容器相比(array，vecto，deque)，list通常在任意位置进行插入、移除元素的执行效率更好
- 与其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素
- list 本质上就是带头双向循环链表
template < class T, class Alloc = allocator<T> > class list;
class Alloc = allocator 是空间配置器（内存池），暂时不用理会，它也给了缺省值，目前不用我们自己传，使用默认缺省值就可以了
使用 list 要包含 list 的头文件：
#include <list>
list 要重点使用迭代器了，因为 list 不能支持随机访问了，即不能使用 “[]” + 下标 进行访问
二、list的使用
list 也是掌握一些常用的接口，其它有需要在查询文档
先说一下成员变量
value_type 就是第一个模板参数 （T）；size_type 与 size_t 的用法一致，无符号
2.1 Construct
接口简单说明：
构造函数 接口说明 list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素 list() 构造空的list
list (const list& x) 拷贝构造函数 list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list
构造某个类型的 list
1. list<int> l1;//构造int类型的list 2. list<double> l2;//构造double类型的list
测试代码
voidTest_list() { list<int>l1; // 构造空的l1list<int>l2(10, 3); // l2中放10个值为3的元素list<int>l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3list<int>l4(l3); // 用l3拷贝构造l4//以数组为迭代器区间构造l5intarray[] = { 1,2,3,4 }; list<int>l5(array, array+sizeof(array) /sizeof(int)); }
2.2 operator=
测试代码
voidTest_list() { list<int>l1(10, 3);// l1中构造10个值为3的元素list<int>l2; l2=l1;//赋值重载}
析构函数不解释了，程序结束自动调用
2.3 Iterators
list 的迭代器不再是简单的原生指针了，指针要经过封装和重载才能支持 list 的迭代器的使用，范围 for 的底层就是迭代器。此处可暂时将迭代器理解成一个指针，该指针指向list中的某个节点，到 list 模拟实现再细讲
常用接口
函数声明 接口说明 begin 返回第一个元素的迭代器 end 返回最后一个元素下一个位置的迭代器
rbegin 返回第一个元素的reverse_iterator，即end位置 rend 返回最后一个元素下一个位置的reverse_iterator,即begin位置
示意图
注意：遍历 list 只能用迭代器和范围for
测试代码
voidTest_list() { intarray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int>l(array, array+sizeof(array) /sizeof(array[0])); list<int>::iteratorit=l.begin(); //迭代器判断结束只能使用 !=while (it!=l.end()) { cout<<*it; ++it; } cout<<endl; for (autoe : l) { cout<<e; } cout<<endl; }
运行结果
注意：迭代器判断结束条件只能使用 != ，因为 list 的每个节点的空间的大小是不确定的，不能使用 it < l.end()；之前 vector 和 string 的迭代器结束可以使用 < 判断迭代器结束，因为它们的空间是连续的
反向迭代器使用
voidTest_list() { intarray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int>l(array, array+sizeof(array) /sizeof(array[0])); list<int>::reverse_iteratorit=l.rbegin(); //迭代器判断结束只能使用 !=while (it!=l.rend()) { cout<<*it; ++it; } cout<<endl; }
注意
- begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
- rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
运行结果
2.4 Capacity
常用接口
函数声明 接口说明 empty 检测 list 是否为空，是返回 true，否则返回 false size 返回 list 中有效节点的个数
不演示，直接使用即可
2.5 Element access
常用接口
函数声明 接口说明 front 返回list的第一个节点中值的引用 back 返回list的最后一个节点中值的引用
测试代码
voidTest_list() { intarray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int>l(array, array+sizeof(array) /sizeof(array[0])); cout<<l.front() <<endl; //1cout<<l.back() <<endl; //0}
运行结果
2.6 Modifiers
常用接口
函数声明 接口说明 push_front 在list首元素前插入值为val的元素 pop_front 删除list中第一个元素 push_back 在list尾部插入值为val的元素
pop_back 删除list中最后一个元素 insert 在list position位置中插入值为val的元素 erase 删除list position位置的元素 swap 交换两个list中的元素
clear 清空list中的有效元素
测试代码
voidTest_list() { list<int>l; l.push_back(1);//尾插数据l.push_back(2); l.push_back(3); l.push_back(4); for (autoe : l) cout<<e; cout<<endl; l.pop_back();//删除 4for (autoe : l) cout<<e; cout<<endl; l.push_front(0);//头插0for (autoe : l) cout<<e; cout<<endl; l.pop_front();//头删for (autoe : l) cout<<e; cout<<endl; }
运行结果
erase
测试代码
voidTest_list() { intarray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int>l(array, array+sizeof(array) /sizeof(array[0])); list<int>::iteratorpos=find(l.begin(), l.end(), 2); l.erase(pos); //删除2for (autoe : l) cout<<e; cout<<endl; }
运行结果
insert
测试代码
voidTest_list() { intarray[] = { 1, 2, 4, 5, 6, 7, 8, 9 }; list<int>l(array, array+sizeof(array) /sizeof(array[0])); list<int>::iteratorpos=find(l.begin(), l.end(), 4); l.insert(pos, 3); //在4的位置的前一个插入3for (autoe : l) cout<<e; cout<<endl; }
运行结果
list 的迭代器失效问题
前面说过，此处可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
所以 insert 并不会造成迭代器失效，而 erase 之后则会造成 pos 迭代器失效，因为 pos 迭代器指向的空间已经被释放了
测试代码
voidTest_list() { intarray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int>l(array, array+sizeof(array) /sizeof(array[0])); autoit=l.begin(); while (it!=l.end()) { // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值l.erase(it); ++it; } }
运行结果
修改代码
voidTest_list() { intarray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 }; list<int>l(array, array+sizeof(array) /sizeof(array[0])); autoit=l.begin(); while (it!=l.end()) { l.erase(it++); // it = l.erase(it); } }
修改之后，程序就可以正常运行了
2.7 Operations
这些接口不怎么使用，就不介绍了，有需要再查询文档，其中的 sort 排序数据量大的时候，效率低，也不怎么使用
----------------我是分割线---------------
文章到这里就结束了，下一篇即将更新
