Clist上list类的常用接口介绍

JAY.LIN 收录于 C

2025-03-13 约 4129 字预计阅读 9 分钟

https://bing.ee123.net/img/rand?artid=145976786

【C++】list(上)：list类的常用接口介绍

前言

**一、list的介绍（包含list类中typedef的部分类型别名介绍）
二、list类的常用接口说明（vector类对象的常见构造、容量操作、遍历操作和修改操作等接口，以及一些list特有的操作（比如 splice、merge、remove、remove_if 等）介绍）
三、list类的成员函数sort和reverse 与算法库中sort和reverse的差异**

一、list的介绍

C++中的 std::list 是标准模板库（STL）提供的双向链表容器，其接口设计专注于高效插入和删除操作。std::list 底层通常实现为一个带哨兵节点的双向循环链表，这种设计显著简化了边界条件的处理。它的接口包括构造函数、元素访问方法、修改容器的操作、迭代器相关的函数，还有一些list特有的操作（比如 splice、merge、remove、remove_if 等）。

**在C++标准库的 std::list 中，allocator（内存分配器）是模板的第二个参数，通常可以忽略，使用默认的即可。但在需要特殊内存管理时，可以自定义allocator，不过这种情况相对少见。
默认内存分配器已足够高效，自定义内存分配器应仅在性能分析表明有必要时才会使用，所以后续介绍list接口时，只会考虑大多数情况，忽略allocator（直接使用默认的）这个参数，简化list的使用。**

list 类中typedef了很多类型别名，以下代码展示了一些常用的类型别名：

typedef T value_type;// 其中 T 是 vector 的第一个模板参数
typedef size_t size_type;
// size_t 是 C++ 标准库中定义的一个类型别名，它通常是一个无符号整数类型。其可能的定义方式如下:
// 64 位系统下: typedef unsigned long long size_t; 
// 32 位系统下: typedef unsigned int size_t; 
typedef T& reference;
typedef const T& const_reference;
typedef Allocator allocator_type;

二、list的常用接口介绍

1.list类对象的常见构造

忽略allocator相关参数后的简化接口：

