【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相关参数后的简化接口：

示例一：
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 的使用

#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类对象的容量操作

#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类对象的访问

#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 和 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、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 函数？
解释如下：

1. 迭代器类型限制

• 标准算法std::sort的局限性
  通用算法std::sort要求输入迭代器为随机访问迭代器（如std::vector或std::deque的迭代器），因为它需要快速跳转到任意位置（例如快速排序的分区操作）。

  而std::list的迭代器是双向迭代器，仅支持顺序移动（++和--），无法直接支持随机访问操作。
  因此，std::list必须实现自己的sort()成员函数，使用适合链表结构的排序算法（如归并排序）。

• std::reverse的可用性
  std::reverse只需要双向迭代器，理论上可以直接用于std::list，但作为成员函数的reverse()可能在实现上更高效，比如通过交换指针而不是移动元素。这样对于链表结构来说，操作更高效。

---

2. 操作效率优化

• 链表结构的特殊性
  链表节点在内存中非连续分布，但每个节点包含前驱和后继指针。成员函数sort()和reverse()可以通过修改指针指向高效重组链表，无需移动元素本身。

  • 例如，reverse()只需遍历链表并交换每个节点的前驱和后继指针，时间复杂度为$O(n)$。
  • sort()使用归并排序，通过分割和合并链表片段实现，时间复杂度为$O(n\log n)$。

• 避免元素拷贝开销
  通用算法std::sort需要交换元素值，而链表排序通过调整指针即可完成，避免了拷贝或移动元素的成本。

---

总结
std::list的成员函数sort()和reverse()是因其数据结构特性和效率优化需求而存在的，既弥补了通用算法的局限性，也充分利用了链表的操作优势。