第18章 STL list和forward_list

标准模板库（STL）以模板类std::list的方式向程序员提供了一个双向链表。双向链表的主要优点是，插入和删除元素的速度快，且时间是固定的。从C++11起，您还可使用单向链表std::forward_list，这种链表只能沿一个方向遍历。

在本章中，您将学习：

• 如何实例化list和forward_list；

• 使用STL链表类，包括插入和删除元素；

• 如何对元素进行反转和排序。

18.1 std::list的特点

链表是一系列节点，其中每个节点除包含对象或值外还指向下一个节点，即每个节点都链接到下一个节点和前一个节点，如图18.1所示。

图18.1 双向链表的可视化表示

list类的STL实现允许在开头、末尾和中间插入元素，且所需的时间固定。

要使用std::list类，需要包含头文件<list>：

18.2 基本的list操作

要使用遵循标准的STL list类，必须包含头文件<list>。std命名空间中的模板类 list是一种泛型实现，要使用其成员函数，必须实例化该模板。

18.2.1 实例化std::list对象

要实例化模板list，需要指定要在其中存储的对象类型，因此实例化list的语法类似于下面这样：

要声明一个指向list中元素的迭代器，可以像下面这样做：

如果需要一个这样的迭代器，即可以使用它来修改值或调用非const函数，可将const_iterator替换为iterator。

鉴于 std::list 的实现提供了一组重载的构造函数，您可以创建包含指定元素数的 list，并初始化每个元素，如程序清单18.1所示。

程序清单18.1 各种实例化std::list的方式：指定元素数和初始值

分析：

这个程序没有输出，它演示了如何使用各种重载的构造函数来创建整型list。第8行创建了一个空list；第11行创建了一个包含10个整型元素的list；第14行创建了一个名为listWith4IntegersEach99的list，它包含10个整型元素，且每个元素都被初始化为99；第17行演示了如何创建一个这样的list，即其内容与另一个list完全相同。第20～24行令人惊讶！您首先实例化了一个vector，它包含10个整型元素，每个元素都被初始化为2011；接下来，第23行实例化了一个list，它包含从vector复制而来的元素，这是使用C++11新增的vector::cbegin()和vector::cend()返回的const迭代器复制的。该程序清单表明，迭代器让容器的实现彼此独立，其通用功能让您能够使用 vector中的值实例化 list，如第 23和24行所示。

cbegin()和cend()是否导致编译错误？

如果您使用的编译器没有遵循C++11标准，请使用begin()和end()分别代替该程序中的cbegin()和cend()。cbegin()和cend()是C++11新增的，它们返回一个const迭代器，不能用于修改元素。

如果将程序清单 18.1与程序清单 17.1进行比较，将发现实例化不同容器的方式类似。随着您越来越多地使用 STL容器进行编程，这种模式将越来越明显，越来越容易理解。

18.2.2 在list开头或末尾插入元素

与deque类似，要在list开头插入元素，可使用其成员方法push_front。要在末尾插入，可使用成员方法push_back。这两个方法都接受一个参数，即要插入的值：

程序清单18.2演示了这两个方法对整型list的影响。

程序清单18.2 使用push_front和push_back在list中插入元素

输出：

分析：

第19～22行演示了如何使用push_front和push_back。以实参方式提供给push_front的值被插入到list开头，而传递给push_back的值被插入到list末尾。使用模板函数DisplayContents()显示了list的内容，以显示插入的元素的排列顺序（它们并非以插入顺序存储）。

关键字auto是否导致编译错误？

在程序清单18.2中，函数DisplayContents()使用了C++11关键字auto来声明迭代器的类型，如第7行所示。另外，它还使用了cbegin()和cend()，这些函数是C++11新增的，返回一个const_iterator。对于这个示例以及以后的示例，如果要使用不遵循C++11的编译器编译，需要将auto替换为显式类型。

因此，如果您使用的是较老的编译器，需要将DisplayContents()修改成下面这样：

程序清单18.2中的DisplayContents()（第4～13行）比程序清单17.6中的DisplayVector()更通用（注意到参数列表不同）。DisplayVector()可用于任何 vector，而不管其存储的元素类型如何，而DisplayContents()可用于任何容器。

调用程序18.2中的DisplayContents()时，如果实参设置为vector或list，该函数也将正确运行。

18.2.3 在list中间插入元素

std::list的特点之一是，在其中间插入元素所需的时间是固定的，这项工作是由成员函数insert完成的。

成员函数list::insert有3种版本。

• 第1种版本：

在这里，insert函数接受的第1个参数是插入位置，第2个参数是要插入的值。该函数返回一个迭代器，它指向刚插入到list中的元素。

• 第2种版本：

该函数的第1个参数是插入位置，最后一个参数是要插入的值，而第2个参数是要插入的元素个数。

