前言
学习完list，我们会对STL中的迭代器有进一步的认识。list底层有很多经典的东西，尤其是他的迭代器。而list的结构是一个带头双向循环链表。
list没有reserve和resize，因为它底层不是连续的空间，它是用时随时申请，不用时随时释放。他也不支持随机访问，所以没有operator[ ]。而他有头插，尾插，头删，尾删，以及任意位置的插入删除。
严格来说，C++中list实际有两个：
第一个forward_list是单链表，它是C++11新增加的，它的使用场景很少。它不支持尾插，尾删，因为单链表尾插尾删的效率很低。并且它对任意位置做插入删除操作是在当前位置之后，因为当前位置之前得找前一个，也是一个O（n）的实现。唯一的优势也就是每个结点少一个指针。
第二个list是我们要学习的带头双向循环链表。
list的介绍
1.列表是序列容器，允许在序列中的任何位置进行恒定时间O(1)的插入和擦除操作，以及双向迭代。
2.列表容器底层是双链表；双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向前一个元素和后一个元素。
3.list与forward_list非常相似：主要区别在于forward_listobject是单个链表，因此它们只能向前迭代，以换取更小、更高效。
4.与其他基本标准序列容器（array，vector和deque）相比，list在任意位置插入，删除结点的效率更高。
5.list和forward_list最大的缺陷是不支持在任意位置的随机访问，其次，list还需要一些额外的空间，以保存每个结点之间的关联信息（对于存储的类型较小元素来说这可能是一个重要的因素）。
list的使用
1.list的构造
| constructor | 接口说明 |
|---|---|
| list() | 构造空的list对象 |
| list(size_t n,const value_type& val =value_type()) | 构造list对象中包含n个值为val的元素 |
| list(const list& x) | 拷贝构造 |
| lsit(Inputiterator first,Inputiterator last) | 用迭代区间构造list对象 |
这里我们只要记住用迭代区间构造list对象时，也可以用其他容器的迭代器就行，其他没什么好说的。
#include<iostream>
#include<vector>
#include<list>
using namespace std;
int main()
{
vector<int> v = { 1, 2, 3, 4, 5 };
list<int> lt1(v.begin(), v.end());//用vector的迭代器构造list对象
return 0;
}
2.list迭代器的使用
| iterator | 接口说明 |
|---|---|
| begin && end | 返回第一个元素的迭代器 && 返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的 reserve_iterator，即 end 位置 && 返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置 |
我们需要记住两点：
1.在遍历的时候vector和string我们可以使用小于或不等于做判断条件，但是list只能使用不等于。因为list内不是连续的空间。
2.因为list不支持operator[ ]，所以我们遍历list的时候不能使用[ ]的方式遍历了
vector<int> v = { 1, 2, 3, 4};
list<int> lt(v.begin(), v.end());
list<int>::iterator it1 = lt.begin();
while(it1 != lt.end())//这里只能使用!=,不能使用<
{
cout << *it1 << " ";
++it1;
}
cout << endl
3.list容量大小的函数（empty && size）
| empty | 判断list对象是否为空 |
| size | 返回list中有效结点的个数 |
4.list结点接收的函数（front && back）
| front | 返回list第一个结点的数据的引用 |
| back | 返回list最后一个结点的数据的引用 |
5.list修改函数
| push_back | 尾插一个值为val的结点 |
| push_front | 头插一个值为val的结点 |
| pop_back | 尾删一个结点 |
| pop_front | 头删一个结点 |
| insert | 在pos位置中插入值为val的结点 |
| erase | 删除pos位置的结点 |
| swap | 交换两个list对象中的元素 |
| clear | 清空list对象中的有效元素 |
下面我们在一段代码中用例子来解释我们需要注意的地方：
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
#include<functional>
using namespace std;
namespace std
{
void test1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.pop_front();
lt.pop_front();
lt.pop_front();
lt.pop_front();
//lt.pop_front(); //注意在头删、尾删时要保证list里还有数据,否则这里会报断言错误
for (const auto& e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test2()
{
list<int> lt;
lt.push_back(10);
lt.push_back(20);
lt.push_back(30);
lt.push_back(40);
list<int>::iterator pos = find(lt.begin(), lt.end(), 30);//list里也没有提供find函数,所以这里使用的是algorithm里的
if (pos != lt.end())
{
lt.insert(pos, 3);
}
for (const auto& e : lt)
{
cout << e << " ";
}
cout << endl;
lt.clear();//clear不会把头节点清除,这里还可以继续插入数据
lt.push_back(1);
lt.push_back(2);
for (const auto& e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test3()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
list<int> lt2;
lt2.push_back(2);
lt2.push_back(1);
list<int> lt3;
lt3.push_back(1);
lt3.push_back(2);
lt3.push_back(3);
lt3.push_back(4);
//对于swap,建议使用容器里的,而不建议使用算法里的。它们效果一样,但是效率不一样
lt1.swap(lt2); //这是std::list::swap，专门为了list设计的，效率会更高
//swap(lt1, lt2); //这是std::swap，这是算法中的，通用的，底层发生的是深拷贝，效率低
for (const auto& e : lt1)
{
cout << e << " ";
}
cout << endl;
for (const auto& e : lt2)
{
cout << e << " ";
}
cout << endl;
//所有的排序都满足,>是降序,<是升序,这里默认是升序
//这个也是一个类模板,它是一个仿函数,所在头<functional>，后面我们会实现,sort所在头<algorithm>
greater<int> g;
lt3.sort(g);
lt3.sort(greater<int>());//同上,可以直接写成匿名对象
for (const auto& e : lt3)
{
cout << e << " ";
}
cout << endl;
//sort(lt3.begin(), it3.end()); //error
//vector可以使用算法提供的sort()函数，但是list不行，因为本质sort()会用两个迭代器相减,而list的迭代器不支持减!!
//unique的功能是去重,是algorithm提供的,去重的前提是排序,升序降序都行,如果不排序它只能去重相邻的数据
lt3.unique();
for (const auto& e : lt3)
{
cout << e << " ";
}
cout << endl;
//erase需要先find,而remove可以直接删除,有就全删,没有就不删,由algorithm提供
lt3.remove(2);
for (const auto& e : lt3)
{
cout << e << " ";
}
cout << endl;
//reverse的功能是逆置,对于带头双向循环链表的逆置比单链表简单,由algorithm提供
lt3.reverse();
for (const auto& e : lt3)
{
cout << e << " ";
}
cout << endl;
//merge的功能是合并
//splice的功能是转移,它转移的是节点不是数据,很特殊的场景下才会使用到,我们以后在了解LRU可能还会再接触到
}
}
int main()
{
//std::test1();
//std::test2();
std::test3();
return 0;
}注意：
1.C++98不论什么容器都建议使用各自容器里的 swap，而不建议使用算法里的 swap。
因为无论什么容器使用算法中的swap()时都会涉及到深拷贝问题，并且需要深拷贝三次，代价极大。
而容器内的swap会根据各个容器的特性，进行交换。例如，两个list对象交换的时候，只需要交换两个对象的头指针指向就行；两个vector对象交换的时候，只需要交换两个vector对象中_start、_finish、_endofstorage三个指针的指向即可，不用做深拷贝，也就提高了效率。
2.关于迭代器的补充
从使用功能的角度分类：正向，反向，const，非const
从容器底层结构分类：单向，双向，随机
如单链表，哈希表迭代器就是单向，特点是能++，不能--；双向循环链表，map迭代器就是双向，特点是能++，也能--；string，vector，deque迭代器就是随机迭代器，特征是不仅能++，--，还能+，-，一般随机迭代器底层都是一个连续的空间。
这里我们可以通过算法里函数参数的命名来推断出他的含义：
我们看，例如sort函数内参数命名为RandomAccessIterator，也就是随机迭代器；而reverse函数内参数命名为BidirectionalIterator，也就是双向迭代器。
而我们使用的时候，要注意，比如：reserve函数的参数是双向迭代器，而string能不能使用呢？答案是可以的，因为string是随机迭代器，它满足双向迭代器的所有功能。但是例如：list能使用sort函数吗？答案是不能的，因为list迭代器是双向的，不满足随即迭代器的功能。也就是说功能多的是可以执行参数迭代器功能少的函数的，这实际上就是一种继承关系。
而我们这里就要明白一个道理：容器是用来存储数据的，而根据封装的要求，他的成员变量一般是私有的，而封装的本质就是通过合法的渠道去进行操作，那我可以提供成员函数来供使用者合法的操作，但是这样的话也不太好，因为底层结构差异大了以后，每种容器的操作起来的差别也会很大。例如，string，vector底层是数组，我们通过数组的方式进行操作，list底层是链表我们通过链表的方式进行操作，而其他复杂的数据结构，操作的方式会更不一样。所以迭代器的本质就是不破坏容器的封装性，不暴露容器底层实现细节的情况下，提供统一的方式去操作容器中存储的数据。只要我们会其中一种容器的迭代器，我们用其他容器的迭代器也没有问题。所以迭代器被称为”容器和算法之间的胶合剂“。
6.list迭代器失效问题
在具体介绍list迭代器之前，我们可以先将迭代器暂时理解为指针，迭代器失效就是迭代器所指向的结点无效，即该结点被删除了。list底层结构为带头双向循环链表，所以对list进行insert操作时不会导致list迭代器失效，只有在erase的时候才会失效，并且失效的只有被删除的结点，其他迭代器不会收到影响。
也就是说：
- vector insert，pos会失效，因为它的物理空间是一个连续的数组，首先它可能会扩容，就会导致野指针问题；就算不扩容，挪动了数据，pos的意义也改变了，所以pos也失效了
- vector erase，pos会失效，因为此时pos的意义已经改变了，为了解决这个问题，我们可以使用pos重新接收erase函数的返回值，其指向删除元素的下一个元素
- list insert，pos不会失效，因为list底层是一个链表，每个结点都是独立的，insert后的数据属于新增的结点，而pos还是指向原来的位置
- erase pos，pos会失效，因为pos指向的结点已经被释放了，为了解决这个问题，和vector erase的解决方法一样，我们也可以使用pos重新接收erase函数的返回值
以上就是本章的所有内容，谢谢大家！！！