(constructor)构造函数声明	接口说明
list ()	构造空的list
list ( size_type n, const value_type& val =value_type() )	构造的list中包含n个值为val的元素
list ( const list& x )	拷贝构造函数
template < class InputIterator > list (InputIterator first, InputIterator last ）	用迭代器范围 [begin, end) 内的元素构造链表
list ( initializer_list< value_type > il ）	初始化列表构造（C++11新增，了解用法）

示例一：

list ( ) ；

list ( size_t n, const T& val =T() )；

list ( const list& x )；

#include <list>
using namespace std;

int main()
{
	// list();
	list<int> it1;// 构造空的list，size为0

	// list( size_t n, const T& val =T() );
	list<int> it2(5, 22); // 构造的list中包含5个值为22的元素

	// list( const list& x );
	list<int> it3(it2); // 用it2拷贝构造it3
	return 0;
}

**示例二：

template < class InputIterator >

list (InputIterator first, InputIterator last ）；**

#include <vector>
#include <list>
using namespace std;

int main()
{
	list<int> it = { 1, 2, 3, 4 }; // 初始化列表的构造方式
	list<int> it1(it.begin(), it.end());  // list的迭代器是双向迭代器

	int arr[] = { 4, 5, 6, 7, 8, 9 };
	list<int> it2(arr + 2, arr + 5); // 指针作为随机访问迭代器 

	vector<int> vec = { 10, 11, 12, 13, 14, 15 }; 
	list<int> it3(vec.begin() + 1, vec.end() - 2); // vector的迭代器是随机访问迭代器
	return 0;
}

**示例三：

list ( initializer_list< value_type > il ）；**

#include <list>
using namespace std;

int main()
{
	list<int> it1{ 1, 2, 3 }; // 调用初始化列表构造vector对象时要使用花括号

	list<int> it2 = { 5, 6, 7 };
	return 0;
}

2.list iterator 的使用

接口	功能
begin	获取第一个数据位置的iterator/const_iterator
end	获取最后一个数据的下一个位置的iterator/const_iterator

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1 = { 1,3,5,7,9 };
	list<int>::iterator it1 = ls1.begin();
	// 普通list对象调用 iterator begin();
	// 返回指向list对象中第一个元素的普通迭代器,允许修改list对象中的元素
	while (it1 != ls1.end())
	{
		(*it1)++;
		cout << *it1 << ' ';
		++it1;
	}
	cout << endl;

	const list<int> ls2 = { 1,3,5,7,9 };
	list<int>::const_iterator it2 = ls2.begin();
	// const list对象调用 const_iterator begin() const;
	// 返回指向const list对象第一个元素的const迭代器,只允许读取const list对象中的元素，不能修改
	while (it2 != ls2.end())
	{
		cout << *it2 << ' ';
		++it2;
	}
	cout << endl;
	return 0;
}

3.list类对象的容量操作

接口	功能
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "ls1的有效节点个数:" << ls1.size() << endl;
	cout << "ls1是否为空:" << ls1.empty() << endl;
	

	list<int> ls2;
	cout << "ls2的有效节点个数:" << ls2.size() << endl;
	cout << "ls2是否为空:" << ls2.empty() << endl;
	return 0;
}

4.list类对象的访问

接口	功能
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "ls1的首节点中的值:" << ls1.front() << endl;
	cout << "ls1的尾节点中的值:" << ls1.back() << endl;

	return 0;
}

5.list类对象的修改操作

5.1 push_front、push_back、insert 和 resize（插入）

接口	功能
push_front	在list首元素前插入值为val的元素
push_back	在list尾部插入值为val的元素
insert	在指定迭代器位置前插入元素，返回新插入元素的迭代器
resize	用于调整链表的大小

示例一（push_front 和 push_back的使用）：

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.push_front(10);
	cout << "在list首元素前插入值为10的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.push_back(20);
	cout << "在list尾部插入值为20的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

**示例二（insert的使用）：

iterator insert (const_iterator position, const T& val);**

#include <list>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	auto it = find(ls1.begin(), ls1.end(), 3); // algorithm库里的find函数
	ls1.insert(it, 100);
	cout << "在元素3位置前插入值为100的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

**示例三（resize的使用）：

void resize (size_t n, T val = T());**

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.resize(3);
	cout << "把有效节点的个数缩到3个:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.resize(6, 10);
	cout << "把有效节点的个数扩到6个，并且全用元素10扩充:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

5.2 pop_front、pop_back、clear 和 erase（删除）

接口	功能
pop_front	删除list中第一个元素
pop_back	删除list中最后一个元素
clear	清空list中的有效元素
erase	移除 pos 处元素，返回下一元素的迭代器

示例一（pop_front、pop_back 和 clear的使用）：

#include <list>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5,6,7,8,9 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.pop_front();
	cout << "删除list中第一个元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.pop_back();
	cout << "删除list中最后一个元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	ls1.clear();
	cout << "清空list中的有效元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

**示例二（erase的使用）：

iterator erase (iterator position);**

#include <list>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3,4,5 };
	cout << "链表初始状态:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;

	auto it = find(ls1.begin(), ls1.end(), 3); // algorithm库里的find函数
	ls1.erase(it);
	cout << "移除值为3的元素:";
	for (auto& it : ls1)
	{
		cout << it << ' ';
	}
	cout << endl;
	return 0;
}

5.3 成员函数swap

swap成员函数是用于高效交换两个list对象的内容的函数

#include <list>
using namespace std;

int main()
{
	list<int> ls1{ 1,2,3 };
	list<int> ls2{ 10,20,30,40 };
	ls1.swap(ls2);
	return 0;
}

6.list类对象的其它操作

6.1 splice

将元素从一个链表转移到另一个链表，无需拷贝或移动元素，操作高效

**示例一（将 x 链表中 i 指向的元素转移到当前链表的 pos 位置前）：

void splice (iterator position, list& x, iterator i);**

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 9,5,2,7 };
	list<int> lst2 = { 5,2,0 };
	lst1.splice(--lst1.end(), lst2, lst2.begin()); 
	// 将 lst2 链表中起始位置的元素转移到当前链表的最后一个元素前
	return 0;
}

