【C++】C++中的list

一、介绍

官方给的 list的文档介绍

简单来说就是：

list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素。

这个时候大家可能觉得，都是有序列表，那么和vector有什么区别和对比吗？实际上和我们学习数据结构时对链表和数组的对比很像，我来介绍一下：

std::list

std::list 是一个双向链表，支持在常数时间内对序列的任何位置进行插入和删除操作。
由于其链表的性质，list 不支持快速随机访问，即不能通过索引以常数时间访问元素（例如 list[5] 是非法的）。
list 更适用于元素频繁插入和删除的场景，尤其是在序列的头部和尾部，或者你不需要通过索引来访问元素。
迭代器失效问题较少，插入和删除操作不会导致除了被操作的元素之外的迭代器失效。
在内存中不是连续存储的，因此不支持指针算术运算，并且可能导致较差的缓存性能。

std::vector

std::vector 是一个动态数组，可以在末尾快速地添加或移除元素（均摊常数时间复杂度），而且支持快速随机访问，即可以以常数时间访问任意位置的元素。
在 vector 的中间或开头插入或删除元素可能会导致较高的性能开销，因为这些操作需要移动插入点之后（或删除点之后）的所有元素。
适用于需要经常随机访问元素，但对于插入和删除的频率较低的场景。
在内存中是连续存储的，这意味着可以使用指针算术，并且有助于优化缓存使用。
当 vector 重新分配更大的内存空间以容纳更多元素时，所有的迭代器、引用和指针都可能失效。

那么list到底长什么样子呢？上图片，是不是就好理解了

二、list的使用

作为STL(标准模板库)中的一个类，我们这篇blog的任务就是学习其的使用。

构造函数

构造函数	接口说明
list()	构造空的list
list (size_type n, const value_type& val = value_type())	构造的list中包含n个值为val的元素
list (const list& x)	拷贝构造函数
list (InputIterator first, InputIterator last)	用[first, last)区间中的元素构造list

上面虽然用了不少代名词，我们直接上代码例子分析自然就清楚了，分析在代码中。

（如果迭代器看不懂可以看这一篇【C++】C++中的vector-CSDN博客，里面详细介绍了）

#include <iostream>
#include <list>
using namespace std;
int main()
{
	//
	list<int> l1; // 构造空的l1
	list<int> l2(4, 100); // l2中放4个值为100的元素
	list<int> l3(l2.begin(), l2.end()); // 用l2的[begin(), end()）左闭右开的区间构造l3
	list<int> l4(l3); // 用l3拷贝构造l4
	// 以数组为迭代器区间构造l5
	int array[] = { 16,2,77,29 };
	std::list<int> l5(array, array + sizeof(array) / sizeof(int));
	// 用迭代器方式打印l5中的元素
	for (std::list<int>::iterator it = l5.begin(); it != l5.end(); it++)
		std::cout << *it << " ";
	std::cout << endl;

	// C++11范围for的方式遍历
	for (auto& e : l5)
		std::cout << e << " ";

	std::cout << endl;
	return 0;
}

其实我们可以看出来，list这个类和之前的使用类的方法是基本一致的，不过他需要一个<int>来确定这个序列容器的类型，比如int，char....，就是list<int>可以当成一个整体，和vector很像。

list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点

函数声明	接口说明
begin + end	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

PS：

1. begin 与 end 为正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动

2. rbegin(end) 与 rend(begin) 为反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动

上代码：

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

void print_list(const list<int>& l)
{
	// 注意这里调用的是list的 begin() const，返回list的const_iterator对象
	// 保护数据通过将l声明为常量引用，我们保证了在print_list函数内部无法修改列表l的内容。
	// 这意味着无法添加、删除或修改列表中的任何元素。这是一种良好的编程实践，
	// 特别是当函数的目的仅仅是读取数据而不修改数据时。
	for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
	{
		cout << *it << " ";
		//如果不同const 就通过
		//*it = 10; 编译不通过
	}

	cout << endl;
}
int main()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	// 使用正向迭代器正向list中的元素
	for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
		cout << *it << " ";
	cout << endl;
	// 使用反向迭代器逆向打印list中的元素
	for (list<int>::reverse_iterator it = l.rbegin(); it != l.rend(); ++it)
		cout << *it << " ";
	cout << endl;
	return 0;
}

常用的成员方法

list capacity

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

列表元素访问

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

list modifiers

函数声明	接口说明
push_front	在list首元素前插入值为val的元素
pop_front	删除list中第一个元素
push_back	在list尾部插入值为val的元素
pop_back	删除list中最后一个元素
insert	在list position 位置中插入值为val的元素
erase	删除list position位置的元素
swap	交换两个list中的元素
clear	清空list中的有效元素

上代码看实现：

