Increment operator/ iterator implementation

Question

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

How do I write an increment operator for a node class that has a pointer to the next node?

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.

You cant. head is a pointer and ++ operator is builtin/defined for pointers. If head was an object or reference to an object then you could do it. — Martin York, Dec 01 '10 at 22:15
hmm..okay. Do you know of any links to implementating iterators? Thanks you — Chenna V, Dec 01 '10 at 22:18
You could look at the answers to this question: http://stackoverflow.com/questions/3582608/how-to-correctly-implement-custom-iterators-and-const-iterators — Fred Larson, Dec 01 '10 at 22:24
@Fred; as you suggested deriving STL iterators I was looking at the example at http://www.cplusplus.com/reference/std/iterator/iterator/. So if I want to read and write, should I just use random_access_iterator_tag ? or do you recommend any others? — Chenna V, Dec 01 '10 at 23:00
I would recommend starting from [boost::iterator_facade](http://www.boost.org/doc/libs/1_45_0/libs/iterator/doc/iterator_facade.html), which helps provide some of the infrastructure that proper iterators need. It even has a tutorial that goes along with it. — ephemient, Dec 01 '10 at 23:03
@blueskin: In order to be a random access iterator, your iterator would have to implement `operator+(int)` and `operator-(int)` as well as `operator++()` and `operator--()`. I think what you would have here for a singly-linked list is a forward iterator. — Fred Larson, Dec 01 '10 at 23:05
@ephemient: hmm... thats a good place to start understanding a better iterator design but for my application I am looking at just using C++ and STL. Thanks ephemient — Chenna V, Dec 01 '10 at 23:06
@Fred: exactly thats what I was looking at.. I was also looking at qlist.h to understand how they separated interface from implementation. Thanks Fred. — Chenna V, Dec 01 '10 at 23:07

score 13 · Accepted Answer · answered Dec 02 '10 at 00:42

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.

I realized that after posting this. I was actually trying to understand to how to implement iterators, its a bad example that I gave. I think QList is well implemented than STL list. I will try to implement something like that. Thanks Karl — Chenna V, Dec 02 '10 at 02:01
http://en.literateprograms.org/Singly_linked_list_%28C_Plus_Plus%29 is more helpful — Chenna V, Dec 02 '10 at 16:13
Why does operator++() return a const reference and operator++(int) return a value? — Alexander Duchene, Mar 14 '13 at 19:25
@AlexanderDuchene I don't know for sure, but I think it's because in post-increment, you have to return the value that existed prior to incrementing, whereas pre-increment returns a const reference to the iterator because it's used solely for advancing the iterator. Notice that post-increment also uses pre-increment to advance the iterator. — Dennis, Jul 29 '13 at 06:18

Increment operator/ iterator implementation

1 Answers1