目录
前言
list
,作为STL中的双向链表容器,以其灵活的操作方式和特定的性能特性,在众多编程任务中崭露头角。与数组等其他容器相比,list
有着自己独特的内部结构和行为模式。它不需要像数组那样进行大规模的内存重新分配来适应元素的增减,而是能够高效地在任意位置进行元素的插入和删除操作。无论是在需要频繁修改元素顺序的算法中,还是在构建复杂的数据结构关系时,list
都能发挥不可替代的作用。
本文将深入剖析C++ STL中的list
容器,从它的基本定义、内部结构,到常用的成员函数操作,再到实际应用中的性能考量等多方面进行全面的介绍,带领读者逐步揭开list
容器的神秘面纱,领略其在C++编程世界中的强大功能和独特价值。
list的构造
还是那句话,要使用,就要先创造
list提供了多种构造方式,以满足不同的初始化需求。以下是常见的list构造方法
方法一:无参构造
std::list<int> emptyList;
朴实无华,创建一个空的list类对象
方法二:用 n 个 x 值初始化一个list对象
list<int> lt(n,x);
注意:使用这种构造方式时,如果只传递数量,而没有传递初始值,则会调用该类型默认的构造函数对list中的元素进行初始化
方法三:使用迭代器区间初始化
std::vector<int> vec = {1,2,3,4,5};
std::list<int> 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<int> 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<int> myList;
myList.push_back(10);// 使用 push_back 在列表末尾插入元素
尾删——pop_back函数
pop_back是list提供的一个成员函数,用于移除列表中的最后一个元素。
函数造型:
void pop_back();
基本用法:
std::list<int> myList = {10, 20, 30, 40, 50};
myList.pop_back();
list的迭代器
在【C++】一文熟练STL容器——vector 中,我们说过,迭代器类似于指针
怎么用指针,怎么就用迭代器
但迭代器只是接近指针,并不是真正的原生指针,只是用封装屏蔽了底层差异
list的迭代器就不是原生指针,而是一个 指向list某个结点 的指针
它的造型是这样的
typedef ListNode<T> Node;
Node* _node;
这个_node 指向的数据的造型,是这样的
struct ListNode {
T data;
ListNode<T>* prev;
ListNode<T>* next;
}
这个结构体,就是list存储实际数据的载体
它内部有两个指针,分别指向前一个ListNode类对象和下一个ListNode类对象,以此达到连接的效果,让不连续的每个ListNode对象在逻辑上成为一个线性结构
我们对指针进行++,就是希望指针直接指向下一个数据
而对list迭代器进行++,就是希望迭代器直接指向下一个ListNode对象
ListNode的原生指针显然做不到这一点,因为list的数据元素并不是连续的,盲目对原生指针 ++ ,指针会指向一个未知的位置,从而引发解引用错误
因此list迭代器就是对ListNode的原生指针进行封装,内部实现一系列方法,指向外提供简单的接口,以此屏蔽底层的差异。
迭代器函数——begin函数
begin函数用于返回一个指向列表中第一个元素的迭代器。
函数造型:
iterator begin();
返回值说明:
- iterator可修改元素的迭代器。
基本用法:
std::list<int> myList = {10, 20, 30, 40, 50};
auto it = myList.begin();//返回第一个迭代器
迭代器函数——end函数
end函数用于返回一个指向列表末尾的迭代器。
函数造型:
iterator end();
返回值说明:
- iterator:可修改元素的迭代器。
基本用法:
std::list<int> myList = {10, 20, 30, 40, 50};
auto it = myList.end();
使用 begin() 与 end() 对 list对象 进行遍历
std::list<int> 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<int> myList = {1, 2, 3};
myList.insert(myList.end(), 4);//等同于push_back
迭代器函数——erase函数
erase函数用于移除列表中的一个或多个元素。
函数造型:
iterator erase(const_iterator pos);
参数说明:
- pos指向要删除的单个元素的迭代器。
返回值说明:
- 返回指向下一个元素的迭代器。
基本用法:
std::list<int> myList = {1, 2, 3, 4, 5};
it = myList.erase(it);
迭代器失效
list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只有指向被删除节点的迭代器,其他迭代器不会受到影响。
补充函数
list提供的接口函数不止我们介绍的这些,但我们介绍的都是重要的,建议记住
以下是一些不常用的函数
与容量相关
与元素访问相关
与交换相关
结语
我们对 list 容器的探索即将告一段落,但探索的道路永无止境。list作为C++ STL中一个重要的组成部分,与我们之前和后续要学习的其他容器和算法都有着千丝万缕的联系。比如,如何结合迭代器更高效地操作list,或者如何与其他容器配合使用来解决复杂的问题,这些都是值得我们深入研究的课题。希望大家以此次对list的学习为起点,不断探索和实践,进一步挖掘C++ STL的强大潜力。