目录
一.简述list容器
list是双向链表容器，也就是说它的底层是一个双向循环链表。所需头文件#include<list>
因为list是双向链表容器，所以它的逻辑地址连续，但是它的物理地址并不连续，因此我们不能使用指针的直接跳转来访问该双向链表的某一元素。例如在上图中，指针arr指向某个双向链表的头结点，当我们想要访问这个双向链表的第二个元素时，就不能以*(arr+2)这种方式来访问，这也就意味着后续我们使用迭代器对list容器进行访问的时候，不能使用 iterator+i (iterator代表迭代器，i=0,1,2,3.....n)这种方式来访问。
二.list容器创建方式
#include<iostream>
#include<vector>
#include<list>
#include<functional>
int main()
{
std::list<int> lst1;
std::list<int> lst2(10);//count
std::list<int> lst3(10, 20);//count, value
std::list<int> lst4(lst3.begin(), lst3.end());
return 0;
}
在构造list容器lst1时，调用的是list类中默认的构造函数，（所有的容器中都有默认的构造函数），且构造的同时没有做任何事情。
在构造list容器lst2时，我们显式的给定了这个容器的初始大小10，并且将这10个大小的数据置为0。
在构造list容器lst3时，我们显式的给定了这个容器的初始大小10，且显式的将这10个大小的数据置为20。即我们给lst3中插入了10个值为20的数据。
在构造list容器lst4时，我们传入的参数是一个迭代器区间，即将lst3的开始和末尾的后一个位置传入，也就是将lst3中的数据插入到lst4中。
三.list容器的插入和删除操作
#include<iostream>
#include<vector>
#include<list>
#include<functional>
template<typename Iterator>
void Show(Iterator first, Iterator last)
{
for (first; first != last; first++)
{
std::cout << *first << " ";
}
std::cout << std::endl;
}
int main()
{
std::list<int> lst1;
for (int i = 0; i < 3; i++)
{
lst1.push_back(i + 1);
}// 1 2 3
for (int i = 0; i < 3; i++)//3 2 1 1 2 3
{
lst1.push_front(i + 1);
}
Show(lst1.begin(), lst1.end());
lst1.insert(++lst1.begin(), 6);
Show(lst1.begin(), lst1.end());
lst1.pop_front();
Show(lst1.begin(), lst1.end());
lst1.pop_back();
Show(lst1.begin(), lst1.end());
lst1.erase(++lst1.begin(), --lst1.end());
Show(lst1.begin(), lst1.end());
return 0;
}
push_back 即尾插，在链表的尾部插入元素，时间复杂度O(1)。
push_front 即头插，在链表的头部插入元素，时间复杂度O(1)。
insert 即按位置来插入元素，insert函数有以下五个重载，时间复杂度O(1)
- iterator std::list<_Ty, _Alloc>::insert<_Iter, >(const const_iterator _Where, _Iter _First, _Iter _Last)，按位置（Where）插入一个区间（Iter_First~Iter_Last）里面的元素，这个区间代表的是一个迭代器区间。
- iterator std::list<_Ty, _Alloc>::insert(const_iterator _Where, size_type _Count, const _Ty & _Val)，在Where这个位置插入Count个值为Val的元素。
- iterator std::list<_Ty, _Alloc>::insert(const_iterator _Where, const _Ty & _Val)，在Where这个位置插入一个值为Val的元素，且这个值被const锁修饰，所以值不能被修改。
- iterator std::list<_Ty, _Alloc>::insert(const_iterator _Where, _Ty && _Val)，在Where这个位置插入一个值为Val的元素，但这个值没有被const锁修饰。
- iterator std::list<_Ty, _Alloc>::insert(const_iterator _Where, initializer_list<_Ty> _Ilist)，使用初始化列表在Where位置插入新的元素，例如
lst1.insert(lst1.begin(),{1,3,4});
pop_front 即头删，删除链表的首元素，时间复杂度O(1)。
pop_back 即尾删，删除链表的尾部元素，时间复杂度O(1)。
erase 即按位置来删除，erase函数有以下两个重载，时间复杂度O(1)
- iterator erase(const const_iterator _First, const const_iterator _Last)，删除某个迭代器区间的所有元素。
- iterator erase(const const_iterator _Where)，删除Where这个位置的元素。
访问，即Show()函数的时间复杂度为O(n)。
所以list容器的优点是“任意位置快速的插入或删除”，缺点是“访问的效率较低”。
四.关于list容器迭代器的使用方法
#include<iostream>
#include<vector>
#include<list>
#include<functional>
int main()
{
int arr[] = { 1, 3, 214, 23, 5, 3 };
int len = sizeof(arr) / sizeof(arr[0]);
std::vector<int> vec(arr, arr + len);//内存连续 随机访问迭代器
std::list<int> lst(vec.begin(), vec.end());//内存不连续 双向迭代器 ++ --
std::cout << vec[2] << std::endl;
//std::cout << lst[1] << std::endl;
std::vector<int>::iterator vit = vec.begin() + 2;
std::cout << *vit << std::endl;
//std::list<int>::iterator lit = lst.begin() + 2;
//std::cout << *lit << std::endl;
return 0;
}
我们知道vector容器的底层是一个数组，它的逻辑和物理地址都是连续的，因此我们可以使用指针加上偏移来访问数据，而list容器的物理地址地址是不连续的，因此我们不能通过指针加上偏移来访问数据。我们把vector容器中的迭代器称为 随机访问迭代器，而list容器中的迭代器称为 双向迭代器。
通俗的讲，双向迭代器不能进行 +i 或 -i 的操作，如果要遍历容器，那么它只能进行++ 或 --操作。（i=1,2,3....n）
而随机访问迭代器，既能进行 +i 或 -i 的操作，也能进行++ 或 -- 操作。（i=1,2,3....n）