I am writing a tree structure - actually a skeleton structure since I''m eventually planning to use it for animation. Each node (or bone) looks something like this

template<class T> class Bone {

    Bone* parent;
    vector<Bone *> children;

    T *object;
    ...

    inline vector<Bone *>::iterator first_child(void) {
        return children.begin();
    }

    inline vector<Bone *>::iterator last_child(void) {
        return children.end();
    }

    ...
};
 

with pointers to the parent Bone, the actual object, and a vector containing any children of the bone. A skeleton is just made up of a bunch of bones in the usual way. The skeleton_iterator class is defined as follows (thanks to this article")

template<class T> class skeleton_iterator {

    stack<vector<Bone<T> *>::iterator> bStack;

    typedef std::forward_iterator_tag iterator_category;
    typedef T value_type;
    typedef std::ptrdiff_t difference_type;
    typedef T*& reference;
    typedef T** pointer;
    typedef Bone<T>* boneptr;

    reference operator*() const { return p->object; }
    pointer operator->() const { return &(p->object); }

    boneptr p;

    skeleton_iterator(boneptr x) : p(x) {
       bStack.push(&p);
    }
    
    ...

};
 

And after that I struggled with a ++ operator for the weekend Basically the idea was to start off at the root node which is returned by a skeleton::begin(). After that current thingy the iterator is pointing to is the object in the boneptr p. To increment it checks to see if p has any children. If it does it moves down to the first child and sticks a vector<Bone *>::iterator to p''s children into the bStack. If p has no children it increments the last vector<Bone *>iterator in the bStack. If this is then the last of the children it moves up the stack, otherwise it moves on to the next child. Something like this:

skeleton_iterator& operator++() {
    if(p->first_child()) {
        bStack.push(p->first_child());
        p = *bStack.top();
    }

    else {
        while (++bStack.top() == p->parent->last_child()) {
            bStack.pop();
            p = *bStack.top();
        }
        p = *bStack.top();
    }

    return *this;
}
 

To terminate I have this global dummy Bone whose object member points to nothing. This is stuck in as the last child of the root Bone and is also returned by skeleton::end() so

skeleton<blah>::iterator i = S.begin();
while (i != S.end()) {
    ...
    ++i;
}
 

behaves as expected. (it was all I could think of) If anyone is interested the entire code is here It seems to work OK but if anyone has any comments I''d appreciate them.

http://www.damtp.cam.ac.uk/user/kp229/tree/#overview