基于链表实现Stack的基于范围的for循环

Question

我正在制作一个基于链表的 Stack。除了不知道如何为其实现“基于范围的for循环”，一切都运行良好。

错误信息：error: no match for ‘operator++’ (operand type is ‘Stack<int>::Node’)。

出了什么问题，我该如何解决？

代码（愚笨的我重载了后置 ++，现已全部更正）：

#include <iostream>
using namespace std;

template<typename T>
class Stack{
private:
    class Node{
        friend Stack;
    public:
        void operator++(){
            this->next = this->next->next;   //point to next Node
        }

        bool operator!=(const Node& rhs){
            return !(*this == rhs);
        }

        T operator*(){
            return this->next->elem;  //return current Node elem
        }

        bool operator==(const Node& rhs){
            return this->next == rhs.next;
        }

    private:
        T elem;
        Node* next;

    };

    Node* first;
    int _size;

public:
    Stack():_size(0){
        first = nullptr;
    }

    void push(T item){
        Node* n = new Node;
        n->elem = item;
        n->next = first;
        first = n;
        _size++;
    }

    T pop(){
        T item = first->elem;
        Node* old_first = first;
        first = first->next;
        delete old_first;
        _size--;
        return item;
    }

    int size(){
        return _size;
    }

    bool empty(){
        return _size == 0;
    }

    Node begin(){
        Node n;
        n.next = first;
        return n;
    }

    Node end(){
        Node m;
        m.next = nullptr;
        return m;
    }

    ~Stack(){
        Node* ele_to_delete;
        while(first != nullptr){
            ele_to_delete = first;
            first = first->next;
            delete ele_to_delete;
        }
    }
    Stack(const Stack&) = delete;
    Stack& operator=(const Stack&) = delete;
};


int main(){
    Stack<int> ls;
    ls.push(1);
    ls.push(2);
    ls.push(3);
    for(auto s: ls){
        cout << s << "|";
    }
    return 0;
}

- Rick

---

注意：由于双下划线，__begin 是一个保留标识符。用户代码不应使用这样的标识符，因为这会导致未定义的行为。 - n. m.

通常情况下，您应该使用标准库提供的list和stack类模板。如果您想要作为练习实现自己的类，请熟悉C++中使用的iterator概念，并在您的实现中使用它。 - n. m.

无论如何，栈应该仅实现push、pop、top和is_empty（或count）操作。它不应该暴露begin、end、nodes或任何与range-for-loop相关的内容。然而，列表应该具有所有这些功能。 - n. m.

我建议在尝试实现自己的容器之前，先获得一些标准容器和迭代器的经验。 - n. m.

请不要上传代码图片。它们只是浪费我的带宽。谢谢。 - n. m.

Answer 1

首先，一个 Stack 栈本身应该是不可遍历的。它应该公开 top、pop、push 和 is_empty 方法，在此基础上进行操作。但让我们暂且抛开这个问题，假设你想要实现一个普通的链表。

在 C++ 中，我们使用迭代器来管理容器和算法，还有基于范围的 for 循环。正式地说，为了使对象能够适用于基于范围的 for 循环，它需要实现 begin() 和 end() 成员（或者使未经限定的 begin(x) 和 end(x) 调用起作用），并且这些方法的结果需要实现 operator++、operator* 和 != 比较。你的 Node 类几乎符合要求，只是它实现了错误类型的 operator++（而且它的逻辑是错误的，因为它从不更新 elem，但就编译而言，这在形式上是可以通过的）。

标准库中典型的链表类模板实现方式与之类似，只是它并不直接公开其版本的 Node。相反，它公开了一个指向节点的指针，包装在一个特殊对象中，该对象实现了 operator* 和 operator++ 以及许多其他方法。这样可以获得更大的灵活性。

在 C++ 中，行为与指针非常相似（或完全相同）的小对象称为迭代器。迭代器在标准库和许多用户代码中都是无处不在的。这是每个C++程序员必须早期学习的重要概念。任何一本好的 C++ 书籍或课程都应该涵盖它们。

下面是一个基于迭代器的链表类片段的示例：

template <class T> class List {
     struct Node {
         T elem; 
         ...
     };
     ...
   public:
     class Iterator {
        Node* node;
       public:
        Iterator operator++() { 
          node = node->next; return *this;
        }
        T& operator*() { 
          return node->elem;
        }
        ...
     };

     Iterator begin();
     Iterator end();
};

建议使用暴露迭代器接口的标准容器和算法来学习这个概念。

- n. m.

---

是的，我在纠正错误的 ++ 运算符和一些边缘情况后使其工作了。谢谢。我会去检查 Iterator。 - Rick

小问题：你不需要专门化 std:begin，begin 只需要通过 ADL 找到即可。 - Passer By

为什么有两个返回类型不同的operator*()运算符？ - super

@超级打字错误，应该是++，已修复。 - n. m.