《C++ STL list详解指南》：从接口实现到容器性能对比，掌握你对链表容器的高效使用！

用户11915063

发布于 2025-11-19 18:58:51

870

一. list 是什么？先搞懂底层结构

list 的本质是双向循环链表，且带有一个"哨兵位头结点"(不存储有效数据)，结构如下：

双向：每个字节包含前驱指针 (prev) 和后继指针 (next) ，支持向前，向后遍历；
循环：尾节点的 next 指向头结点，头结点的 prev 指向尾结点，形成闭环；
哨兵位头结点：避免插入/删除时判断"是否为空"”是否为头结点“的麻烦，简化代码逻辑

这种结构决定了 list 的核心特性：任意位置插入/删除效率高（O(1)），但不支持随机访问(访问元素需要遍历，O(N))

头文件包含：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

二. list核心接口使用：从构造到修改

list 的接口丰富，但重点掌握"构造，迭代器，容量，元素，访问修改’五大类即可满足日常开发需求，以下结合代码示例讲解

2.1 构造函数：初始化一个list

list 提供4种常用构造方式，覆盖"空容器，n个相同元素，拷贝，区间初始化"场景

构造函数	接口说明	代码示例
list()	构造空 list	list<int> l1;（空链表，仅含头结点）
list(size_type n, const T& val = T())	构造含 n 个 val 的 list	list<int> l2(3, 2);（元素：2,2,2）
list(const list& x)	拷贝构造	list<int> l3(l2);（l3 是 l2 的副本）
list(InputIterator first, InputIterator last)	用 [first, last) 区间构造	int arr[] = {1,2,3}; list<int> l4(arr, arr+3);（元素：1,2,3）

代码演示：

