链表的迭代器

背景阅读

在阅读这些注释的其余部分之前，您应该阅读本文中的3.1、3.2和3.7节。这些部分涵盖了链表的基础知识，并向您介绍了标准模板库list类，它是STL对双重链表的实现。

改进作者的课程

作者在第3章中介绍的单链表和双链表类说明了这些类背后的基本思想。然而，作者的实现存在几个问题。

这两个类都包含用于从列表末尾添加和删除项的方法，但缺乏用于在列表中任意位置插入和删除项的通用方法。由于此功能是链表结构的主要卖点之一，因此这是一个重要的疏忽。
作者没有提供与链表类配套的迭代器类。迭代器是现代c++编程的重要组成部分，实际上应该包含在任何容器类中。
作者的类不遵循大多数STL容器类使用的命名约定。

在这些注释中，我将通过几乎完全重写单链表类来修复赢博体育这些问题。在这些笔记的最后，您会发现一个编程作业，要求您以类似的方式重写作者的双链表类。

开始——迭代器

由于我要在单链表类中引入的主要新元素是一个迭代器，因此我们需要首先考虑这样一个迭代器是如何工作的。

对于第一次猜测，我们将迭代器类放入list类中。该迭代器实现为指向节点的指针，并包含对解引用、自增、比较和赋值这四种常用迭代器操作符的操作符重载。

几乎一开始为该类编写代码，我们就会发现迭代器类已经严重损坏。主要的问题是，我们最终还需要实现一个方法

插入迭代器（iterator position,const T& value）

在列表类中，可用于在列表中的任意位置插入新数据项。给定迭代器位置，insert应该将包含该数据值的新节点放置在该位置所指向的节点之前。在插入的过程中，我们会遇到的问题是，我们需要一个指针，指向位置所指向的节点之前的节点，这样我们就可以把之前的节点挂接到我们要创建的新节点上。由于我们处理的是单链表类，因此获取该指针并不容易。

类似地，我们也想在列表类中实现一个erase（）方法：

迭代器擦除（迭代器位置）

此方法的参数是一个指向我们想要擦除的节点的交互器。在删除该节点的过程中，我们需要使目标节点之前的节点指向要删除的节点之后的节点。由于没有简单的方法来获得指向位置所指向的节点之前的节点的指针，我们再次陷入困境。

更好的方法

我们可以通过对迭代器类做一些稍微奇怪的事情来解决插入和擦除的问题。我们没有让迭代器类包含指向节点的指针，而是让迭代器指向我们想要指向的节点前面的节点。这立即解决了insert的问题。假设迭代器包含一个名为nodePtr的指针，这是插入方法的代码，既简单又正确：

迭代器插入（迭代器位置，const T& value）{节点<T>* newNode =新节点<T>(value, position. nodeptr ->next)；如果位置。nodePtr ==尾部)尾部= newNode；的位置。nodePtr->next = newNode；返回的位置;｝

正如在编程中经常发生的那样，这种解决方案产生了另一个问题。这个问题是如何处理begin（）。begin（）方法应该返回一个指向列表开头的迭代器。既然我们的迭代器类将包含一个指向我们想要指向的节点之前的节点的指针，那么我们应该在begin（）返回的迭代器中放入什么呢？

解决这个问题的方法是使用另一种技巧。我们为list类配备了一个虚拟头节点。这是一个额外的节点，我们从一开始就插入到列表中。虚拟头节点是出现在包含数据的第一个实际节点之前的节点。通过使列表类中的头指针指向虚拟头节点，并定义begin（）来完成此操作

