STL的list容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。 list容器中的元素可以分散的存储在内存空间中，而不是必须存储在一整块连续的内存空间中。

list容器中各个元素的前后顺序是靠指针来维系的，每个元素配备了2个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为null，尾部元素的后向指针也总为null.

list容器可以在快速的以O（1）的时间复杂度插入或删除元素。但是其不能像array和vector那样快速的随机访问元素，只能从容器中第一个元素或者最后一个元素开始遍历容器，直到找到该位置。

list容器以模板类list<T>的形式在<list>头文件中，并且位于std命名空间中，因此使用该容器前，应该包含以下两行代码：

#include<list>

using namespace std;

`list`容器的创建

创建空的容器

std::list<int> values;

和array容器不同，空的list容器在创建之后仍然可以添加元素。

创建包含`n`个元素的`list`容器

std::list<int> values(10);

创建包含`n`个元素的`list`容器并指定初值‘

std::list<int> values(10,5)

通过已有`list`创建新的`list`容器

std::list<int> values(10);

std::list<int> value2(value1);

需要保证新旧容器存储的元素类型一致。

通过拷贝其他容器或普通数组（可以看作容器）中指定的元素来创建`list`容器

//拷贝普通数组，创建list容器
int a[] = { 1,2,3,4,5 };
std::list<int> values(a, a+5);

//拷贝其它类型的容器，创建 list 容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::list<int>values(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

`list`可用的成员函数

sort()函数默认升序排序。

#include <iostream>
#include <list>
using namespace std;

int main()
{
    //创建空的 list 容器
    std::list<double> values;
    //向容器中添加元素
    values.push_back(3.1);
    values.push_back(2.2);
    values.push_back(2.9);
    cout << "values size：" << values.size() << endl;
    //对容器中的元素进行排序
    values.sort();
    //使用迭代器输出list容器中的元素
    for (std::list<double>::iterator it = values.begin(); it != values.end(); ++it) {
        std::cout << *it << " ";
    }
    return 0;
}

注意双向迭代器不支持<进行比较，且不能支持用下标随机访问元素。

`STL` `list`迭代器及用法

list容器迭代器与之前的vector,deque、array最大的不同在于，list容器配备的迭代器类型为双向迭代器，而不是是随机访问迭代器。

双向迭代器支持使用++p1、p1++、p1--、p1--、*p1、p1==p2以及p1!=p2（逻辑运算符）运算符，但不支持以下操作：

p1[i]: 不能通过下标访问list容器中指定位置处的元素。
p1-=i、p1+=i、p1+i、p1-i:双向迭代器p1不支持-=、+=、+、-运算符。
p1<p2、p1>p2、p1<=p2、p1>=p2：双向迭代器不支持<、>、<=、>=比较运算符

#include <iostream>
#include <list>
using namespace std;

int main()
{
    //创建 list 容器
    std::list<char> values{'h','t','t','p',':','/','/','c','.','b','i','a','n','c','h','e','n','g','.','n','e','t'};
    //使用begin()/end()迭代器函数对输出list容器中的元素
    for (std::list<char>::iterator it = values.begin(); it != values.end(); ++it) {
        std::cout << *it;
    }
    cout << endl;
    //使用 rbegin()/rend()迭代器函数输出 lsit 容器中的元素
    for (std::list<char>::reverse_iterator it = values.rbegin(); it != values.rend();++it) {
        std::cout << *it;
    }
    return 0;
}

注意程序中用到的是!=逻辑运算符，而不是<等比较运算符。在实际应用中可以使用auto代替std::list<char>::iterator

list容器在进行插入（insert），结合(splice)等操作时，都不会造成原有的list迭代器失效，甚至删除操作，而只有指向被删除元素的元素的迭代器失效，其他迭代器不受任何影响。

#include <iostream>
#include <list>
using namespace std;

int main()
{
    //创建 list 容器
    std::list<char> values{'h','t','t','p',':','/','/','c','.','b','i','a','n','c','h','e','n','g','.','n','e','t'};
    //创建 begin 和 end 迭代器
    std::list<char>::iterator begin = values.begin();
    std::list<char>::iterator end = values.end();
    //头部和尾部插入字符 '1'
    values.insert(begin, '1');
    values.insert(end, '1');
    while (begin != end)
    {
        std::cout << *begin;
        ++begin;
    }
    return 0;
}

可以看出，在进行插入操作之后，仍使用先前创建的迭代器遍历容器，虽然程序不会出错，但是可能会由于插入位置的不同，会遗漏新插入的元素。

`list`容器的底层存储结构

对于list容器，有的容器采用双向链表实现，有些使用循环链表。

`list`容器的节点结构

