List类的超详细解析！（超2w+字）

1. list 的介绍及使用

---

1.1 list 的介绍

list的文档介绍

1. list是可以在常数范围内（即O(1)时间复杂度）在任意位置进行插入和删除的序列式容器，并且该容器 可以前后双向迭代。
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中一些常见的重要接口。

1.2.1 list 的构造

构造函数（ (constructor)）	接口说明
list()	构造空的 list
list (size_type n, const value_type& val = value_type())	构造的 list 中包含 n 个值为 val 的元素
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用 [first, last) 区间中的元素构造 list

1.2.2 list iterator 的使用

list 的迭代器是将原生指针进行封装后的自定义类型，因为与 vector 和 string 等在物理结上是连续的，所以可以直接将原生指针作为迭代器，而 list 不行，因为 list 的存储方式是链式结构，是分散的，所以不能直接对原生指针进行 等操作，所以得对 list 的指针进行封装，下面模拟实现的时候会具体讲。

函数声明	接口说明
begin() end()	**返回第一个元素的迭代器 ** 返回最后一个元素下一个位置的迭代器
rbegin() rend()	返回第一个元素的 reverse_iterator, 即 end 位置，返回最后一个元素下一个位置的 reverse_iterator, 即begin 位置

【注意】

1. begin 与 end 为正向迭代器，对迭代器执行 操作，迭代器向后移动
2. rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器执行 操作，迭代器向前移动

代码语言：javascript复制

// list迭代器的使用
// 注意：遍历链表只能用迭代器和范围for，因为list不支持[]重载
void PrintList(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const，返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end();   it)
    {
        cout << *it << " ";
        // *it = 10; 编译不通过
    }

    cout << endl;
}

void TestList2()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array   sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list<int>::iterator it = l.begin();   // C  98中语法
    auto it = l.begin();                     // C  11之后推荐写法
    while (it != l.end())
    {
        cout << *it << " ";
          it;
    }
    cout << endl;

    // 使用反向迭代器逆向打印list中的元素
    // list<int>::reverse_iterator rit = l.rbegin();
    auto rit = l.rbegin();
    while (rit != l.rend())
    {
        cout << *rit << " ";
          rit;
    }
    cout << endl;
}

1.2.3 list capacity

函数声明接口说明empty检测 list 是否为空，是返回 true，否则返回 falsesize返回 list 中的有效个数

1.2.4 list element access

函数声明接口说明front返回 list 的第一个节点中值的引用back返回 list 的最后一个节点中值的引用

1.2.5 list modifiers

函数声明接口说明push_front在 list 首元素前插入值为 val 的元素pop_front删除 list 中的第一个元素push_back在 list 尾部插入值为 val 的元素pop_back删除 list 中的最后一个元素insert在 list position 位置前插入值为 val 的元素 （迭代器不会失效） （一般配合算法库中的find一起使用）erase删除 list position 处位置的元素 （迭代器会失效）swap交换两个 list 中的元素clear清空 list 中的有效元素 （不清理头节点）

1.2.6 list Operations

函数声明接口说明splice将 list1 中的元素转移到 list2中 （不是拷贝，而是搬移）remove将 list 中所有 val 节点删掉unique去掉 list 中的重复的元素 （需要先排序，配合 list 类自己的sort函数一起使用）merge在相同类型且分别有序的情况下，将 list2 中的元素都搬移到 list1 中，且按大小进行排序 （list2变成空的）sort排序 list 中的元素==（效率低，不推荐）==reverse逆置 list 中的元素 这些操作用的比较少，而且不太推荐使用sort等函数，因为效率比较低。

list 中还有一些操作，需要用到时大家可参阅 list 的文档说明。

补充问题：

为什么 list 类中要重新实现sort函数，而不是使用算法库里面的？

• 理论上来说，算法库中实现的函数模板是通用的，但是因为算法库里面的一些函数是需要接受不同类型的迭代器的，而 list 类的迭代器属于双向迭代器，算法库里面sort函数底层使用的是快速排序，而快速排序要求容器迭代器接收的是随机迭代器，迭代器类型不符合，所以使用不了库里面的sort函数以及其他一些函数。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Lsp6rLWo-1659497276150)(…/…/img/image-20220731184111907.png)]

2. list 的迭代器失效

---

前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行 插入不会导致 list 的迭代器失效 的， 只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。

代码语言：javascript复制

void TestListIterator1()
{
     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
     list<int> l(array, array sizeof(array)/sizeof(array[0]));
     auto it = l.begin();
     while (it != l.end())
     {
         // erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
         l.erase(it); 
           it;
     }
}
// 改正
void TestListIterator()
{
     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
     list<int> l(array, array sizeof(array)/sizeof(array[0]));
     auto it = l.begin();
     while (it != l.end())
     {
     	l.erase(it  ); // it = l.erase(it);
     }
}

3. list 的模拟实现

---

Ⅰ、基本框架的实现

1. 构造节点