**示例二（将 x 链表中 [first, last) 范围的元素转移到当前链表的 pos 位置前）：

void splice (iterator position, list& x, iterator first, iterator last);**

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 9,5,2,7 };
	list<int> lst2 = { 5,2,0 };
	lst1.splice(--lst1.end(), lst2, lst2.begin(), --lst2.end());
	// 将 lst2 链表中指定范围的元素转移到当前链表的最后一个元素前
	return 0;
}

**示例三（将 x 链表的所有元素转移到当前链表的 pos 位置前）：

void splice (iterator position, list& x);**

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 9,5,2,7 };
	list<int> lst2 = { 5,2,0 };
	lst1.splice(--lst1.end(), lst2);
	// 将 lst2 链表的所有元素转移到当前链表的最后一个元素前
	return 0;
}

6.2 remove

删除链表中所有与给定值匹配的元素

#include <list>
using namespace std;

int main()
{
	list<int> lst = { 1,2,3,2,5,2 };
	lst.remove(2);
	return 0;
}

6.3 unique

删除有序链表中连续重复的元素，所以使用前通常需先排序

#include <list>
using namespace std;

int main()
{
	list<int> lst = { 1, 2, 2, 3, 3, 3, 4 };
	lst.unique(); // void unique();
	return 0;
}

6.4 merge

合并两个已排序的链表，合并后目标链表仍有序，原链表被清空

#include <list>
using namespace std;

int main()
{
	list<int> lst1 = { 1, 3, 5 };
	list<int> lst2 = { 2, 4, 6 };
	lst1.merge(lst2); // 默认排升序 
	// 合并结果: lst1 {1,2,3,4,5,6}, lst2 为空

	// 自定义降序合并
	list<int> lst3 = { 5, 3, 1 };
	list<int> lst4 = { 6, 4, 2 };
	lst3.merge(lst4, greater<int>()); // 传 greater<int>() 仿函数自定义降序排序
	// 合并结果: lst3 {6,5,4,3,2,1}, lst4 为空
	return 0;
}

6.5 成员函数sort和reverse 与算法库中sort和reverse的差异

其实标准算法库中实现了std::sort和std::reverse这样的算法，那么list为什么还要自己再创建一套sort和reverse 成员函数呢？为什么不直接调用算法库里的 sort和reverse 函数？

解释如下：

迭代器类型限制
标准算法 std::sort 的局限性
通用算法 std::sort 要求输入迭代器为 随机访问迭代器 （如 std::vector 或 std::deque 的迭代器），因为它需要快速跳转到任意位置（例如快速排序的分区操作）。
而 std::list 的迭代器是双向迭代器 ，仅支持顺序移动（ ++ 和 -- ），无法直接支持随机访问操作。
因此， std::list 必须实现自己的 sort() 成员函数，使用适合链表结构的排序算法（如归并排序）。
std::reverse 的可用性
std::reverse 只需要双向迭代器，理论上可以直接用于 std::list ，但作为成员函数的 reverse() 可能在实现上更高效，比如通过交换指针而不是移动元素。这样对于链表结构来说，操作更高效。
操作效率优化
链表结构的特殊性
链表节点在内存中非连续分布，但每个节点包含前驱和后继指针。成员函数 sort() 和 reverse() 可以通过修改指针指向高效重组链表，无需移动元素本身。
例如， reverse() 只需遍历链表并交换每个节点的前驱和后继指针，时间复杂度为
O ( n ) O(n)
O
(
n
) 。
sort() 使用归并排序，通过分割和合并链表片段实现，时间复杂度为
O ( n log ⁡ n ) O(n \log n)
O
(
n
lo g
n
) 。
避免元素拷贝开销
通用算法 std::sort 需要交换元素值，而链表排序通过调整指针即可完成，避免了拷贝或移动元素的成本。
总结
std::list 的成员函数 sort() 和 reverse() 是因其 数据结构特性 和 效率优化需求 而存在的，既弥补了通用算法的局限性，也充分利用了链表的操作优势。