迭代器begin() const{返回迭代器（头）；｝

我们的问题就解决了。

自增操作符

迭代器需要支持的操作之一是自增操作。c++实际上有两个自增操作符，预自增操作符

+ + itr;

和后增量运算符，写为

itr + +;

当在语句中单独使用时，这两个操作符具有完全相同的效果。当我们将这两个操作符与同一语句中的其他操作结合使用时，这两个操作符的区别就很明显了：自增前操作在语句中的任何其他操作之前赢博体育，而自增后操作在语句中的赢博体育其他操作之后赢博体育。

下面是C语言中比较著名的一段代码，它对一对指针使用了自增后操作符。这段代码是C标准库strcpy函数的实现，该函数将C字符串中的字符从指针src指向的C字符串复制到指针dest指向的C字符串：

Void strcpy(char* dest,const char* src) {while(*dest++ = *src++)；｝

这个函数中相当特殊的while循环完成了测试表达式中赢博体育有用的工作，并且具有一个空的主体。test表达式是一个复合表达式，它同时做三件事：

*dest = *src将单个字符从源数组复制到目标数组。
赋值有一个副作用，它返回复制的字符。该字符是一个数字代码，C将其解释为供循环测试使用的true/false值。空字符，' \ 0”，它标志着源字符串的结束，被解释为false，这将导致循环在正确的时间终止。赢博体育其他字符都被解释为真，这将导致循环继续。
增量运算，桌子+ +和src + +最后在test表达式中发生，它在每轮中将两个指针推进到下一对字符。注意，为了使循环逻辑正常工作，我们必须在将两个指针移动到下一个位置之前进行字符赋值。

由于有两种不同的自增操作符，c++不得不采用一种特殊的约定来区分它们。要重载自增前操作符，在迭代器类中构造一个成员函数，其形式为

迭代器操作符+ + ()

该操作符的重载应该将迭代器推进到下一个位置，然后返回对自身的引用。这通常是通过添加语句来完成的

返回*;

在方法的最后。操作符必须返回此引用，以便在复合表达式中使用增量。

要重载自增后操作符，在迭代器类中构造一个成员函数，其形式为

迭代器操作符+ + (int)

重载需要int形参，因为c++中操作符重载的规则规定，c++的两个重载必须具有相同的名称operator++，而且两个重载函数不允许仅在返回类型上有所不同。为了区分两个版本的operator++， c++使用了强制后增量版本接受单个整数形参的约定。该操作符的赢博体育实现都将忽略该形参，因为它纯粹用于区分两个版本的++。

自增后重载也很特殊，因为它必须在推进迭代器之前返回迭代器的副本。记住，在后增量中，增量发生在表达式的末尾，因此我们被迫在增量之前返回迭代器的副本，以获得正确的行为。

整个班级

下面是我们完整的单链表类的完整源代码。这个类的特点是使用一个虚拟头节点，因此即使是空列表也至少包含一个节点。list类的迭代器被定义为list类中的内部类，并存储指向该迭代器所指向的节点之前的节点的指针。

//链表模板的节点类<typename T> class node {public: T data；节点< T > *下;node(): next(nullptr) {} node(const T& item, node<T> *ptr = nullptr): data(item), next(ptr) {}}；//链表类模板<typename T> class list {public: list(){//创建虚拟头节点head = tail =新节点<T>()；} list(const list<T>& other) = delete；list(list<T>&& other) = delete；~list() {while (head->next != nullptr) {node<T>* temp = head；Head = Head ->next；删除临时表;}删除头部；} list<T>& operator=(const list<T>& other) = delete；list<T>& operator=(list<T>&& other) = delete；//内部类迭代器类迭代器{友类列表；private: node<T> *nodePtr；//构造函数是私有的，所以只有友元可以创建迭代器的实例。iterator(node<T b> *newPtr): nodePtr(newPtr) {} public: iterator(): nodePtr(nullptr){} //重载比较操作符！= bool操作符！=(const iterator& itr) const{返回nodePtr != itr.nodePtr；} //重载解引用操作符* T& operator*() const{返回nodePtr->next->数据；} //重载后增量操作符++迭代器operator++(int){迭代器temp = *this；nodePtr = nodePtr->next；返回临时;}};//内部类iterator的结束iterator begin() const{返回iterator(head)；}迭代器end() const{返回迭代器（尾）；}迭代器插入（迭代器位置，常量T和值）{节点<T>* newNode =新节点<T>（值，位置。nodeptr ->下一个）；如果位置。nodePtr ==尾部)尾部= newNode；的位置。nodePtr->next = newNode；返回的位置;}迭代器erase（迭代器位置）{node<T> *toDelete = position. nodeptr ->next；的位置。nodePtr->next = position.nodePtr->next->next；if (toDelete == tail) tail = position.nodePtr；删除删除;返回的位置;} private: node<T>* head；节点< T > *尾巴;}；

为了防止内部类与模板混合导致的问题，我在这里采用的方法是在类声明中为赢博体育成员函数编写代码，而不是将其设计为类声明后面跟着单独的方法实现。

列表类本身中最重要的两个新方法是insert（）和erase（）方法。这些方法取代了作者在列表末尾添加和删除项目的原始方法。这两种方法都遵循STL中insert（）和erase（）方法的约定。

insert（）方法的第一个参数是一个指向列表中某个位置的interator。insert（）方法将创建一个包含第二个参数中给出的数据的新节点，并将该新节点插入到列表中第一个参数所指向的节点之前的位置。插入新节点后，insert（）返回一个指向新节点的交互器。Insert（）可用于在列表中的任何位置添加新节点，甚至在列表的末尾。通过将list的end（）方法返回的迭代器作为insert（）的第一个参数传递，可以在list的末尾添加一个新项。您可能需要仔细查看insert（）方法的代码，并确信它在赢博体育情况下都能做正确的事情，包括在列表的前面和后面添加新项。

erase（）方法从迭代器在其参数中所指向的位置中删除一个节点，并返回一个指向被删除节点后节点的交互器。

要测试我们的新类，这里有一个简单的测试程序

#include <iostream> #include "list.h" int main(int argc,const char* argv[]) {list<int> v；v.insert (v.end (), 2);v.insert (v.end (), 4);v.insert (v.end (), 5);Auto iter = v.begin()；insert(Iter, 1)；//在2iter ++前插入1；//指向2 v.insert(iter++,3)；//在2之前插入3，提前到4 ++；//指向5 v.insert(iter,10)；//在5之前插入10 = v.begin()；iter + +;//指向3 v.erase(iter)；/ /擦除3(汽车itr =逆序函数();itr ! = v.end (); itr + +) std:: cout < < * itr < < std:: endl;返回0;｝

编译并运行这个测试程序确认我们的list类正在按它应该的方式工作。

编程任务

下面是作者的双链表类的代码。修改这个类做以下事情：

引入一个内部迭代器类。迭代器类将包含指向节点的单个指针，并将直接指向您希望迭代器引用的节点。
摆脱作者的方法addToDLLTail，deleteFromDLLTail，addToDLLHead和deleteFromDLLHead然后用插入和擦除方法，就像我在上面的例子中所做的那样。
也可以去掉作者的代码firstEl，找到,操作符< <，因为它们都实现了用迭代器更合适完成的事情。
提供开始()和结束()方法。开始()应该返回一个指向头节点的迭代器，并且结束()应该返回一个指针值为nullptr指示迭代器指向列表末尾以外的位置。
由于我们不会在双链表类中使用虚拟头节点，因此作者的原始构造函数和析构函数方法将继续正常工作—不要修改它们。

在如上所示修改作者的类之后，修改我在上面的课堂讲稿中展示的简单测试程序，使其与您的双链表类一起工作。运行您的测试程序并验证是否产生了正确的结果。