链表迭代器在C++中的使用及设置方法

在C++中，链表迭代器是一种用来遍历链表（如std::list）元素的工具。链表是一种数据结构，其中每个元素（节点）包含一个数据值和一个指向下一个节点的指针。链表迭代器允许以类似于数组的方式访问链表中的元素，但不需要直接操作指针。

链表迭代器的作用

• 访问元素：链表迭代器使你能够顺序访问链表中的每个元素，就像在数组中遍历元素一样。

• 遍历链表：通过迭代器，你可以在链表中前进或后退，从而进行遍历操作。这使得在链表中执行各种操作（如查找、修改、删除等）变得简单而直观。

• 抽象化操作：迭代器提供了一种统一的方式来访问不同类型的数据结构。无论是链表、数组还是其他容器，迭代器的使用方式大致相同，这让代码更加通用和易于维护。

使用示例

#include <iostream>
#include <list>

int main() {
    std::list<int> myList = {1, 2, 3, 4, 5};
    
    // 使用迭代器遍历链表
    for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";  // 输出链表元素
    }
    
    return 0;
}

为什么要为自己的类设置迭代器？

class List {
public:
    List(): head(new Node()) { }
    ~List();

    bool push(int x, int y);    // 在头部插入一个新坐标
    bool POP(int x, int y);     // 查找指定坐标，并删除

private:
    Node* head;
};

在该链表中，定义了 push 和 pop 两个方法，现假定，我们需要能够从第一个节点开始，逐步在外部调用链表的每一个节点，有一种简单的实现方法：

• 定义 search(int i) 函数，从头开始，向后查询 i 个节点

• 在外部采用for循环递增节点索引 i 。

这里给出一个伪代码：

for (int i = 0; i < 10; ++i) {
    Node cur = myList.search(i);
    std::cout << cur << std::endl;
}

上述方法能够实现在外部对链表节点的遍历，但是，当索引较大时，鉴于每一次都需要从头访问至索引处，算力开销极大，因此我们必须采用更高效的方法。

如何为类设置迭代器方法？

观察标准库中迭代器的使用方法：

for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";  // 输出链表元素
}

我们了解到需要实现如下内容：

• 定义迭代器类，包含一个 Node* 类型的指针 cur ，指向当前元素。

• 在链表类中，定义 begin 、 end 函数，分别指向第一个元素和尾节点。

• 定义 != 运算符，以支持比较两个指针是否相同。

• 定义 ++ 运算符，使得可以更便携的遍历节点。

• 定义 * 运算符，使得可以采用指针方法访问到节点的值。

我们可以依次完成实现

class List {
public:
    List() : head(new Node()) { }
    ~List();

    bool push(int x, int y);
    bool pop(int x, int y);

    // 定义迭代器类
    class Iterator {
    public:
        // 构造函数
        Iterator(Node* node) : cur(node) {}
        // 指针运算符
        Cell& operator*() { return cur->cell; }
        // 前置自增运算符
        Iterator& operator++() {
            if (cur) cur = cur->next;
            return *this;
        }
        // 不等于运算符
        bool operator!=(const Iterator& other) const { return cur != other.cur; }

    private:
        // cur字段
        Node* cur;
    }

    // 分别定义begin()、end()方法
    Iterator begin() const { return Iterator(head->next); }
    Iterator end() const { return Iterator(nullptr); }

private:
    Node* head;
};

完成上述实现后，我们就可以使用迭代器方法快捷的访问类成员了。

#include <iostream>
#include "list.h"

int main() {
    List ROI;
    // 插入节点
    ROI.push(0, 0);
    ROI.push(0, 1);  
    ROI.push(0, 2);
    ROI.push(0, 3);

    for (List::Iterator it = ROI.begin(); it != ROI.end(); ++it) {
        std::cout << *it << "\n";
    }

    return 0;
}

为什么将迭代器类 Iterator 嵌入链表类 List 中？

• 封装性 ：将 Iterator 类作为 LinkedList 的嵌套类，可以更好地封装链表内部的实现细节。这样 Iterator 类只能访问 LinkedList 类的私有成员，而其他类不能直接访问 Iterator 类的内部细节。

• 逻辑关联 ： Iterator 是专门用于遍历 LinkedList 的，因此将它放在 LinkedList 类内部有助于保持逻辑上的一致性和相关性。这样可以清晰地表示 Iterator 是为 LinkedList 量身定做的。

• 简化访问 ：嵌套类可以访问外部类的私有成员。对于 Iterator 来说，它需要访问 LinkedList 的内部节点，因此将它作为嵌套类可以简化访问逻辑，而不需要额外的接口或方法来暴露链表的内部结构。