双向链表的各个节点中存储的不仅仅是元素的值，还包含2个指针，分别指向前一个元素和后一个元素。

template<typename T,...>
struct __List_node{
    //...
    __list_node<T>* prev;
    __list_node<T>* next;
    T myval;
    //...
}

其中prev指针指向前一个节点，next指向后一个节点，myval用于存储当前元素的值。

`list`容器迭代器的实现

和array、vector这些容器迭代器的实现方式不同，由于list容器的元素不是连续存储的，所以该容器迭代器中，必须包含一个可以指向list容器的指针，并且该指针可以借助重载的*、++、--、==、!=等运算符，实现迭代器的递增、递减、取值等操作。

template<tyepname T,...>
struct __list_iterator{
    __list_node<T>* node;
    //...
    //重载 == 运算符
    bool operator==(const __list_iterator& x){return node == x.node;}
    //重载 != 运算符
    bool operator!=(const __list_iterator& x){return node != x.node;}
    //重载 * 运算符，返回引用类型
    T* operator *() const {return *(node).myval;}
    //重载前置 ++ 运算符
    __list_iterator<T>& operator ++(){
        node = (*node).next;
        return *this;
    }
    //重载后置 ++ 运算符
    __list_iterator<T>& operator ++(int){
        __list_iterator<T> tmp = *this;
        ++(*this);
        return tmp;
    }
    //重载前置 -- 运算符
    __list_iterator<T>& operator--(){
        node = (*node).prev;
        return *this;
    }
    //重载后置 -- 运算符
    __list_iterator<T> operator--(int){
        __list_iterator<T> tmp = *this;
        --(*this);
        return tmp;
    }
    //...
}

`list`访问元素的方法

对于list容器，只能通过front()和end()成员函数，或者迭代器访问元素，不支持随机访问，不支持[]，.at()和data()成员函数。

通过`front()`和`back()`成员函数

#include <iostream>
#include <list>
using namespace std;

int main()
{
    std::list<int> mylist{ 1,2,3,4 };
    int &first = mylist.front();
    int &last = mylist.back();
    cout << first << " " << last << endl;
    first = 10;
    last = 20;
    cout << mylist.front() << " " << mylist.back() << endl;
    return 0;
}

可以看出可以通过引用的方式获取list容器中的首尾元素，必要时还可以修改他们的值。

迭代器访问

如果要访问list容器中存储的其他元素，就只能使用list容器的迭代器。

#include <iostream>
#include <list>
using namespace std;
int main()
{
    const std::list<int> mylist{1,2,3,4,5};
    auto it = mylist.begin();
    cout << *it << " ";
    ++it;
    while (it!=mylist.end())
    {
        cout << *it << " ";
        ++it;  
    }
    return 0;
}

`list`添加元素的方法

push_back()
push_front()
emplace_front()
emplace_back()
emplace(): 在指定的位置直接生成新的元素
insert()：在指定位置插入元素
splice(): 将其他list容器存储的多个元素添加到当前list容器的指定位置处

以上插入元素的方法除了insert()和splice()方法有多种语法外，其他成员方法都仅有1种语法格式：

#include <iostream>
#include <list>
using namespace std;

int main()
{
    std::list<int> values{1,2,3};
    values.push_front(0);//{0,1,2,3}
    values.push_back(4); //{0,1,2,3,4}

    values.emplace_front(-1);//{-1,0,1,2,3,4}
    values.emplace_back(5);  //{-1,0,1,2,3,4,5}
   
    //emplace(pos,value),其中 pos 表示指明位置的迭代器，value为要插入的元素值
    values.emplace(values.end(), 6);//{-1,0,1,2,3,4,5,6}
    for (auto p = values.begin(); p != values.end(); ++p) {
        cout << *p << " ";
    }
    return 0;
}

`insert()`成员函数

#include <iostream>
#include <list>
#include <array>
using namespace std;
int main()
{
    std::list<int> values{ 1,2 };
    //第一种格式用法
    values.insert(values.begin() , 3);//{3,1,2}

    //第二种格式用法
    values.insert(values.end(), 2, 5);//{3,1,2,5,5}

    //第三种格式用法
    std::array<int, 3>test{ 7,8,9 };
    values.insert(values.end(), test.begin(), test.end());//{3,1,2,5,5,7,8,9}

    //第四种格式用法
    values.insert(values.end(), { 10,11 });//{3,1,2,5,5,7,8,9,10,11}

    for (auto p = values.begin(); p != values.end(); ++p)
    {
        cout << *p << " ";
    }
    return 0;
}

`splice()`成员函数

和insert()成员函数相比， splice()成员方法的作用将其他list容器中的元素添加到当前list容器中指定位置处。