• 第3种版本：

该重载版本是一个模板函数，除一个位置参数外，它还接受两个输入迭代器，指定要将集合中相应范围内的元素插入到list中。注意，输入类型InputIterator是一种模板参数化类型，因此可指定任何集合（数组、vector或另一个list）的边界。

程序清单18.3演示了如何使用函数list::insert的这些重载版本。

程序清单18.3 在list中插入元素的各种方法

输出：

分析：

在程序清单18.3中，begin()和end()是list的成员函数，分别返回指向list开头和末尾的迭代器；几乎对所有 STL 容器来说都如此。函数 list::insert 接受一个迭代器参数，元素将插入到该参数指定的位置前面。end()函数返回的迭代器（如第24行所示）指向list中最后一个元素的后面，因此这行代码将3插入到末尾。第32行在一个list开头插入了4个元素，这些元素的值都为0。第41行和第42行演示了如何将一个list的内容插入到另一个list开头。虽然这里演示的是将一个整型list插入到另一个list中，但也可将插入范围指定为vector的边界（像程序清单18.1那样使用begin()和end()）或普通静态数组的边界。

18.2.4 删除list中的元素

list的成员函数erase有两种重载版本：一个接受一个迭代器参数并删除迭代器指向的元素，另一个接受两个迭代器参数并删除指定范围内的所有元素。程序清单18.4演示了如何使用list::eras函数删除一个元素或指定范围内的所有元素。

程序清单18.4 删除list中的元素

输出：

分析：

在main()中，第20～25行使用了各种方式在list中插入元素。用于插入一个元素时，insert()返回一个迭代器，该迭代器指向新插入的元素。在第 25 行，将指向值为 2 的元素的迭代器存储到了变量iValue2中，以便第35行使用它来调用erease()，从而将该元素从list中删除。第30和38行演示了如何使用erease()来删除指定范围内的元素。在第30行，删除了从begin()到值为2的元素之间的所有元素（不包括值为2的元素）；而在第38行，删除了从begin()到end()之间的所有元素，这相当于清空整个list。

程序清单18.4的第40行表明，可使用方法size()确定std::list的大小，就像vector一样。这种模式适用于所有STL容器类。

18.3 对list中的元素进行反转和排序

list 的一个独特之处是，指向元素的迭代器在 list 的元素重新排列或插入元素后仍有效。为实现这种特点，list提供了成员方法sort和reverse，虽然STL也提供了这两种算法，且这些算法也可用于list类。这些算法的成员函数版本确保元素的相对位置发生变化后指向元素的迭代器仍有效。

18.3.1 使用list::reverse()反转元素的排列顺序

list提供了成员函数reverse()，该函数没有参数，它反转list中元素的排列顺序：

程序清单18.5演示了如何使用reverse()。

程序清单18.5 反转list中元素的排列顺序

输出：

分析：

如第 30 行所示，reverse()只是反转 list 中元素的排列顺序。它是一个没有参数的简单函数，确保指向元素的迭代器在反转后仍有效——如果程序员保存了该迭代器。

18.3.2 对元素进行排序

list的成员函数sort()有两个版本，其中一个没有参数：

另一个接受一个二元谓词函数作为参数，让您能够指定排序标准：

程序清单18.6演示了这两个版本。

程序清单18.6 使用list::sort()将整型list按升序和降序排列

输出：

分析：

该示例演示了如何对整型list进行排序。开头几行代码创建了一个list对象，并在其中插入一些值。第35行演示了不带参数的sort()函数的用法，它使用运算符<比较整数（就整型而言，该运算符是由编译器实现的），并将元素按默认的升序排列。然而，如果程序员要覆盖这种默认行为，必须向sort函数提供一个二元谓词。第4～8行定义了函数SortPredicate_Descending，它是一个二元谓词，帮助list的sort 函数判断一个元素是否比另一个元素小。如果不是，则交换这两个元素的位置。换句话说，您告诉了list如何解释小于，就这里而言，小于的含义是第一个参数大于第二个参数。将这个谓词作为参数传递给了sort()函数，如第40行所示。这个谓词仅在第一个值比第二个值大时返回true。也就是说，使用该谓词时，仅当第一个元素（lsh）的数字值比第二个元素（rsh）大时，sort才认为第一个元素比第二个元素小。基于这种解释，sort交换元素的位置，以满足谓词指定的标准。

18.3.3 对包含对象的list进行排序以及删除其中的元素

如果list的元素类型为类，而不是int等简单内置类型，如何对其进行排序呢？假设有一个包含地址簿条目的list，其中每个元素都是一个对象，包含姓名、地址等内容，如何确保按姓名对其进行排序呢？

答案是采取下面两种方式之一：

• 在list包含的对象所属的类中，实现运算符<。

