迭代器模式 - 百兽海贼团

苏丙榅2022-09-152023-04-06

配套视频课程已更新完毕，大家可通过以下两种方式观看视频讲解：

1. 凯多的烦恼

百兽海贼团是由原新世界的四皇之一“百兽”凯多创建并领导的海贼团。其成员多为恶魔果实动物系能力者（或人造恶魔果实能力者），被称之为最强大的海贼团体，其大本营驻扎在新世界的和之国海域的鬼之岛上。其成员按照职位高低来分类，分为：总督（1人），大看板（3人），真打，编号者，给赋者，爆笑者，等待者，小弟更是不计其数。

通过上面的介绍可以得知，百兽海贼团的结构是一个树状结构，而且人员众多。假设我们要将百兽海贼团中的成员逐一遍历一遍，应该如何处理呢？

如果按照海贼团的等级划分来存储这些团员信息，遍历他们有两种方式：深度优先搜索和广度优先搜索；如果存储海贼团成员信息的时候使用的是线性表或者其他结构，现有的遍历算法可能就不再适用了，最优的解决方案就是将集合与它对应的遍历算法解耦。

所以我们需要提供一种解决方案使其能够顺序访问一个集合对象中的各个元素，而又不暴露该集合底层的表现形式（列表、栈、树、图等），这种行为设计模式就叫迭代器模式。

关于迭代器模式，现实生活中对应的场景也有很多，比如：

上课点名
上体育课报数
坐火车查票
躲在被窝里数钱
STL容器的迭代器

2. 同志们辛苦了

凯多虽然打架很厉害，但是如果问他手下有多少人，估计他也不知道，虽然尾田说凯多的百兽海贼团共计约3万人，但凯多自己肯定也没有数过，下面我们写个程序替凯多检阅一下它的队伍。

2.1 集结部队

迭代器模式主要是用来进行数据的遍历，对于凯多的百兽海贼团来说，需要有一个容器将海贼团的成员存储起来，这里我们选择使用链表（因为STL容器都携带了各自的迭代器，不需要我们再为其提供新的迭代器）。

头文件 MyList.h

#pragma once
#include <string>
using namespace std;
// 定义一个链表节点
struct Node
{
    Node(string n) : name(n) {}
    string name = string();
    Node* next = nullptr;
    Node* prev = nullptr;
};

// 双向链表
class MyList
{
public:
    inline int getCount()
    {
        return m_count;
    }

    inline Node* head()
    {
        return m_head;
    }

    inline Node* tail()
    {
        return m_tail;
    }

    Node* insert(Node* item, string data);
    Node* pushFront(string data);
    Node* pushBack(string data);

private:
    Node* m_head = nullptr;
    Node* m_tail = nullptr;
    int m_count = 0;
};

源文件 MyList.cpp

#include "MyList.h"

Node* MyList::insert(Node* item, string data)
{
    Node* node = nullptr;
    if (item == m_head)
    {
        node = pushFront(data);
    }
    else
    {
        node = new Node(data);
        node->next = item;
        node->prev = item->prev;
        // 重新连接
        item->prev->next = node;
        item->prev = node;
        m_count++;
    }

    m_count++;
    return node;
}

Node* MyList::pushFront(string data)
{
    Node* node = new Node(data);
    // 空链表
    if (m_head == nullptr)
    {
        m_head = m_tail = node;
    }
    else
    {
        node->next = m_head;
        m_head->prev = node;
        m_head = node;
    }
    m_count++;
    return node;
}

Node* MyList::pushBack(string data)
{
    Node* node = new Node(data);
    // 空链表
    if (m_tail == nullptr)
    {
        m_head = m_tail = node;
    }
    else
    {
        m_tail->next = node;
        node->prev = m_tail;
        m_tail = node;
    }
    m_count++;
    return node;
}

上面代码实现的是一个双向链表，这样就可以把百兽海贼团所有成员集结到一起了。

2.2 准备检阅

如果想要遍历上面的链表集合，有两种方式：一种是正向遍历，一种是逆向遍历，不论哪一种遍历方式它们都对应相同的操作接口，所以需要先提供一个抽象的迭代器基类。通过代器接口访问上面的双向链表的时候，我们只知道它是一个容器，至于其内部的数据结构已经全部被隐藏了。

抽象的迭代器类（Iterator.h）

// 抽象的迭代器类
class Iterator
{
public:
    Iterator(MyList* mylist) : m_list(mylist) {}
    Node* current()
    {
        return m_current;
    }
    virtual Node* first() = 0;
    virtual Node* next() = 0;
    virtual bool isDone() = 0;
    virtual ~Iterator() {}
protected:
    MyList* m_list = nullptr;
    Node* m_current = nullptr;
};

在这个迭代器基类的内部包含一个双向链表的实例对象 m_list，通过迭代器类遍历双向链表的时候：

通过isDone()函数判断遍历是否结束了
通过current()函数得到遍历到的当前节点
在进行正向遍历的时候:
- 通过first()函数得到链表的头结点
- 通过next()函数得到当前节点的后继节点
在进行逆向遍历的时候:
- 通过first()函数得到链表的尾结点
- 通过next()函数得到当前节点的前驱节点

正向遍历和逆向遍历

// 正向迭代器
class ForwardIterator : public Iterator
{
public:
    using Iterator::Iterator;
    Node* first() override
    {
        m_current = m_list->head();
        return m_current;
    }
    Node* next() override
    {
        m_current = m_current->next;
        return m_current;
    }
    bool isDone() override
    {
        return m_current == m_list->tail()->next;
    }
};

