【C++】12.list接口介绍

在C++标准库中，std::list 是一个基于双向链表实现的顺序容器，它支持高效的插入和删除操作，但无法直接通过下标进行随机访问。以下是关于 std::list 的简单介绍：

核心特性

1. 底层结构
   • 双向链表实现，每个节点包含数据、前驱指针（prev）和后继指针（next）。
   • 内存非连续分配，插入/删除节点只需调整指针，时间复杂度为 O(1)。
2. 操作效率
   • 优点：在任意位置插入/删除元素高效（如中间位置）。
   • 缺点：随机访问需要遍历链表，时间复杂度为 O(n)，不支持 operator[]。
3. 内存占用
   • 每个元素需要额外存储两个指针（内存开销较大）。

list的常用接口

1. 头文件与声明

#include <list>
std::list<T> myList;  // T为元素类型，如int、string等

2. 常用成员函数

一些简单接口和vector，string是一样的，这里就不介绍了

2.1insert()

如果我们要在第k个位置前插入一个元素

void test_list1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(2);
	lt.push_back(7);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;

	auto it = lt.begin();
	int k = 3;
	while (k--)
	{
		it++;
	}
	lt.insert(it, 30);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
}

例如这里我们想在第四个数之前插入一个元素，先让迭代器指向第四个元素，然后在这之前插入

其余两个接口也差不多，分别是在pos位置前插入n个val和在pos位置前插入其他容器的迭代器区间

void test_list1()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(2);
	lt.push_back(7);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;

    int k = 3;
    while (k--)
    {
	    it++;
    }

	// 在pos位置前插入3个30， pos指向2
	lt.insert(it, 3, 30);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;

	//在pos位置前插入v中所有的元素， pos指向2
	vector<int> v(2, 50);
	lt.insert(it, v.begin(), v.end());
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
}

2.2erase()

一个是删除pos位置的值，另一个是删除一个区间的值

用法是和insert差不多的

不过需要注意的是和vector一样，他们也有迭代器失效的问题，所以需要注意。

2.3迭代器划分

1. 单向迭代器（Forward Iterator）

• 定义：单向迭代器是最基础的迭代器类型，支持单向遍历容器中的元素。它只能向前移动，不能后退。
• 功能：
  • 通过 ++ 运算符向前移动迭代器。
  • 通过 * 运算符访问当前元素。
  • 支持比较操作（如 ==、!=），用于判断是否到达容器末尾。
• 应用场景：
  • 适用于只需要单向遍历的场景，如从输入流（如文件、标准输入）读取数据，或向输出流写入数据。
  • C++中的 std::forward_list 容器提供单向迭代器。

2. 双向迭代器（Bidirectional Iterator）

• 定义：双向迭代器在单向迭代器的基础上增加了向后遍历的能力。它支持向前和向后移动，但只能逐个元素遍历。
• 功能：
  • 支持 ++ 和 -- 运算符，实现向前和向后移动。
  • 支持所有单向迭代器的操作。
• 应用场景：
  • 适用于需要双向遍历容器元素的场景，如链表、集合（std::set）、映射（std::map）等。
  • 可以通过 std::reverse 等算法实现反向遍历。

3. 随机迭代器（Random Access Iterator）

• 定义：随机迭代器是功能最强大的迭代器类型，支持在容器中任意位置进行访问和操作。它类似于指针，支持随机访问和偏移量操作。
• 功能：
  • 支持所有双向迭代器的操作。
  • 支持通过 +、- 运算符直接跳转任意位置（如 it + 5）。
  • 支持比较运算符（如 <、>），用于判断迭代器之间的位置关系。
  • 支持通过 [] 运算符进行索引访问。
• 应用场景：
  • 适用于需要快速访问容器中任意元素的场景，如数组、向量（std::vector）、双端队列（std::deque）等。
  • 支持高效的排序（std::sort）、二分查找（std::binary_search）等算法。

区别总结

总结

• 单向迭代器：适用于简单的前向遍历。
• 双向迭代器：适用于需要双向遍历的场景。
• 随机迭代器：适用于需要高效随机访问的场景，功能最强大。

2.4sort()

list中实现的sort与算法库中的sort是不一样的，底层实现不同

在C++中，std::list容器的成员函数sort()与算法库中的std::sort()都可以用来排序，但它们之间存在显著差异。以下是两者的主要区别：

1. 适用容器类型