• 提供一个排序二元谓词——一个这样的函数，即接受两个输入值，并返回一个布尔值，指出第一个值是否比第二个值小。

在实际的应用程序中，很少使用STL容器来存储整数，而是存储用户定义的类型，如类或结构。程序清单18.7是一个使用联系人list的示例。乍一看，这个示例很长，但大部分代码都很简单。

程序清单18.7 存储对象的list：创建一个联系人列表

输出：

分析：

首先，将重点放在第57～81行的main()函数上。第57行实例化了一个list，它包含类型为ContactItem的地址簿条目。第58～63行使用了一些著名技术专家和政治家的姓名和电话号码（虚构的）填充了该list，而第66行显示了该list的内容。第68行调用了list::sort，但没有提供谓词函数。在没有提供谓词的情况下，函数 sort检查 ContactItem 是否定义了运算符<，发现第 37～40行定义了该运算符。ContactItem::operator<让list::sort按姓名的字母顺序排列元素（而不是根据电话号码或随机逻辑进行排序）。要根据电话号码进行排序，可在调用list::sort()时提供二元谓词函数SortOnPhoneNumber()，如第72行所示。这个函数是在第49～53行实现的，它根据电话号码（而不是姓名）对两个类型为ContactItem的输入参数进行比较，从而让 list::sort 根据电话号码对这个名人列表进行排序，如输出所示。最后，第77行使用list::remove()将一个名人的联系信息从list中删除。您将参数设置成了包含该名人姓名的ContactItem对象，list::remove()使用第30～34行实现的ContactItem::operator==将该对象与list中的元素进行比较。该运算符在姓名相同时返回true，向list::remove()指出了匹配标准。

这个例子表明STL list是一个模板类，可用于创建任何对象类型的列表，它还说明了运算符与谓词的重要性。

C++11

std::forward_list

从C++11起，您可以使用forward_list，而不是双向链表std::list。std::forward_list是一种单向链表，即只允许沿一个方向遍历，如图18.2所示。

图18.2 单向链表的可视化表示

要使用std::forward_list，需要包含头文件<forward_list>：

forward_list 的用法与 list 很像，但只能沿一个方向移动迭代器，且插入元素时只能使用函数push_front()，而不能使用push_back()。当然，总是可以使用insert()及其重载版本在指定位置插入元素。

程序清单18.8演示了forward_list类的一些函数。

程序清单18.8 forward_list的基本插入和删除操作

输出：

分析：

该示例表明，forward_list与list很像。鉴于forward_list不支持双向迭代，因此只能对迭代器使用运算符++，而不能使用—。在这个示例中，第 28 行使用函数 remove(2)删除了值为 2 的所有元素；第29行调用了sort()，这将使用默认的排序谓词，即std::less<T>。

forward_list的优点在于，它是一种单向链表，占用的内存比list稍少，因为只需指向下一个元素，而无需指向前一个元素。

18.4 总结

本章介绍list的特征以及各种list操作。现在读者知道了list的最常用函数，能够创建用于存储任何类型的对象的list。

18.5 问与答

问：list为何提供诸如sort和remove等成员函数？

答：STL list类需要确保指向 list中元素的迭代器始终有效，而不管如何在 list中移动该元素。虽然STL算法也可用于list，但list的成员函数可确保list的上述特征，即将list排序后，指向list中元素的迭代器仍指向原来的元素。

问：使用存储 CAnimal 对象的 list 时，为让 list 的成员函数能够正确处理 CAnimal 对象，应为CAnimal类实现哪些运算符？

答：对于其对象将存储在STL容器中的类，必须为它实现默认比较运算符==和运算符<。

问：对于下述代码行，该如何将关键字auto替换为显式类型？

答：如果您使用的是不遵循 C++11的老式编译器，应将关键字 auto替换为显式类型，如下所示：

18.6 作业

作业包括测验和练习，前者帮助读者加深对所学知识的理解，后者提供了使用新学知识的机会。请尽量先完成测验和练习题，然后再对照附录D的答案。在继续学习下一章前，请务必弄懂这些答案。

18.6.1 测验

1．与在开头或末尾插入元素相比，在STL list中间插入元素是否会降低性能？

2．假设有两个迭代器分别指向STL list对象中的两个元素，然后在这两个元素之间插入了一个元素。请问这种插入是否会导致这两个迭代器无效？

3．如何清空std::list的内容？

4．能否在list中插入多个元素？

18.6.2 练习

1．编写一个程序，它接受用户输入的数字并将它们插入到list开头。

2．使用一个简短的程序来演示这样一点：在list中插入一个新元素，导致迭代器指向的元素的相对位置发生变化后，该迭代器仍有效。

3．编写一个程序，使用 list的 insert函数将一个 vector的内容插入到一个STL list中。

4．编写一个程序，对字符串list进行排序以及反转排列顺序。