#include <iostream>
#include <list>
#include <vector>
using namespace std;
void PrintList(list<int>& l)
{
	for (auto& e : l)
		cout << e << " ";
	cout << endl;
}
//===============================================================
// push_back/pop_back/push_front/pop_front
void TestList1()
{
	cout << "TestList1()" << endl;
	int array[] = { 1, 2, 3 };
	list<int> L(array, array + sizeof(array) / sizeof(array[0]));
	// 在list的尾部插入4，头部插入0
	L.push_back(4);
	L.push_front(0);
	PrintList(L);
	// 删除list尾部节点和头部节点
	L.pop_back();
	L.pop_front();
	PrintList(L);
}
//================================================================
// insert /erase 
void TestList2()
{
	cout << "TestList2()" << endl;
	int array1[] = { 1, 2, 3 };
	list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	// 获取链表中第二个节点
	auto pos = ++L.begin();
	cout << *pos << endl;
	// 在pos前插入值为4的元素
	L.insert(pos, 4);
	PrintList(L);
	// 在pos前插入5个值为5的元素
	L.insert(pos, 5, 5);
	PrintList(L);
	// 在pos前插入[v.begin(), v.end)区间中的元素
	vector<int> v {7, 8, 9 };
	L.insert(pos, v.begin(), v.end());
	PrintList(L);
	// 删除pos位置上的元素
	L.erase(pos);
	PrintList(L);
	// 删除list中[begin, end)区间中的元素，即删除list中的所有元素
	L.erase(L.begin(), L.end());
	PrintList(L);
}
// resize/swap/clear
void TestList3()
{
	cout << "TestList3()" << endl;
	// 用数组来构造list
	int array1[] = { 1, 2, 3 };
	list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));
	PrintList(l1);
	// 交换l1和l2中的元素
	list<int> l2;
	l1.swap(l2);
	PrintList(l1);
	PrintList(l2);
//使用resize将l2的大小先增加到5个元素，所有新添加的元素都将被赋值为99
	l2.resize(5, 99);
	PrintList(l2);
	// 将l2中的元素清空
	l2.clear();
	cout << l2.size() << endl;
}

int main()
{
	TestList1();
	TestList2();
	TestList3();
	return 0;
}

好了，目前通过上面这一段精简的代码，我们把常用的成员方法基本解决了，但是list的成员方法实在太多，很多操作都是很特殊，不常见的，但是如果刚好需要又非常方便，所以就是可以在需要的时候查官方文档。

list的迭代器失效

在之前我们学习过vector的迭代器会有失效的情况，原因很简单，指针失效了，那么list会不会有这种情况呢？答案是有的，前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。所以影响相对vector来说比较小。

理解了吗？两段代码来检测一下大家

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

void TestListIterator1()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
			l.erase(it);
		++it;
	}
}

void TestListIterator2()
{
	int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	list<int> l(array, array + sizeof(array) / sizeof(array[0]));
	auto it = l.begin();
	while (it != l.end())
	{
		l.erase(it++); // it = l.erase(it);
	}
}

int main()
{
	TestListIterator1();
	TestListIterator2();
	return 0;
}

是 TestListIterator1 出错还是 TestListIterator2 出错？

如果你一眼就看出了，那么恭喜你，你掌握了。

其实很简单，第一个当调用erase(it)后，it被删除，使得it失效。尝试在失效的迭代器上进行操作（比如递增++it）是未定义行为。

第二个，l.erase(it++)：这里使用了“后置递增”运算符，它创建了it的一个副本，然后将副本传递给erase方法。erase删除了当前迭代器指向的元素，然后it被递增，指向下一个元素。因为it在递增前已经复制给erase，所以即使在删除当前元素后，递增操作是在一个新的、未被修改的迭代器上进行的，这保证了迭代器的有效性。或者可以这样写，等价的：it = l.erase(it);：erase函数返回下一个有效的迭代器，然后将其赋值给it。这样，it始终保持有效，且指向当前元素的下一个元素。

三、结语

到此为止，我们已经把list的基本使用方法学习结束了，list的成员方法十分丰富，这篇文章就是介绍了常用的，让大家基本会使用，目前你也可以用这种双向列表来实现一些复杂的算法，我在下面了可以给大家写一个。等我有时间再出一篇，模拟实现list的blog，理解他的底层实现，有缘再见，朋友！

实现的经典算法

约瑟夫环问题（Josephus Problem）。这个问题的一个版本可以描述如下：N个人围成一圈，从第一个人开始报数，每报到M时，该人被淘汰，接着从下一个人开始继续报数，直到所有人都被淘汰。任务是按顺序输出被淘汰人的编号。

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

void JosephusProblem(int N, int M) {
    // 初始化人员列表，编号从1到N
    list<int> people;
    for (int i = 1; i <= N; ++i) {
        people.push_back(i);
    }

    auto it = people.begin(); // 迭代器指向第一个人
    while (!people.empty()) {
        // 模拟报数，M-1次移动迭代器（因为从当前人开始报数）
        for (int count = 1; count < M; ++count) {
            ++it;
            // 如果迭代器超过了末尾，重新从头开始
            if (it == people.end()) {
                it = people.begin();
            }
        }

        // 报到M，移除当前人，并输出编号
        cout << *it << " ";
        it = people.erase(it); // erase返回下一个元素的迭代器
        
        // 如果列表不为空，但迭代器已经到达末尾，需要重新指向开头
        if (it == people.end() && !people.empty()) {
            it = people.begin();
        }
    }
    cout << endl;
}

int main() {
    int N = 7; // 人数
    int M = 3; // 报数淘汰
    JosephusProblem(N, M);
    return 0;
}