时间戳

首页 > 解决方案 > 基于链表的Stack的基于范围的for循环

c++ - 基于链表的Stack的基于范围的for循环

问题描述

我正在制作一个Stack基于linked-list. 一切正常，除了我不知道如何为此实现“基于范围的 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;
}

标签： c++

解决方案

首先， aStack根本不应该是可遍历的。它应该暴露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();
};

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

推荐阅读