How to implement an end in a map?

Question

I'm implementing map for an excersise and I'm at the point where I would have to iterate over it (done and working) but the problem is that I don't know how to implement a last element (presumably an empty link). I was thinking that I would attach some special kind of link (descendant of base link) which would then be attached to the last element and in this way I would be able to detect if I'm at the real last element or not. I wonder what will be your opinion about this idea and probably hear from you about some more traditional and regularly used techniks for doing this.

Answer 1

There are two ways to implement end: a dummy node and a singular iterator (i.e. NULL).

The problem with NULL is that you need to be able to get back to the structure if you decrement --end().

What GCC does is create a truncated dummy node in the map object itself. It has links but no data payload. It is maintained as the root of the tree, with a circular parent link that invokes special behavior. Semantically it might be a little messy, but C++-compliant semantics should be worth the hassle.

Answer 2

If your iterator isn't bidirectional then you don't really need end to point to anything (just use NULL in that case). end() only needs to have a real value in the case of a bidirectional iterator, because in that case you'll need to be able to move backwards from end() towards the beginning of the list.

The GNU C++ Library (what you get if you use std::map with GCC/G++) implements end() as a pointer to the root node of the tree. This way, if used in a bidirectional iterator you can access the root node to find the right most node in the tree (which is the node directly before end()).

Edit to explain an empty tree

The map itself always contains a node for the root of the tree (it's not a pointer, its a normal member node). When the tree is empty, both leaves of this node point to the node itself (as does end()). So in an empty tree begin() would return the same thing as end().

So we have something like this:

template<class T> struct node_t {
    T data;
    node_t *left;
    node_t *right;
};


template<class T> class map {
    private:
        node_t root;
    public:
        // ...
        iterator begin() { return iterator(root.left); }
        iterator end() { return iterator(&root); }
}

Answer 3

Use dummy node for that.