Increment operator/ iterator implementation

blueskin picture blueskin · Dec 1, 2010 · Viewed 16.6k times · Source

I am trying to figure out a couple of things here:

  1. How do I write an increment operator for a node class that has a pointer to the next node?
  2. How do I implement iterators for a class like below?

    #include <iostream>
    #include <vector>
    using namespace std;
    
    template <typename T>
    class Node {
    public:
        Node(int i=0):val(i) {}
        Node*& operator++(int i=0) {return next;};
    
        T val;
        Node *next;
    };
    
    //================================================
    int main() {
    
        Node<int> *head, *tmp1, *tmp2;
    
        tmp1 = new Node<int>(0); 
        head = tmp1;
    
        for (int i=1; i<10; ++i) {
    
            tmp2 = new Node<int>(i);
            tmp1->next = tmp2;
            tmp1 = tmp2;
        }
    
        while (head != NULL) {
    
            cout << head->val << " '";
            head = head->operator++(0);    //How do I make it work with ++head;?
        }
    }
    

This is not a good example for demonstrating operator overloading or iterators.

Answer

Karl Knechtel picture Karl Knechtel · Dec 2, 2010

You don't implement operator++ for the Node class; you implement it for the iterator. The iterator class should be a separate class.

And please, don't spoil your template by making assumptions (since val is a T, your constructor should accept a T, not an int). Also, do not ignore the int parameter to operator++ like that: it is a dummy used to distinguish the pre-increment implementation from the post-increment implementation.

template <typename T>
struct Node {
    T val;
    Node *next;

    Node(const T& t = T()) : val(t) {}
};

template <typename T>
struct node_iter {
    Node<T>* current;
    node_iter(Node<T>* current): current(current) {}

    const node_iter& operator++() { current = current->next; return *this; }
    node_iter operator++(int) {
        node_iter result = *this; ++(*this); return result;
    }
    T& operator*() { return current->val; }
};

int main() {
    // We make an array of nodes, and link them together - no point in
    // dynamic allocation for such a simple example.
    Node<int> nodes[10];
    for (int i = 0; i < 10; ++i) {
        nodes[i] = Node<int>(i);
        nodes[i].next = (i == 9) ? nodes + i + 1 : 0;
    }

    // we supply a pointer to the first element of the array
    node_iter<int> test(nodes);
    // and then iterate:
    while (test.current) {
        cout << *test++ << " ";
    }
    // Exercise: try linking the nodes in reverse order. Therefore, we create 
    // 'test' with a pointer to the last element of the array, rather than 
    // the first. However, we will not need to change the while loop, because
    // of how the operator overload works.

    // Exercise: try writing that last while loop as a for loop. Do not use
    // any information about the number of nodes.
}

This is still a long, long way off from providing proper data encapsulation, memory management etc. Making a proper linked list class is not easy. That's why the standard library provides one. Don't reinvent the wheel.