void test_list1()
{
	//展示其中两个，其实使用起来跟前面的vector差不多
	list<int> lt1;//无参构造
	list<int> lt2 = {1,2,3,4,5};
	list<int>::iterator it2 = lt2.begin();
	while (it2 != lt2.end())
	{
		cout << *it2 << " ";
		++it2;
	}
	cout << endl;

	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{
	test_list1();
}

2.2 迭代器：遍历list的 “指针”

list 的迭代器本质是 “结点指针的封装”，支持正向和反向遍历，核心接口如下(当然也可以使用范围for)：

函数声明	接口说明	特点
begin() / end()	正向迭代器：begin() 指向 list 第一个有效元素，end() 指向头结点（尾后位置）	对迭代器执行 ++ 操作，迭代器向后移动，用于正向遍历所有有效元素
rbegin() / rend()	反向迭代器：rbegin() 指向 list 最后一个有效元素，rend() 指向头结点（反向尾后位置）	对迭代器执行 ++ 操作，迭代器向前移动，用于反向遍历所有有效元素

迭代器知识补充：

2.3 容量与元素访问：判断空、查大小、取首尾

list 不支持随机访问（没有 operator[] 和 at()），仅提供 “判断空、获取大小、取首尾元素” 的接口：

函数声明	接口说明	代码示例（基于 l4 = {1,2,3,4}）
empty()	检测 list 是否为空，空则返回 true，非空返回 false	l4.empty();（返回 false，因 l4 含 4 个有效元素）
size()	返回 list 中有效元素的个数，单位为无符号整数（size_type）	l4.size();（返回 4，对应 l4 中的元素 1、2、3、4）
front()	返回 list 第一个有效元素的引用，支持读写操作（可直接修改元素值）	l4.front() = 10;（修改后 l4 变为 {10,2,3,4}）
back()	返回 list 最后一个有效元素的引用，支持读写操作（可直接修改元素值）	l4.back() = 40;（修改后 l4 变为 {10,2,3,40}）

注意：front() 和 back() 仅在 list 非空时使用，若为空会触发未定义行为（建议先 empty() 进行判断）

2.4 元素修改：插入，删除，清空

list 的核心优势在"修改操作",任意位置插入/删除仅需调整指针，效率极高，常用接口如下：

函数声明	接口说明	代码示例（基于 l4 = {1,2,3,4}）
push_front(const T& val)	在 list 头部（第一个个有效元素之前）插入值为 val 的元素	l4.push_front(0);（插入后 l4 变为 {0,1,2,3,4}）
pop_front()	删除 list 的第一个个有效元素	l4.pop_front();（删除后 l4 变回 {1,2,3,40}）
push_back(const T& val)	在 list 尾部（最后一个有效元素之后）插入值为 val 的元素	l4.push_back(5);（插入后 l4 变为 {1,2,3,4,5}）
pop_back()	删除 list 的最后一个有效元素	l4.pop_back();（删除后 l4 变回 {1,2,3,4}）
insert(iterator pos, const T& val)	在迭代器 pos 指向的位置之前插入值为 val 的元素，返回指向新插入元素的迭代器	auto it = l4.begin(); ++it; l4.insert(it, 15);（it 初始指向 2，插入后 l4 变为 {1,15,2,3,4}）
erase(iterator pos)	删除迭代器 pos 指向的元素，返回指向被删除元素下一个元素的迭代器	it = l4.begin(); ++it; l4.erase(it);（it 指向 15，删除后 l4 变回 {1,2,3,4}）
clear()	清空 list 中所有有效元素（仅保留头结点），清空后 size() 为 0	l4.clear();（清空后 l4 无有效元素，l4.size() 返回 0）

2.5 常用算法与操作：find、sort、unique、reverse

list 提供多个实用成员函数和适配的通用算法，用于处理查找、排序、去重、反转等场景，具体如下：

函数类型	函数声明 / 调用方式	接口说明	代码示例（基于 list<int> l = {1,1,2,6,3,4,5}）	注意事项
算法函数（需包含 <algorithm>）	find(iterator first, iterator last, const T& val)	在 [first, last) 区间查找值为 val 的元素，返回首个匹配元素的迭代器；若未找到，返回 last	#include <algorithm> auto it = find(l.begin(), l.end(), 4); // it 指向元素 4（值为4的位置）	1. 属于 STL 通用算法，非 list 成员函数 2. 时间复杂度 O(N)，需遍历查找
成员函数	sort()	对 list 元素进行升序排序（默认按 < 比较）	l.sort(); // 排序后 l = {1,1,2,3,4,5,6}	1. list 不支持随机访问，不能用 STL 通用 sort 算法，需用自身成员函数 2. 底层通常为归并排序，时间复杂度 O(N log N)
成员函数	unique()	移除连续重复的元素（只保留第一个），返回指向最后一个有效元素后位置的迭代器	l.sort(); // 先排序使重复元素连续：{1,1,2,3,4,5,6} l.unique(); // 去重后 l = {1,2,3,4,5,6}	1. 仅移除“连续重复”元素，需先 sort() 使相同元素相邻才能完全去重 2. 时间复杂度 O(N)
成员函数	reverse()	反转 list 中所有元素的顺序	l.reverse(); // 原 l={1,1,2,3,4,5,6} → 反转后 {6,5,4,3,2,1,1}	仅调整节点指针方向，时间复杂度 O(N)，效率极高

代码演示：

void test_list2()
{
	list<int> lt1;//无参构造
	list<int> lt2 = { 1,2,3,4,5 };
	auto pos = find(lt2.begin(),lt2.end(),3);
	if (pos != lt2.end())
	{
		lt2.insert(pos, 30);//pos没有失效，因为没有扩容
		lt2.erase(pos);//pos失效了
		//cout << *pos << endl;
	}

	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_list3()
{
	list<int> lt2 = { 1,2,4,3,5 };
	//sort(lt2.begin(), lt2.end());//不支持
	lt2.sort();

	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test_list4()
{
	list<int> lt3 = { 1,2,2,3,3,2,3,4,5 };
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl;
	lt3.sort();
	lt3.unique();//去重
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{
	//test_list1();
	test_list2 ();
	test_list3();
	test_list4();
}

三. list迭代器失效：只在删除时发生

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

迭代器失效是使用 list 时的核心注意点，但其失效规则比 vector 简单得多：

插入时： list 插入仅需调整指针，不会移动现有节点，因此所有迭代器都不会失效；
删除时： 仅指向 “被删除节点” 的迭代器失效，其他迭代器（指向未删除节点）不受影响

补充知识点：splice的使用

void test_list5()
{
	//将4这个节点挪到头位置
	list<int>lt4 = { 1,2,3,4,5 };
	for (auto e : lt4)
	{
		cout << e << " ";
	}
	cout << endl;
	auto pos = find(lt4.begin(), lt4.end(),4);
	lt4.splice(lt4.begin(), lt4, pos);
	for (auto e : lt4)
	{
		cout << e << " ";
	}
	cout << endl;

}

int main()
{
	//test_list1();
	//test_list2 ();
	//test_list3();
	//test_list4();
	test_list5();
}

四. 什么时候用list？什么时候用vector？

list 和 vector 是 STL 中最常用的两个序列容器，但适用场景完全不同，核心差异如下表：

	vector	list
底层结构	动态顺序表，一段连续空间	带头结点的双向循环链表
随机访问	支持随机访问，访问某个元素效率O(1)	不支持随机访问，访问某个元素效率O(N)
插入和删除	任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低	任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)
空间利用率	底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高	底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器	原生态指针	对原生态指针(节点指针)进行封装
迭代器失效	在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效	插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景	需要高效存储，支持随机访问，不关心插入删除效率	大量插入和删除操作，不关心随机访问