【C++】一文吃透STL容器——list

前言

list，作为STL中的 双向链表 容器，以其灵活的操作方式和特定的性能特性，在众多编程任务中崭露头角。与数组等其他容器相比，list有着自己独特的内部结构和行为模式。它不需要像数组那样进行大规模的内存重新分配来适应元素的增减，而是能够高效地在任意位置进行元素的插入和删除操作。无论是在需要频繁修改元素顺序的算法中，还是在构建复杂的数据结构关系时，list都能发挥不可替代的作用。 本文将深入剖析C++ STL中的list容器，从它的基本定义、内部结构，到常用的成员函数操作，再到实际应用中的性能考量等多方面进行全面的介绍，带领读者逐步揭开list容器的神秘面纱，领略其在C++编程世界中的强大功能和独特价值。

list的构造

还是那句话， 要使用，就要先创造 list提供了多种构造方式，以满足不同的初始化需求。以下是常见的list构造方法 方法一:无参构造 std::list emptyList;

朴实无华，创建一个空的list类对象 方法二:用 n 个 x 值初始化一个list对象 list lt(n,x); 注意: 使用这种构造方式时，如果只传递数量，而没有传递初始值，则会调用该类型默认的构造函数对list中的元素进行初始化 方法三:使用迭代器区间初始化 std::vector vec = {1,2,3,4,5}; std::list lt(vec.begin(),vec.end()); STL容器的宗门底蕴，只要有迭代器，均可以使用迭代器对容器进行初始化

list的常用函数

知道了如何创造，接下来就是如何使用了 见识一list容器提供的常用函数

头插——push_front函数

push_front 是 std::list 提供的一个成员函数，用于在列表的前端插入一个新元素。 函数造型: void push_front(const T& value); 参数说明:

• const T& value:要插入的元素的常量引用。 基本使用： std::list myList; myList.push_front(10);//使用 push_front 在列表前端插入元素

头删——pop_front函数

pop_back 是 std::list 提供的一个成员函数，用于移除列表中的最后一个元素。 函数造型: void pop_back(); 基本用法: myList.pop_back();

尾插——push_back函数

push_back()用于在列表的末尾插入一个新元素。 函数造型: void push_back(const T& value); 参数说明:

• const T&value要插入的元素的常量引用。 基本用法: std::list myList; myList.push_back(10);// 使用 push_back 在列表末尾插入元素

尾删——pop_back函数

pop_back是list提供的一个成员函数，用于移除列表中的最后一个元素。 函数造型: void pop_back(); 基本用法: std::list myList = {10, 20, 30, 40, 50}; myList.pop_back();

list的迭代器

在 中，我们说过，迭代器类似于指针 怎么用指针，怎么就用迭代器 但迭代器只是接近指针，并不是真正的原生指针，只是用封装屏蔽了底层差异 list的迭代器就不是原生指针，而是一个 指向list某个结点 的指针 它的造型是这样的 typedef ListNode Node; Node* _node; 这个_node 指向的数据的造型，是这样的 struct ListNode { T data; ListNode* prev; ListNode* next; } 这个结构体，就是list存储实际数据的载体 它内部有两个指针，分别指向前一个ListNode类对象和下一个ListNode类对象，以此达到连接的效果，让不连续的每个ListNode对象在逻辑上成为一个线性结构 我们对指针进行++，就是希望指针直接指向下一个数据 而对list迭代器进行++,就是希望迭代器直接指向下一个ListNode对象 ListNode的原生指针显然做不到这一点，因为list的数据元素并不是连续的，盲目对原生指针 ++ ，指针会指向一个未知的位置，从而引发解引用错误 因此list迭代器就是对 ListNode的原生指针进行封装，内部实现一系列方法，指向外提供简单的接口，以此屏蔽底层的差异。

迭代器函数——begin函数

begin函数用于返回一个指向列表中第一个元素的迭代器。 函数造型: iterator begin(); 返回值说明:

• iterator可修改元素的迭代器。 基本用法: std::list myList = {10, 20, 30, 40, 50}; auto it = myList.begin();//返回第一个迭代器

迭代器函数——end函数

end函数用于返回一个指向列表末尾的迭代器。 函数造型: iterator end(); 返回值说明:

• iterator:可修改元素的迭代器。 基本用法: std::list myList = {10, 20, 30, 40, 50}; auto it = myList.end(); 使用 begin() 与 end() 对 list对象 进行遍历 std::list myList = {10, 20, 30, 40, 50}; // 使用 begin() 和 end() 遍历并输出列表中的元素 std::cout « “列表中的元素: “; for (auto it = myList.begin(); it != myList.end(); ++it) { std::cout « *it « " “; } 运行结果: ****

迭代器函数——insert函数

insert函数用于在列表的指定位置插入一个或多个新元素。 list的底层是双向链表，使用insert进行插入，不会影响其他存在的数据。 函数造型: iterator insert(const_iterator pos, const T& value); 参数说明:

• pos:插入位置的迭代器，指向要插入新元素的位置。
• value要插入的元素的常量引用或右值引用。 基本用法: std::list myList = {1, 2, 3}; myList.insert(myList.end(), 4);//等同于push_back

迭代器函数——erase函数

erase函数用于移除列表中的一个或多个元素。 函数造型: iterator erase(const_iterator pos); 参数说明:

• pos指向要删除的单个元素的迭代器。 返回值说明：
• 返回指向下一个元素的迭代器。 基本用法: std::list myList = {1, 2, 3, 4, 5}; it = myList.erase(it);

迭代器失效

list的底层结构为带头结点的双向循环链表 ，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只有指向被删除节点的迭代器，其他迭代器不会受到影响。

补充函数

list提供的接口函数不止我们介绍的这些，但我们介绍的都是重要的，建议记住 以下是一些不常用的函数 与容量相关 与元素访问相关 与交换相关

结语

我们对 list 容器的探索即将告一段落，但探索的道路永无止境。list作为C++ STL中一个重要的组成部分，与我们之前和后续要学习的其他容器和算法都有着千丝万缕的联系。比如，如何结合迭代器更高效地操作list，或者如何与其他容器配合使用来解决复杂的问题，这些都是值得我们深入研究的课题。希望大家以此次对list的学习为起点，不断探索和实践，进一步挖掘C++ STL的强大潜力。