splice()成员函数移动元素的方法是：将存储该元素的节点从list容器底层的链表中摘除，然后在链接到当前list容器底层的链表中，这意味这，当使用splice()成员函数将x容器中的元素添加到当前容器的同时，该元素会从x容器中删除

#include <iostream>
#include <list>
using namespace std;
int main()
{
    //创建并初始化 2 个 list 容器
    list<int> mylist1{ 1,2,3,4 }, mylist2{10,20,30};
    list<int>::iterator it = ++mylist1.begin(); //指向 mylist1 容器中的元素 2
   
    //调用第一种语法格式
    mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                 // mylist2:
                                 // it 迭代器仍然指向元素 2，只不过容器变为了 mylist1

    //调用第二种语法格式，将 it 指向的元素 2 移动到 mylist2.begin() 位置处
    mylist2.splice(mylist2.begin(), mylist1, it);   // mylist1: 1 10 20 30 3 4
                                                    // mylist2: 2
                                                    // it 仍然指向元素 2
   
    //调用第三种语法格式，将 [mylist1.begin(),mylist1.end())范围内的元素移动到 mylist.begin() 位置处                  
    mylist2.splice(mylist2.begin(), mylist1, mylist1.begin(), mylist1.end());//mylist1:
                                                                             //mylist2:1 10 20 30 3 4 2
   
    cout << "mylist1 包含 " << mylist1.size() << "个元素" << endl;
    cout << "mylist2 包含 " << mylist2.size() << "个元素" << endl;
    //输出 mylist2 容器中存储的数据
    cout << "mylist2:";
    for (auto iter = mylist2.begin(); iter != mylist2.end(); ++iter) {
        cout << *iter << " ";
    }
    return 0;
}

`empty()`和`size()`判断容器是否为空

假设有一个容器cont,则此代码：

if(cont.size()==0)

本质上和如下代码是等价的：

if(cont.empty())

建议使用empty()成员方法，理由很简单。无论是哪种容器，只要其模板类中提供了empty()成员方法，使用此方法都可以保证在O(1)时间复杂内完成对容器是否为空的判断；但对于list容器来说，使用size()成员方法判断容器是否为空，可能要消耗O(n)的时间复杂度。

这个结论不仅适用于vector、deque和list容器，后续还会讲解更多容器的用法，该结论也依然使用。

`list`删除元素详解

`pop_front()`，`pop_back()`, `clear()`

#include <iostream>
#include <list>
using namespace std;
int main()
{
    list<int>values{ 1,2,3,4 };
   
    //删除当前容器中首个元素
    values.pop_front();//{2,3,4}
   
    //删除当前容器最后一个元素
    values.pop_back();//{2,3}
   
    //清空容器，删除容器中所有的元素
    values.clear(); //{}
   
    for (auto begin = values.begin(); begin != values.end(); ++begin)
    {
        cout << *begin << " ";
    }
    return 0;
}

`erase()`函数

iterator erase(iterator position);  //删除`list`容器中`position`迭代器所指位置处的元素

iterator erase(iterator first, iterator last);   //删除`list`容器中`first`迭代器和`last`迭代器限定区域内的所有元素，不包括`last`指向的元素

#include <iostream>
#include <list>
using namespace std;
int main()
{
    list<int>values{ 1,2,3,4,5 };
    //指向元素 1 的迭代器
    auto del = values.begin();
    //迭代器右移，改为指向元素 2
    ++del;
    values.erase(del); //{1,3,4,5}

    for (auto begin = values.begin(); begin != values.end(); ++begin)
    {
        cout << *begin << " ";
    }
    return 0;
}

#include <iostream>
#include <list>
using namespace std;
int main()
{
    list<int>values{ 1,2,3,4,5 };
    //指定删除区域的左边界
    auto first = values.begin();
    ++first;//指向元素 2

    //指向删除区域的右边界
    auto last = values.end();
    --last;//指向元素 5

    //删除 2、3 和 4
    values.erase(first, last);

    for (auto begin = values.begin(); begin != values.end(); ++begin)
    {
        cout << *begin << " ";
    }
    return 0;
}

`remove()`函数

erease()函数是按照删除元素的位置来执行删除操作，如果想按照元素的值来执行删除操作，可以使用remove()成员函数。

#include <iostream>
#include <list>
using namespace std;
int main()
{
    list<char>values{'a','b','c','d'};
    values.remove('c');
    for (auto begin = values.begin(); begin != values.end(); ++begin)
    {
        cout << *begin << " ";
    }
    return 0;
}

`unique()`成员函数

void unique()

void unique(BinaryPredicate) //传入一个二元谓词函数

