mercredi 29 avril 2020

How to implement iterator design pattern on C++?

I'm curious about how to implement the iterator pattern the way STL does in a stack ADT.

#include <iostream>
#include <vector>

int main() {
    std::vector<char> v = { 'a', 'b', 'c', 'd', 'e', 'f'};

    std::vector<char>::iterator it = v.begin();

    while(it != v.end()) {
        std::cout << *it << "->";
        ++it;
    }

    std::cout << "\n";

    return 0;
}

Output

a->b->c->d->e->f->

so far I have implemented the following code

#include <iostream>
#include <memory>

template<class T>class Node {
private:
    T data = 0;
    std::shared_ptr<Node<T>> next_node = nullptr;

public:
    Node(T data = 0, std::shared_ptr<Node<T>> next_node = nullptr)
        : data(data), next_node(next_node)
    {
        std::cout << "created node[" << data << "]\n";
    }

    ~Node() {
        std::cout << "deleted node[" << data << "]\n";
    }

    // getters and setters

    T getData() const {
        return this->data;
    }

    std::shared_ptr<Node<T>> getNextNode() const {
        return this->next_node;
    }

    void setData(T value) {
        this->data = value;
    }

    void setNextNode(std::shared_ptr<Node<T>> node) {
        this->next_node = node;
    }
};

template<class T>std::ostream& operator<<(std::ostream& o, const std::shared_ptr<Node<T>> node) {
    return o << "node["<< node->getData() <<"]-> ";
}

template<class T>class Stack {
private:
    std::shared_ptr<Node<T>> top = nullptr;

public:
    Stack()
        : top(nullptr)
    { /* empty */ }

    ~Stack() { /* empty */ }

    void push(T value) {
        if(!top) {
            top = std::shared_ptr<Node<T>> (new Node<T>(value));
        } else {
            top = std::shared_ptr<Node<T>> (new Node<T>(value, top));
        }
    }

    void display() {
        if(!top) {
            std::cout << "display::The stack is empty.\n";
        } else {
            std::shared_ptr<Node<T>> p = top;

            while(p) {
                std::cout << p;
                p = p->getNextNode();
            }

            std::cout << "\n";
        }
    }

    class Iterator {
    private:
        std::shared_ptr<Node<T>> node;

    public:
        Iterator(std::shared_ptr<Node<T>> node)
            : node(node)
        { /* empty */ }

        bool hasMore() {
            return node->getNextNode() != nullptr;
        }

        Iterator getNext() {
            return Iterator(node->getNextNode());
        }

        int getData() {
            return node->getData();
        }
    };

    Iterator begin() const {
        return Iterator(top);
    }

    Iterator getIterator() {
        Iterator it = Iterator(top);

        return it;
    }
};

int main() {
    Stack<char> stack;

    for(char i = 'a'; i < 'f'; ++i) {
        stack.push(i);
    }

    Stack<char>::Iterator it = stack.begin();

    while(it.hasMore()) {
        std::cout << it.getData() << "->";
        it = it.getNext();
    }

    std::cout << "\n";

    return 0;
}

Output:

created node[a]
created node[b]
created node[c]
created node[d]
created node[e]
101->100->99->98->
deleted node[e]
deleted node[d]
deleted node[c]
deleted node[b]
deleted node[a]

My question is how to implement nested template detection for the Iterator class, as you can see the expected output is a char type and I am getting integers.

Can someone help me understand how this is implemented in the STL and how it could be implemented in an ADT?

thanks!!!

Aucun commentaire:

Enregistrer un commentaire