STL之list的使用（超详解）

💓 博客主页：

⏩ 文章专栏：

一、list的介绍及使用

1.1 list的介绍

1.1 list的介绍

list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。

list 的底层是双向链表结构，双向链表中的每个元素存储在互不相关的独立节点中，在节点中通过指针指向的前一个元素和后一个元素。

list 和 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效。

与其它的序列式容器相比（arry、vector、deque） ，list 通常在任意位置进行插入，移除元素的执行效率更好。

与其它序列式容器相比， list 和 forward_list 最大的缺陷是不支持任意位置的随机访问 ，比如：要访问 list 的第 5 个元素，必须从已知的位置（比如头部或者尾部）迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，已保存每个节点的相关联信息。

1.2 list的使用

list 在实际中非常重要，在实际中我们熟悉常用的接口就可以，下面列出了需要我们重点掌握的接口。

1.2.1 list的构造

size_type 表示一个无符号整数类型，value_type 是 list 的第一个模板参数，也就是要存储的数据类型。使用迭代器区间的构造函数是函数模板，只要是满足 Input 类型的迭代器都可以使用该构造函数。

1.2.2  iterator的使用

注意： begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动。rbegin 与 rend 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动。由于 list 的底层物理空间并不连续，所以 list 的迭代器不再是原生指针，并且 list 的迭代器没有对 + 和 - 进行重载，只重载了 ++ 和 – ，因为空间不连续，重载 + 会比较复杂。即 l.begin() + 5 是不被允许的。

#include<iostream>
using namespace std;
#include<list>
void print_list(list<int>& lt)
{
    list<int>::iterator it = lt.begin();
   // 用迭代器方式打印l2中的元素
    while (it != lt.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;

    
    for (int& e : lt) // C++11范围for的方式遍历
    {
        cout << e << " ";
    }
    cout << endl;
    //反向迭代器
    list<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
        cout << *rit << " ";
        rit++;
    }
    cout << endl;
}
void TestList1()
{
    list<int> l1; // 构造空的l1
    list<int> l2(4, 100);// l2中放4个值为100的元素
    list<int> l3(l2.begin(), l2.end());// 用l2的[begin(), end()）左闭右开的区间构造l3
    list<int> l4(l3);// 用l3拷贝构造l4
    int arr[] = { 1,2,3,4,5,6 };
    list<int> l5(arr, arr + sizeof(arr) / sizeof(arr[0])); // 以数组为迭代器区间构造l5
    list<int> l6{ 9,8,7,6 };// 列表格式初始化C++11
    print_list(l1);
    print_list(l2);
    print_list(l3);
    print_list(l4);
    print_list(l5);
    print_list(l6); 
}

int main()
{
	TestList1();
	return 0;
}

1.2.3capacity（容量相关）

void TestList2()
{
    list<int> l1; // 构造空的l1
    list<int> l2(4, 100);// l2中放4个值为100的元素
    cout << l1.size() << endl;
    cout << l2.size()<<endl;

}
int main()
{
	TestList2();
	return 0;
}

1.2.4  element access（元素访问）

1.2.5 modifiers（链表修改）

insert 插入元素并不会导致迭代器失效，例如：相较于 vector 中的 insert，list 中的 insert 并不会去扩容挪动数据，而 vector 中的 insert 可能会进行扩容挪动数据，最终导致迭代器失效。list 中的删除元素接口会导致迭代器失效，失效的只有指向被删除节点的迭代器，其他迭代器不会受到影响。

void TestList3()
{
    list<int> l1; // 构造空的l1
    list<int> l2(4, 100);// l2中放4个值为100的元素
    cout << l1.size() << endl;
    cout << l2.size()<<endl;
    l1.push_front(22);
    l1.push_front(11);
    print_list(l1);
    l2.insert(l2.begin(), 99);
    print_list(l2);
    list<int>::iterator it = l2.begin();
    int k = 3;
    while (k--)
    {
        it++;
    }
    l2.insert(it, 0);
    print_list(l2);
    l2.clear();
    print_list(l2);
    cout << "**********************";
}
int main()
{
	TestList3();
	return 0;
}

1.2.6 operation（对链表的一些操作）

splice() 函数主要用于在列表中进行元素的转移操作。 它可以将一个列表中的部分或全部元素转移到另一个列表中。可以指定要转移的元素范围以及目标插入位置等，实现了高效灵活的元素移动和重组。

remove 函数相当于一直遍历列表，然后 erase 删除指定元素。

unique 函数主要用于移除列表中相邻的重复元素。它使得容器中只保留不重复的元素序列，但需要注意的是，它并不保证完全去除所有重复元素，只是处理相邻的重复项，通常也需要结合其他操作来实现完全去重。

merge() 函数主要用于将两个已排序的序列合并成一个新的已排序序列。 它会按照排序顺序将一个序列中的元素与另一个序列中的元素合理地组合在一起，形成一个合并后的有序序列。需要注意的是，在合并之前，两个源序列本身需要是已经排序好的。

链表逆置可以使用 list 自身的接口，也可以使用算法库中的 reverse，二者没有什么区别。链表排序只能使用 list 自身的 sort() 接口（底层是利用归并排序），不能使用算法库的 sort，因为算法库中的 sort 底层是通过快排来实现的，而快排中会涉及到三数取中需要迭代器 - 迭代器，链表不能很好的支持。虽然链表提供了排序接口，但是用链表对数据排序意义不大，效率太低了，更希望用 vector 来对数据进行排序。

二、从功能角度迭代器分类：

其中 forward_list 、 unordered_xxx 都是单向迭代器； list 、 map 、 set 都是双向迭代器； vector 、 string 、 deque 都是随机迭代器。对迭代器的这种分类方式，是由容器的底层结构来决定的。

算法库中也有一个 sort() 函数，但是其支持的是随机迭代器，而 list 是一种双向迭代器，所以 list 无法调用算法库中的 sort() 。