C++中STL六大组件List的简单介绍

一、前言

        C++非常重视效率，对效率有损失的代码常常是能省则省。使用list要包含的头文件是<list>，要包含头文件就是#iinclude <list>，List肯定是一种链表，我们不妨回忆一下那种链表插入删除效率最快也就是最简单，还能减少判断次数，链表的结尾是否要判断nullptr。毫无疑问，list所使用的结构是带头双向环形链表。带头意味着插入形式单一，无论链表中是否存在数据，都只需要将新结点的上一个指针和下一个指针做处理，省去判断是否存在结点，而且写起来也非常简单。双向意味着只要知道链结点的位置就可以访问它的下一个位置或是上一个位置，插入删除都十分方便，如果是单向还要一个一个的遍历查找。环形链表就更加简单了，学过双向链表、单(向)链表的同学都知道，不管是单链表还是双向链表尾插都十分不便，如果有固定的尾插地址维护起来更是难上加难，但是双向(可以往后也可以往前)环形链表根本就没有这样的顾虑，因为可以从开头往后走到达尾插位置。形状大概就像土家族的吊脚楼。

二、list的详细介绍

        在STL容器中，我们只要会其中的一个容器的接口，我们就可以触类旁通。不用抱太多疑虑。

        和大多数STL容器一样。包含的头文件还是它的本名<list>

        包含就要做#include <list>，不想加每次声明list对象和迭代器都加std::在对象之前的话#include <list>        using namespace std;也是可以的。

        2.1        size()函数和empty()函数

        注意该容器不是和Vector和String一样的数组存储。而是通过一个特质的结构体对象进行链接。(小编尽量快点出一个关于指针和结构体指针的专题。)连接的结点地址不一定要像数组一样连续，，所以list没有像Vector和String有容量capacity这个概念，地址分布可以尽量松散一些，可以不用申请那么大块空间，更好申请。size()函数就是反映list中的数据有多少。empty()反映list是否为空。

// 形如这样的结点进行链接。
// 这里是随便写的，list的结点肯定不长这样。比这要复杂。
struct List_Node
{
    // 要存储的内容。
    // 有模板的话，什么类型都可以。
    int _val;
    // 上一个结点的地址。
    struct List_Node* _prev;
    // 下一个结点的地址。
    struct List_Node* _next;
};


#include <iostream>
#include <list>

int main()
{
    std::list<int> lt;
    
    for (int i = 0; i <= 13; ++i)
    {
        lt.push_back(i);
        lt.push_back(i);
        std::cout << "当i为   " << i << "     时list中的数据总量:      " << lt.size() << std::endl;
    }

    return 0;
}

        2.2        insert()函数和erase()函数

        通过Vector和String的学习，我们知道insert()函数和erase()函数都是在指定位置插入删除，同时用到的都是与指针有着相似作用的迭代器。下面话不多说，直接开始上示例。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lt;
    
    for (int i = 0; i <= 13; ++i)
    {
        // 头插
        lt.insert(lt.begin(), i);
        // 尾插
        lt.insert(lt.end(), i);
        // std::cout << "当i为   " << i << "     时list中的数据总量:      " << lt.size() << std::endl;
    }

    //lt.unique();

    //lt.remove(10);

    // 范围for，C++创造者认为每次遍历都要写一个int太过于麻烦。
    // 所以直接支持了范围for。
    // 范围for会根据类中的begin()和end()函数(前面提到过的C++定好的函数名不要去改，不知道大家有没有印象。)
    // 提供的迭代器进行访问。
    for (auto& e : lt)
    {
        std::cout << e << std::endl;
    }

    return 0;
}

        2.3        front()函数和back()函数

        前面小编提到链表头插和尾插，那我们怎么快速拿到链表首尾的数据，查看是否头插尾插成功了呢？front()和back()就可以很好的检测这一点。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lt;

    for (int i = 0; i <= 13; ++i)
    {
        lt.insert(lt.begin(), i);
        lt.insert(lt.end(), i);
        std::cout << "第" << i << "行" << "front:         " << lt.front() << "        back:             " << lt.back() << std::endl;
    }

    return 0;
}

        2.4        begin()函数和end()函数

        关于begin()函数和end()函数有一些要补充的内容，Vector的迭代器是随机迭代器，与指针非常相似可以加减任意符合数组范围的值来访问该位置的值，而list的迭代器是双向迭代器只能通过++、--来改变访问的位置，毕竟list中的结点并不一定像Vector存储一样是连续的。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lt;

    for (int i = 0; i <= 13; ++i)
    {
        lt.insert(lt.begin(), i);
    }

    std::list<int>::iterator it = lt.begin();

    while (it != lt.end())
    {
        std::cout << *it << std::endl;
        // 报错
        //it + 3;

        // 双向迭代器。
        ++it;
    }

    return 0;
}

        2.5        push_front函数和push_back()函数

        通过函数名称可以得知这是头插和尾插函数。话不多说直接上案例。

#include <iostream>
#include <list>

int main()
{
    std::list<int> lt;

    for (int i = 0; i <= 13; ++i)
    {
        lt.push_front(i);
        lt.push_back(i);
        std::cout << "第" << i << "行" << "front:         " << lt.front() << "        back:             " << lt.back() << std::endl;
    }

    return 0;
}

        2.6        pop_front函数和pop_back()函数

        通过函数名称可以得知这是头删和尾删函数。和上面对比很好理解。那为什么Vector没有头插头删，list却有？因为效率！还是效率!Vector的结构就像数组一样，一个指针变量指向一块地址开头，进行访问使用。指针指向一块地址的开头该怎么头删？只能将要删除的位置之后的数据往前移动一个单位，正好将要删除位置的数据覆盖掉。这非常影响效率，所以没有实现该函数。不过大家可以试试deque容器，Vector和List的特性兼具，既可以头删又可以尾删。至于为什么等以后再说吧。

        2.7        unique()函数、remove()函数、remove_if()函数

        unique()函数是去重函数，remove()函数是删除数据为参数的函数，remove_if()函数就有一点超纲了，是根据条件删除，那怎么传条件呢？通过仿函数(就是像函数调用的类调用形式。)

#include <iostream>
#include <list>

// 仿函数
class Like_Function
{
public:
    bool operator () (int x)
    {
        // 删除偶数
        if (x % 2 == 0)
        {
            // 函数返回值为true对应的参数会被删除。
            return true;
        }

        return false;
    }
};

int main()
{
    std::list<int> lt;

    for (int i = 0; i <= 13; ++i)
    {
        // 这里我故意插入两个相同值。
        // 头插
        lt.insert(lt.begin(), i);
        // 尾插
        lt.insert(lt.end(), i);
    }

    // 去重。
    lt.unique();

    // 去掉特殊值。
    lt.remove(10);

    // 可以传一个匿名对象(写起来方便，就相当于C语言的临时值)
    lt.remove_if(Like_Function(/*构造函数要的参数*/));

    for (auto& e : lt)
    {
        std::cout << e << std::endl;
    }

    return 0;
}