list和我们之前讲的东西都一样，list第二个参数是一个空间配置器，是一个内存池， 底层是一个带头双向循环列表。list可以重载[]，但是效率太低了。
list的遍历不能使用下标+[]，因为它的空间不是连续的，可以使用迭代器，也可以使用范围for。
#include<iostream>
#include<list>
using namespace std;
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
return 0;
}
1. list的介绍及使用
1.1 list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)
1.2 list的使用
list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。list的头插和头删复杂度都为O(1)。
从string之后，position都变了，在string的部分都是用下标去插入，现在的位置都是迭代器，但是和vector还是有点区别的。比如下面的在第五个位置插入数据：
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(10);
lt.push_front(20);
//如果要在第五个位置插入数据
//下面这种方法是不行的
//lt.insert(lt.begin() + 5, 10);
//因为vector是一个连续的物理空间，是支持+的，但是插入的代价比较大，数据要往后挪动。
//list和vector各有各的优缺点。
//list的物理空间不是连续的，可以支持+，但是代价比较大，库立面没有直接支持。
//只有一种方法
auto it = lt.begin();
for (size_t i = 0; i < 5; i++)
{
++it;
}
lt.insert(it, 100);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
return 0;
}
这是vector和list的第一个差别，这种差别是迭代器的差别导致的，list的插入代价是很低的，把前后位置的指向关系改变一下就可以了，排序都写到算法里面去了。
还有一种插入的场景，就是找到一个值，在它的前面插入一个数据。list和vector都没有提供find接口。
对于vector来说用小于没有问题，但对于list来讲，迭代器中end()节点的地址不一定比begin()大， end()的节点是有效数据的下一个位置，也就是哨兵位。
list中的insert接口不存在迭代器失效的问题，比如我要在这个位置插入接点，没有扩容的问题，没有野指针的问题，没有位置改变的问题，因为不需要挪动数据。vector在这个位置插入之前有两大问题，第一大问题就是扩容，第二大问题就是插入这个数据之后，位置往后挪，它的位置意义都变了。
erase节点存在迭代器失效的问题，因为节点都没了。
算法中的find，找到就返回这个节点，找不到就返回end节点。
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(10);
lt.push_front(20);
auto it = lt.begin();
it = find(lt.begin(), lt.end(), 3);
if (it != lt.end())
{
lt.insert(it, 3);
*it *= 100;
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
it = find(lt.begin(), lt.end(), 3);
if (it != lt.end())
{
lt.insert(it, 30);
*it *= 100;
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
return 0;
}
如果是erase的话，程序就会崩溃：
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(10);
lt.push_front(20);
auto it = lt.begin();
it = find(lt.begin(), lt.end(), 3);
if (it != lt.end())
{
lt.insert(it, 3);
*it *= 100;
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
it = find(lt.begin(), lt.end(), 3);
if (it != lt.end())
{
lt.erase(it);
*it *= 100;
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
return 0;
}
如果要用erase删除list中的偶数：
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(10);
lt.push_front(20);
auto it = lt.begin();
//如果要用erase删除list中的偶数：
while (it != lt.end())
{
if (*it % 2 == 0)
{
it = lt.erase(it);
}
else
{
++it;
}
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
return 0;
}
swap就是两个链表直接交换。
int main()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
list<int> lt2;
lt2.push_back(10);
lt2.push_back(20);
lt2.push_back(30);
lt2.push_back(40);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
lt1.swap(lt2);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
return 0;
}
容器都是通过迭代器区间去访问的，比如这有一个容器，想在这一段查找，给这个容器的区间查找这个val就可以了。
clear就是把我们的节点删掉等等这些情况。
list中sort的价值大不大，库里面也有一个sort，list中也提供了一个sort，有啥意义呢？编译报错了，有时候掉不调到库里面去了，就看这个库是谁的归属，那就是哪儿出错了，sort这个库用这个迭代器我们不能用，因为sort这个库里面用到一个
，就一个点我们就知道了，sort是快排，快排不能用这个东西，因为快排要做过参数取中，参数取中选其中一个值的时候，选中间那个值或者选另外一个值的时候，我直接要选那个位置，快排不适合，就是那个链表没办法适应这个场景。
所以大家仔细再看，如果我们单看算法，这些算法的名字有一些差异，他这个是函数模板，但是他在这个名字上面很有讲究，它的名字就暗示了应该传什么迭代器，这里就要迁移出一个知识讲一讲，然后再结合这这个说，迭代器从他的功能的角度是会分类的，从功能上来说，分为单向、双向、随机。功能上是什么呢？单向就只能++，双向可以++也可以--，随机是可以++、--、也可以+，也可以-。
谁的迭代器就是典型的单向呢？单链表、哈希表。谁是双向迭代器呢？双向链表，其实也就是我们的list，还有map、set，也就是树。谁是随机迭代器呢？vector、string、双端队列deque。它这的名字就暗示了你用哪种算法，reverse就适合用双向，find就适合用单向，sort就适合用随机。这个地方对迭代器是一个隐式的分类，可以认为它是一个性质进行划分，这个性质跟容器的底层结构有关系。
谁可以调用这个sort算法呢，这个sort底层是快排，决定了他要用这个随机迭代器，随机是可以吊的，链表就不可以调，链表这里调就报错了，用这个算法就要看容器的迭代器到底是哪一种，能不能适应，我怎么知道我的容器是哪一种呢？这里是有说明的，它的迭代器的内容是什么，vector和string可以用这个逆置，随机迭代器可以认为是一个特殊的双向迭代器，随机迭代器满足双向的要求，满足单向的要求，
，如果写这个，单向、双向、随机都可以用，写随机的就随机可以用，写双向的就双向、随机可以用，写单向的就单向、双向、随机都可以用。
set底层就是更复杂的迭代器，也就是树了，forward_list是单向迭代器，
排序应该用vector，不应该用list，vector的效率远高于list，
数据量越大，差距越大一些，list排序终究还是要慢不少。如果我们真的要数据排序，我们不应该用链表，链表访问数据相比vector毕竟还是慢，list底层用的是归并算法。所以说list的sort意义不大。
void test_op()
{
srand(time(0));
const int N = 1000000;
vector<int> v;
v.reserve(N);
list<int> lt1;
//list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
v.push_back(e);
lt1.push_back(e);
}
// 排序
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
int main()
{
test_op();
return 0;
}
list的作用是当排序值比较小的时候，list排序才有价值。
void test_op()
{
srand(time(0));
const int N = 100000;
vector<int> v;
v.reserve(N);
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i)
{
auto e = rand();
lt2.push_back(e);
lt1.push_back(e);
}
// 拷贝到vector排序，排完以后再拷贝回来
int begin1 = clock();
// 先拷贝到vector
for (auto e : lt1)
{
v.push_back(e);
}
// 排序
sort(v.begin(), v.end());
// 拷贝回去
size_t i = 0;
for (auto& e : lt1)
{
e = v[i++];
}
int end1 = clock();
int begin2 = clock();
lt2.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
int main()
{
test_op();
return 0;
}
我们可以区分迭代器的类型，区分迭代器的类型有点复杂，叫做迭代器的萃取，就可以分辨出迭代器的类型。
merge就是连个链表可以直接进行归并，归并有一个前提就是先有序，两个链表要先sort再merge，这里还有另外一个东西叫仿函数，比较的仿函数的概念，仿函数在优先级队列再讲。
这个接口的本质是去重，去重也是有前提的，也是要先排序， 如果不排序去重的话效率是很低的。
remove就是find加erase，remove就是直接可以删。remove唯一要注意的是如果这个值不存在会不会报错？
void text_x()
{
int myints[] = { 17,89,7,14 };
std::list<int> mylist(myints, myints + 4);
mylist.remove(890);
for (auto e : mylist)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
text_x();
return 0;
}
相当于find，如果找到就删除了，没找到就啥也不干。
remove_if 也涉及到一个仿函数的问题。
这个接口可以把一个链表的内容转移到另一个，它的转移是直接把节点拿走，就比如说有一个a链表，有一个b链表，直接把a链表的节点取下来直接插入到b链表，相当于a链表删除了数据，b链表插入了数据，严格来说就是发生了转移。也可以转移到自己身上，但是别把范围区间重叠了。
int main()
{
int myints[] = { 17,89,7,14 };
std::list<int> mylist1, mylist2;
std::list<int>::iterator it;
for (int i = 1; i <= 4; ++i)
mylist1.push_back(i); // mylist1: 1 2 3 4
for (int i = 1; i <= 3; ++i)
mylist2.push_back(i * 10); // mylist2: 10 20 30
for (auto e : mylist1)
{
cout << e << " ";
}
cout << endl;
for (auto e : mylist2)
{
cout << e << " ";
}
cout << endl << endl;
it = mylist1.begin();
++it;
// points to 2
//全部转移
//mylist1.splice(it, mylist2);
//转移一个
//mylist1.splice(it, mylist2, ++mylist2.begin());
//部分转移
//mylist1.splice(it, mylist2, ++mylist2.begin(), mylist2.end());
//把后面的数据转移到第一个的前面
mylist1.splice(mylist1.begin(), mylist1, ++mylist1.begin(), mylist1.end());
for (auto e : mylist1)
{
cout << e << " ";
}
cout << endl;
for (auto e : mylist2)
{
cout << e << " ";
}
cout << endl;
return 0;
}