代码之家 › 专栏 › 技术社区 › Rick Jim DeLaHunt

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

c++

Rick Jim DeLaHunt · 技术社区 · 7 年前

我在做一件事 Stack 这是基于 linked-list . 除了我不知道如何实现 range-based for loop

我拿到钱了 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;
}

1 回复 | 直到 7 年前

n. m. could be an AI 7 年前

首先,一个 Stack 根本不应该被遍历。它应该暴露 top pop push ,和 is_empty ,基本上就是这样。但是让我们忘掉它,假装你想要实现一个常规的链表。

在C++中,我们使用迭代器的概念来管理容器和算法,以及基于范围的循环。形式上,为了符合基于范围的for循环的条件,需要实现一个对象 begin() 和 end() begin(x) 和 end(x) 这些方法的结果需要实现 operator++ , operator* 和 != 比较。你的 Node 类几乎是合格的,只是它实现了错误的 操作员++ (它的逻辑被打破了,因为它从不更新 elem ,但从形式上来说,就编译而言,这是可以的)。

标准库中的典型列表类模板实现的工作方式类似,只是它不公开其版本 节点 直接。相反,它公开了一个指向节点的指针, 包裹在一个特殊的物体里 实现 操作员* 操作员++ 还有很多其他的事情。这允许更大的灵活性。

迭代器 在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();
};

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