• list.sort()： 是std::list类的成员函数，只能用于std::list容器。 因为std::list是双向链表，其元素在内存中不连续，无法直接通过索引访问。
• std::sort()： 是算法库<algorithm>中的通用函数，适用于所有支持随机访问迭代器的容器（如std::vector、std::deque、std::array等）。 这些容器的元素在内存中连续存储，支持通过索引快速访问。

2. 算法实现与性能

• list.sort()： 采用归并排序（Merge Sort），时间复杂度为 O(n log n)。 由于链表结构特点，归并排序在链表上实现效率较高，但整体性能通常低于std::sort()。
• std::sort()： 采用快速排序（Quick Sort）的变种（如Introsort），时间复杂度为 O(n log n)。 利用随机访问迭代器的特性，std::sort()在连续内存容器上的性能通常优于list.sort()。

3. 稳定性

• list.sort()： 是不稳定排序，相等元素的相对顺序可能改变。
• std::sort()： 是稳定排序，相等元素的相对顺序保持不变。

4. 内存使用

• list.sort()： 是原地排序，不需要额外内存空间。
• std::sort()： 通常需要额外内存空间（取决于具体实现），尤其是在元素较大或容器较小时。

5. 使用方式

• list.sort()： 直接调用成员函数，无需传递迭代器： std::list<int> myList = {3, 1, 4, 1, 5};myList.sort(); // 直接排序
• std::sort()： 需要传递容器的随机访问迭代器： std::vector<int> myVector = {3, 1, 4, 1, 5};std::sort(myVector.begin(), myVector.end()); // 排序范围 [begin, end)

总结对比

选择建议

• 如果需要对std::list排序，直接使用list.sort()。
• 如果需要对std::vector、std::deque等容器排序，且需要高性能和稳定性，优先使用std::sort()

2.5merge()

可以看到将两个链表归并在一起的前提是两个链表是有序的

所以需要先将两个链表排序。

void test_list3()
{
	std::list<double> first, second;

	first.push_back(3.1);
	first.push_back(2.2);
	first.push_back(2.9);

	second.push_back(3.7);
	second.push_back(7.1);
	second.push_back(1.4);

	first.sort();
	second.sort();

	first.merge(second);
}

调试窗口可以看到归并后，另一个链表就为空了

2.6unique()

这个函数接口是用来去重的，不过也需要先排序再去重，因为是将几个连续相等的元素去重，如果不连续，可能去重不干净

void test_list4()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(7);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
    
    //lt.sort();
	lt.unique();
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;

}

先来测试一下不排序前去重

再来看一下排序后的去重

2.7remove()

移除指定值的元素

void test_list5()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(7);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;

	lt.remove(3);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
}

2.8remove_if()

在C++中，Predicate（谓词） 是一个通用的编程概念，指返回布尔值（bool）的可调用对象（函数、函数对象、lambda表达式等），用于判断某个条件是否成立。它是泛型编程和STL算法中的核心工具，常用于自定义条件判断。

其实就是在remove的基础上加上了一个判断条件，例如我们通过一个仿函数或者lambda表达式写一个判断奇偶数，然后在调用remove_if()时作为参数，就可以指定移除我们想删除的奇数或者偶数。

struct is_odd 
{
	bool operator() (const int& value) { return (value % 2) == 1; }
};

void test_list6()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(5);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(7);
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;

	lt.remove_if(is_odd());
	for (auto e : lt)
	{
		cout << e << ' ';
	}
	cout << endl;
}

例如上面代码中，我们想移除奇数

2.9splice()

第一个版本 （1） 将 x 的所有元素拼接到容器中的pos位置前。 第二个版本 （2） 仅将 i 指向的元素从 x 传输到容器中的pos位置前。 第三个版本 （3） 将范围 [first，last] 从 x 传输到容器中的pos位置前。

void test_list7()
{
	list<int> lt1, lt2;
	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(5);
	lt1.push_back(3);
	lt1.push_back(2);

	lt2.push_back(7);
	lt2.push_back(8);
	lt2.push_back(9);

	cout << "lt1:";
	for (auto e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	cout << "lt2:";
	for (auto e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;
	auto it = lt1.begin();
	it++;//it指向3

	lt1.splice(it, lt2);
	cout << "lt1:";
	for (auto e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	cout << "lt2:";
	for (auto e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;
}

另外两个接口其实类似，就不一一演示了

关于list的介绍就到这里了