// 逆向迭代器
class ReverseIterator : public Iterator
{
public:
    using Iterator::Iterator;
    Node* first() override
    {
        m_current = m_list->tail();
        return m_current;
    }
    Node* next() override
    {
        m_current = m_current->prev;
        return m_current;
    }
    bool isDone() override
    {
        return m_current == m_list->head()->prev;
    }
};

在子类ForwardIterator 和ReverseIterator 中分别重写父类的纯虚函数，实现了对双向链表的正向遍历和逆向遍历。通过编写的代码我们可以非常清晰的看到，其实所谓的迭代器模式就是专门针对某个容器的遍历提供对应的操作类，通过迭代器类的封装使对应的容器的遍历操作变得简单，并且隐藏了容器的内部细节。

2.3 小插曲

现在容器类（也就是上面的双向链表类）和遍历容器的迭代器类都定义出来了，而且迭代器类是为容器量身定制的，如果想遍历容器，那么就需要让这个容器能够提供出一个可用的迭代器对象，所以还需要在链表类中添加一个获取或者创建迭代器对象的函数：

头文件 MyList.h

#pragma once
#include <string>
using namespace std;
// 定义一个链表节点
struct Node
{
    Node(string n) : name(n) {}
    string name = string();
    Node* next = nullptr;
    Node* prev = nullptr;
};

class Iterator;
// 双向链表
class MyList
{
public:
    inline int getCount()
    {
        return m_count;
    }

    inline Node* head()
    {
        return m_head;
    }

    inline Node* tail()
    {
        return m_tail;
    }

    Node* insert(Node* item, string data);
    Node* pushFront(string data);
    Node* pushBack(string data);
    Iterator* getIterator(bool isReverse = false);

private:
    Node* m_head = nullptr;
    Node* m_tail = nullptr;
    int m_count = 0;
};

由于迭代器类Iterator和链表类MyList是相互包含的关系，所以尽量不要让这两个类的头文件互相包含，在上面的MyList 类中第13行只是对 Iterator 迭代器类进行了声明，保证编译器能够识别出第36行的返回值类型即可。

源文件 MyList.cpp

#include "MyList.h"
#include "Iterator.h"

Node* MyList::insert(Node* item, string data)
{
    Node* node = nullptr;
    if (item == m_head)
    {
        node = pushFront(data);
    }
    else
    {
        node = new Node(data);
        node->next = item;
        node->prev = item->prev;
        // 重新连接
        item->prev->next = node;
        item->prev = node;
        m_count++;
    }
    return node;
}

Node* MyList::pushFront(string data)
{
    Node* node = new Node(data);
    // 空链表
    if (m_head == nullptr)
    {
        m_head = m_tail = node;
    }
    else
    {
        node->next = m_head;
        m_head->prev = node;
        m_head = node;
    }
    m_count++;
    return node;
}

Node* MyList::pushBack(string data)
{
    Node* node = new Node(data);
    // 空链表
    if (m_tail == nullptr)
    {
        m_head = m_tail = node;
    }
    else
    {
        m_tail->next = node;
        node->prev = m_tail;
        m_tail = node;
    }
    m_count++;
    return node;
}

Iterator* MyList::getIterator(bool isReverse)
{
    Iterator* iterator = nullptr;
    if (isReverse)
    {
        iterator = new ReverseIterator(this);
    }
    else
    {
        iterator = new ForwardIterator(this);
    }
    return iterator;
}

在这个MyList 类的源文件中包内含了迭代器类的头文件 Iterator.h，这样在getIterator()函数中就可以根据参数的值创建出一个正向迭代器的实例对象或者一个逆向迭代器的实例对象了，有了这个迭代器对象就可以通过它完成对双向链表的遍历。

2.4 开始检阅

我们先把凯多的百兽海贼团成员初始化到链表中，然后就可以让凯多来检阅队伍了：

int main()
{
    vector<string> nameList{ 
        "烬", "奎因", "杰克", "福兹·弗", "X·德雷克",
        "黑色玛利亚", "笹木", "润媞", "佩吉万",
        "一美", "二牙", "三鬼", "四鬼", "五鬼",
        "六鬼", "七鬼", "八茶", "九忍","十鬼"
    };
    MyList mylist;
    for (int i = 0; i < nameList.size(); ++i)
    {
        mylist.pushBack(nameList.at(i));
    }
    // 遍历
    Iterator* it = mylist.getIterator(true);
    cout << "检阅开始, 凯多: 同志们辛苦啦~~~~~" << endl;
    for (auto begin = it->first(); !it->isDone(); it->next())
    {
        cout << "   " << it->current()->name << "say: 为老大服务!!! " << endl;
    }
    cout << endl;
    delete it;
    return 0;
}

在上面的代码中是进行了逆向遍历，检阅的顺序和nameList 名单中的顺序是相反的，最终输出的结果如下：

检阅开始, 凯多: 同志们辛苦啦~~~~~
   十鬼say: 为老大服务!!!
   九忍say: 为老大服务!!!
   八茶say: 为老大服务!!!
   七鬼say: 为老大服务!!!
   六鬼say: 为老大服务!!!
   五鬼say: 为老大服务!!!
   四鬼say: 为老大服务!!!
   三鬼say: 为老大服务!!!
   二牙say: 为老大服务!!!
   一美say: 为老大服务!!!
   佩吉万say: 为老大服务!!!
   润媞say: 为老大服务!!!
   笹木say: 为老大服务!!!
   黑色玛利亚say: 为老大服务!!!
   X·德雷克say: 为老大服务!!!
   福兹·弗say: 为老大服务!!!
   杰克say: 为老大服务!!!
   奎因say: 为老大服务!!!
   烬say: 为老大服务!!!