【C++进阶】深入STL之list：高效双向链表的使用技巧

????个人主页????：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” ????往期回顾????：探索迭代器失效 ????????期待您的关注 ????????

@TOC

---

在C++编程的广阔天地中，STL（Standard Template Library）以其高效、灵活和可重用的特性，成为开发者们不可或缺的工具之一。作为STL中重要的一员，list容器为我们提供了双向链表的功能，让我们在编程过程中能够更方便地处理需要频繁插入和删除元素的场景

前言：双向链表是链表数据结构的一种重要变体，它允许我们在链表的任何位置进行高效的插入和删除操作，而无需像数组那样进行大量的数据移动。list容器正是基于这种数据结构实现的，它提供了丰富的成员函数和迭代器接口，让我们能够轻松地管理和操作链表元素让我们一起走进STL中list容器的世界，探索其背后的奥秘吧！

因为前面我们学习string和vector，为list做足了铺垫，所以我们直接来看它的使用！

---

????1. list的基本概念

list 是 C++ 标准模板库 (STL) 中的一个容器，它基于双向链表实现。双向链表是一种动态数据结构，由一系列节点组成，每个节点包含数据元素和两个指向其他节点的指针

在介绍list的使用之前，我们先来看看它的结构：

实际上：list就是一个带头双向链表

---

????2. list的常用操作

????list的构造函数

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

int main()
{
    list<int> lt1(10, 5); //构造的list中包含n个值为val的元素
    list<int> lt2; // 构造空的list
    list<int> lt3(lt1); // 拷贝构造函数
    list<int> lt4(lt1.begin(), lt1.end()); // 用迭代器区间中的元素构造list
    return 0;
}

????list iterator的使用

关于迭代器，我们都可以将迭代器暂时理解成一个指针，该指针指向list中的某个节点

函数声明	接口说明
begin +end	返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin +rend	返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的reverse_iterator,即begin位置

迭代器打印列表：

int main()
{
    list<int> lt(10, 5);
	list<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        it++;
    }
    return 0;
}

注意：

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

---

????list的常用函数

函数声明	接口说明
empty	检测list是否为空，是返回true，否则返回false
size	返回list中有效节点的个数
front	返回list的第一个节点中值的引用
back	返回list的最后一个节点中值的引用

这几个函数都比较简单，前面也都接触过，我们就不细讲

---

⭐list的增删查改

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

代码示例：

int main()
{
	list<int> lt1 = { 2,3,4,5 };
	lt1.push_back(6);
	lt1.push_front(1);

	// 将值为100的元素用insert插入lt1;
	lt1.insert(++lt1.begin(), 100);

	// 用erase删除lt1中的一个头部元素
	auto it1 = lt1.begin();
    it1 = lt1.erase(lt1.begin());
	// auto it1 = lt1.begin(); // 这里出现了迭代器失效
	while (it1 != lt1.end())
	{
		cout << *it1 << " ";
	    it1++;
	}
	    cout << endl;
	return 0;
}

在演示中，由于我们使用erase删除时，已经将该节点删除了，然后迭代器指向的该节点是一个无效的节点导致了迭代器失效！因此迭代器失效也存在list中

在这几个函数中，insert和erase当然又是最棘手的，但是它们的使用方法和vector其实是差不多的

当然除了插入删除，list中还有sort排序，swap交换和clear清除

代码示例：

int main()
{
	list<int> lt1 = { 1,4,3,2,5 };
	list<int> lt2 = { 6,9,8,7,0 };

	cout << "lt1: ";
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "lt2: ";
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
	lt1.swap(lt2); // 交换两个容器里面的元素
	cout << "lt1(after swap): ";
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "lt2(after swap): ";
	for (auto e : lt2)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "clear lt2";
	cout << endl;
	lt2.clear(); // 清除lt2中的元素
	cout << "lt1: ";
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

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

	lt1.sort(); // 将lt1中的元素排序
	cout << endl;
	cout << "after sort lt1: ";
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

注意：

• list的clear()是将链表除头节点外全部清除
• list的sort()在排序时，默认是进行升序排序

---

????3. list迭代器失效

迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响

void test_list()
{
	list<int> l= { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	auto it = l.begin();
	while (it != l.end())
	{
	// erase()函数执行后，it所指向的节点已被删除，因此it无效，在下一次使用it时，必须先给其赋值
		l.erase(it);
		++it;
	}
}

解决迭代器失效的办法就是在遇到迭代器失效时，我们要对迭代器重新赋值

注意：erase返回的是被删除位置的下一个位置的迭代器!

void test_list()
{
	list<int> l= { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
	auto it = l.begin();
	while (it != l.end())
	{
		it = l.erase(it);
	}
}

---

????4. 总结拓展

????拓展：迭代器的性质类型

随机访问迭代器（Random Access Iterator）

• 支持快速访问容器中的任意元素。
• 支持迭代器之间的比较操作（如==、!=、<、<=、>、>=）。

双向迭代器（Bidirectional Iterator）

• 支持向前和向后遍历容器中的元素。
• 支持迭代器之间的相等和不等比较。

单向迭代器（Forward Iterator）

• 仅支持向前遍历容器中的元素。
• 支持迭代器之间的相等和不等比较。

迭代器类型	使用容器
单向迭代器	单链表，哈希表
双向迭代器	双链表，红黑树(map,set)
随机访问迭代器	vector，string，queue

随机访问迭代器支持++，--，-，+操作， 双向迭代器能支持++，--， 单向迭代器只支持++

这些迭代器是向上兼容的，随机访问迭代器是特殊的单向迭代器

---

---

????总结

通过本篇文章，我们一同探索了C++标准模板库（STL）中list容器的奥秘。list以其基于双向链表的特性，为我们提供了在序列容器中进行高效插入和删除操作的强大工具。我们深入了解了list的基本操作、迭代器使用、内存管理以及与其他STL容器的比较，使得我们能够在编程中更加灵活地应用它。

每个工具都有其适用的场景和局限性。在选择使用list容器时，我们需要根据具体需求权衡其优点和缺点。例如，list的随机访问性能较差，不适合需要频繁访问特定元素位置的场景。此时，我们可以考虑使用vector或deque等随机访问容器。

学习STL中的list容器不仅是为了掌握其使用技巧，更是为了培养我们解决问题的思维方式和编程能力。希望本篇文章能够为您在C++编程道路上的探索提供一些帮助和启示。让我们一起继续深入学习STL和其他C++编程技术，不断提升自己的编程水平！

谢谢大家支持本篇到这里就结束了，祝大家天天开心！