c++ - 外部双向链表迭代器 C++

Question

我做了一个双向链表。总的来说，我需要使用一个外部列表迭代器，它有一个接受列表的构造函数。这是我目前所拥有的:

struct ListIterator : List {
    Node* cur = head;

    ListIterator(List* list) {
        this -> list = list;
    }

    bool hasNext() {
        return (cur -> next) != nullptr;
    }

    int next() {
        return list.at(cur -> next);
    }
};

这是我的主要内容:

List list1;

list1.append('I');
list1.append('D');
list1.append('F');
list1.append('G');
ListIterator it(list1);

while (it.hasNext()) {
   cout << it.next();
}

如您所见，我正在尝试使用 hasNext() 和 next() 来显示列表中的所有节点。我对如何创建一个接受列表的构造函数并在 ListIterator 结构中使用该函数感到困惑。非常感谢任何提示和提示。

Answer 1

您似乎深受 Java(甚至可能是 C#)的影响。这不是坏事，您只需要学习 C++ 的来龙去脉。

对于您的第一个问题:在 C++ 中，值、引用和指针之间有明确的区别。当您声明 List 类的实例时，如下所示:

List list1;

那实际上是一个值。该实例存在于堆栈中，一旦范围结束，将被正确处理(将调用析构函数)。

如果您现在要按如下方式初始化第二个列表:

List list2 = list1;

这也是一个值，它将复制整个列表(将调用复制构造函数或赋值运算符)。现在 list1 和 list2 是两个不同的列表实例，修改一个不会影响另一个。

无论如何，要获得指向列表的指针，您需要以下语法:

List *listPtr1 = &list1;

由于是指针，是间接寻址，复制它不会复制底层结构:

List *listPtr2 = listPtr1; // Will also point to list1

---

虽然使用正确的语法可以解决您眼前的问题，但它不能正确解决奇怪的迭代器实现问题。

在 C++ 中，迭代器要么指向容器中的单个元素，要么指向尾部。迭代器通常不知道自己是否到达了容器的末尾；相反，它需要与这个 past-the-end 迭代器进行比较。

容器通常定义一个 begin返回指向第一个元素的迭代器的方法，以及一个 end将迭代器返回到 past-the-end 的方法。

迭代容器通常使用以下原型(prototype):

for (auto it = container.begin(); it != container.end(); ++it)
{
    // To access the element, you need to dereference the iterator:
    std::cout << "The current value is :" << *it << std::endl;
}

在这方面，迭代器的行为很像指向元素的指针。不需要笨重的 next 和 hasNext 方法。您只需获取一个指向容器开头的迭代器，确保在它指向past-the-end 后停止迭代，并在您想转到下一个元素时递增它。

正确定义begin 和end 方法的容器也可以用在range-based for loop 中。 :

for (auto &element : container)
{
    std::cout << "The current value is :" << element << std::endl;
}

---

我知道实现您自己的容器很有趣并且很有教育意义。我重新发明了我相当一部分的轮子只是为了了解事情是如何运作的，所以这没有错。但我建议您或许首先尝试使用标准 C++ 容器，掌握 C++ 与 Java 和 C# 等语言之间的主要区别，然后再进行一次练习。