本篇基于https://cplusplus.com/reference/list/list/讲解

认识

list是一个带头结点的双向循环链表

翻译总结：

1. 序列容器：list是一种序列容器，允许在序列的任何位置进行常数时间的插入和删除操作。
2. 双向迭代：list支持双向迭代，即可以向前和向后遍历元素。
3. 双链表实现：list容器内部通过双链表实现。每个元素都包含指向前一个元素和后一个元素的链接。
4. 非连续存储：与数组或vector不同，list中的元素可以存储在不同的、不连续的内存位置。
5. 内存开销：由于需要额外的内存来存储每个元素的链接信息，list相对于数组或vector会消耗更多的内存。
6. 与forward_list的区别：list与forward_list相似，但forward_list是单链表，只能单向迭代，而list是双链表，可以双向迭代。
7. 插入和删除性能：与其他标准序列容器（如array、vector和deque）相比，list在已知迭代器位置的容器内插入、提取和移动元素时表现更好，尤其是在需要频繁修改序列内容的情况下。
8. 访问性能：与array、vector和deque相比，list的主要缺点是缺乏通过位置直接访问元素的能力。访问特定位置的元素需要从已知位置（如序列的开始或结束）开始迭代，这需要线性时间。
9. 适用场景：list适用于需要频繁在序列中间插入和删除元素的场景，以及需要双向迭代的场景。对于需要频繁访问特定位置元素的场景，list可能不是最佳选择。

接口

在string、vector的基础上不作过多说明，仅强调差异的内容

遍历

由于底层不是数组，由其访问性能得知（ 访问性能：与array、vector和deque相比，list的主要缺点是缺乏通过位置直接访问元素的能力。访问特定位置的元素需要从已知位置（如序列的开始或结束）开始迭代，这需要线性时间。）
不再支持operator[]，只支持迭代器遍历和范围for。

// list::begin
#include <iostream>
#include <list>int main ()
{int myints[] = {75,23,65,42,13};std::list<int> mylist (myints,myints+5);std::cout << "mylist contains:";for (std::list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

支持头删、头插

string、vector这两个底层是数组的结构进行头删会导致大量的数据挪动，所以尽量避免头插头删，只在必要时使用insert实现，但对于list，不会产生大量挪动消耗，因此有单独的头插头删函数。

容量操作

没有reserve，因为list是一个一个结点开辟、一个一个结点删除的

额外增加的链表相关接口

remove 删除特定的值

注意其与erase的区别

// remove from list
#include <iostream>
#include <list>int main ()
{int myints[]= {17,89,7,14};std::list<int> mylist (myints,myints+4);mylist.remove(89);std::cout << "mylist contains:";for (std::list<int>::iterator it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

remove_if 条件删除

merge 归并

两个有序list合并以后仍然有序

（1）void merge(list<T>& x);
（2）使用自定义比较函数：void merge(list<T>& x, Compare comp);
这里，x 是要合并到当前列表的另一个列表，comp 是一个自定义的比较函数，它接受两个参数并返回一个布尔值，指示第一个参数是否应该在第二个参数之前。

#include <iostream>
#include <list>// 自定义的比较函数
bool mycomparison (double first, double second)
{ return ( int(first)<int(second) ); }int main ()
{std::list<double> first, second;first.push_back (3.1);first.push_back (2.2);first.push_back (2.9);second.push_back (3.7);second.push_back (7.1);second.push_back (1.4);//先让两个列表是有序的first.sort();second.sort();
//（1）first.merge(second);// (second is now empty)合并后second变为空second.push_back (2.1);
//（2）first.merge(second,mycomparison);std::cout << "first contains:";for (std::list<double>::iterator it=first.begin(); it!=first.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

unique 去重

前提是有序的list！！原因和去重函数的底层实现有关

// list::unique
#include <iostream>
#include <cmath>
#include <list>// a binary predicate implemented as a function:
bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }// a binary predicate implemented as a class:
struct is_near {bool operator() (double first, double second){ return (fabs(first-second)<5.0); }
};int main ()
{double mydoubles[]={ 12.15,  2.72, 73.0,  12.77,  3.14,12.77, 73.35, 72.25, 15.3,  72.25 };std::list<double> mylist (mydoubles,mydoubles+10);mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,// 15.3,  72.25, 72.25, 73.0,  73.35mylist.unique();           //  2.72,  3.14, 12.15, 12.77// 15.3,  72.25, 73.0,  73.35mylist.unique (same_integral_part);  //  2.72,  3.14, 12.15// 15.3,  72.25, 73.0mylist.unique (is_near());           //  2.72, 12.15, 72.25std::cout << "mylist contains:";for (std::list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

sort

默认排升序

• 为什么标准库里有sort，且vector都没有单独实现sort，list却要单独实现？

1. 迭代器按功能分类为单向、双向、随机迭代器，分类由容器的底层结构决定，底层连续存储的，更好支持加减
2. 三种迭代器有兼容关系：要求单向，可以用双向和随机，要求双向，可以用随机。
   包含大小：随机>双向>单向
3. 算法的迭代器类型参数名字，暗示了其需要的迭代器类型要求
   std::sort需要随机迭代器，而list的迭代器是双向迭代器，所以list无法使用标准库的sort
   reverse需要双向迭代器，find需要只读迭代器InputIterator（实际上代表单向、双向、随机迭代器都可以）

• 这个成员函数sort效率如何？
  效率远不如std::sort。所以数据多的时候尽量不要使用这个sort
  当数据量为1000000时，拷贝到vector去排序再拷贝回来，vector的性能都好很多。
  

reverse 反转

splice 粘贴

把一个链表中的数据转移到另一个链表里去

注意list迭代器要求是双向迭代器，无法通过begin（）+几或-几来控制位置

// splicing lists
#include <iostream>
#include <list>int main ()
{std::list<int> mylist1, mylist2;std::list<int>::iterator it;// set some initial values:for (int i=1; i<=4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i=1; i<=3; ++i)mylist2.push_back(i*10);   // mylist2: 10 20 30it = mylist1.begin();++it;                         // points to 2mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element)mylist2.splice (mylist2.begin(),mylist1, it);// mylist1: 1 10 20 30 3 4// mylist2: 2// "it" is now invalid.it = mylist1.begin();std::advance(it,3);           // "it" points now to 30mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());// mylist1: 30 3 4 1 10 20
//实现一个list中的元素调整————输入该list的迭代器std::cout << "mylist1 contains:";for (it=mylist1.begin(); it!=mylist1.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';std::cout << "mylist2 contains:";for (it=mylist2.begin(); it!=mylist2.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}