以上两种格式都可以实现去除list容器中相邻重复的元素，仅保留一份。但第二种格式的优势在于可以自定义去重规则

#include <iostream>
#include <list>
using namespace std;
//二元谓词函数
bool demo(double first, double second)
{
    return (int(first) == int(second));
}

int main()
{
    list<double> mylist{ 1,1.2,1.2,3,4,4.5,4.6 };
    //删除相邻重复的元素，仅保留一份
    mylist.unique();//{1, 1.2, 3, 4, 4.5, 4.6}

    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        cout << *it << ' ';
    cout << endl;
    //demo 为二元谓词函数，是我们自定义的去重规则
    mylist.unique(demo);

    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}

除了使用一定谓词函数的方式外，还可以使用**lamba表达式及函数对象**的方式定义

通过无参的unique只能删除相邻的重复元素，而通过自定义去重的规则，可以更好的满足不同场景下去重的需求。

`remove_if()`成员函数

可以将自定义的谓词函数（不限定参数个数）传给remove_if成员函数，list容器中能使谓词函数成立的元素都会被删除。

#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> mylist{ 15, 36, 7, 17, 20, 39, 4, 1 };
    //删除 mylist 容器中能够使 lamba 表达式成立的所有元素。
    mylist.remove_if([](int value) {return (value < 10); }); //{15 36 17 20 39}
    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;
    return 0;
}

补充知识点`lamda`表达式

可以直接在使用的时候定义函数，这个函数就叫做lamda表达式，在c++11被引入。

lambda表达式的定义形式如下：

[外部变量访问方式说明符]（参数表） -> 返回值类型

{
  语句块
}

其中外部变量访问方式说明符可以是=或&,这些外部变量访问方式说明符表示{}用到的，定义在{}外面的变量在{}是否允许被改变，如果是==，表示不允许，&表示允许改变。当然在{}也可以不使用定义在外面的变量， ->返回值类型可以省略

合法的lambda表达式：

[=](int x, int y) -> bool{return x%10<y%10;}

下列代码使用上述无名的函数：

int a[4]={11,2,33,4};

sort(a, a+4,[=](int x, int y)->bool {return x%10 <y%10;});

for_each(a,a+4, [=](int x ){cout << x <<" ";});

上述程序第二行使数组a按个位数从小到大进行排序，具体操作如下：

执行sort时，需要判断两个元素x、y的大小，会以x、y作为参数，调用lambda表达式所代表的函数，根据返回值来判断x、y的大小

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[4] = { 1, 2, 3, 4 };
    int total = 0;
    for_each(a, a + 4, [&](int & x) { total += x; x *= 2; });
    cout << total << endl;  //输出 10
    for_each(a, a + 4, [=](int x) { cout << x << " "; });
    return 0;
}

[&]表示该lambda表达式中用到的外部变量total是传引用的，其值可以在表达式执行过程中被改变。在每次执行for_each()的时候，都会将a中的一个元素累加到total中，然后将该元素加倍。

对于外部变量访问方式说明符中，还可以如下使用：

[=,&x,&y]表示外部变量x、y的值可以被修改，其余外部变量不能被修改
[&,x,y]表示除x、y外的外部变量，值都可以被修改。

#include <iostream>
using namespace std;
int main()
{   
    int x = 100,y=200,z=300;
    auto ff  = [=,&y,&z](int n) {
        cout <<x << endl;
        y++; z++;
        return n*n;
    };
    cout << ff(15) << endl;
    cout << y << "," << z << endl;
}

上述代码将lambda表达式赋予给了ff，相当于句柄函数。第 11 行通过 ff，以 15 作为参数 n 调用上面的 Lambda 表达式。该 Lambda 表达式指明，对于外部变量 y、z，可以修改其值；对于其他外部变量，例如 x，不能修改其值。因此在该表达式执行时，可以修改外部变量 y、z 的值，但如果出现试图修改 x 值的语句，就会编译出错。

list容器的创建

创建空的容器

创建包含n个元素的list容器

创建包含n个元素的list容器并指定初值‘

通过已有list创建新的list容器

通过拷贝其他容器或普通数组（可以看作容器）中指定的元素来创建list容器

list可用的成员函数

STL list迭代器及用法

list容器的底层存储结构

list容器的节点结构

list容器迭代器的实现

list访问元素的方法

通过front()和back()成员函数

迭代器访问

list添加元素的方法

insert()成员函数

splice()成员函数

empty()和size()判断容器是否为空

list删除元素详解

pop_front()，pop_back(), clear()

erase()函数

remove()函数

unique()成员函数

remove_if()成员函数

补充知识点lamda表达式