Re: [boost] Hash tables and singly linked lists

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-13 19:57:30

On Sat, 13 Jan 2001, Matt Austern wrote:

> "John E. Potter" wrote:
> 
> > Another alternative.  Since the iterator contains a prior pointer,
> > iterators may be invalidated in ways other than erase of the
> > current node.  That makes containers of iterators unlikely and the
> > total number of iterators likely becomes small.  The space can be
> > shifted to the iterator with a prior and current pointer.  The
> > list contains a single pointer.  Insert, erase, begin, end are O(1).
> > Dereference is one step.  Increment is two updates, but one is
> > local to the iterator.  The increased size of the iterator may
> > make everything slower or may not be measurable.
> 
> I don't see how that lets you get away without having an end
> pointer in the list itself.  If an iterator has a prior pointer,
> then doesn't the end iterator still have to have a pointer to
> the last list node?

Circular list with no dummy node.  Tail points to last node.  For
an empty list end == begin == (0, 0).  For a non empty list, end
== (tail, tail->next) and begin == (0, tail->next).  Iterators
naturally increment to end.  There are only n values for current,
but there are n + 1 values for pred.  Iterator== is on pred only.

Proof of concept follows.

John

template <class T>
struct Node {
    Node* next;
    T data;
    Node (Node* n, T const& d) : next(n), data(d) { }
    };
template <class T>
struct Iter {
    Node<T>* pre;
    Node<T>* cur;
    Iter (Node<T>* p, Node<T>* c) : pre(p), cur(c) { }
    Iter () { }
    T& operator* () const { return cur->data; }
    T* operator-> () const { return &**this; }
    Iter& operator++ () { cur = (pre = cur)->next; return *this; }
    friend bool operator!= (Iter<T> const& lhs, Iter<T> const& rhs) {
        return lhs.pre != rhs.pre;
        }
    };
template <class T>
struct Slist {
    Node<T>* tail;
    Slist () : tail(0) { }
    typedef Iter<T> iterator;
    iterator begin () { return iterator(0, tail ? tail->next : 0); }
    iterator end () { return iterator(tail, tail ? tail->next : 0); }
    bool empty () const { return tail == 0; }
    iterator insert (iterator pos, T const& v) {
        iterator ret(pos.pre, new Node<T>(pos.cur, v));
        if (! tail) // empty list
            tail = ret.cur->next = ret.cur;
        else if (! ret.pre) // at front
            tail->next = ret.cur;
        else {
            ret.pre->next = ret.cur;
            if (ret.pre == tail) // at back
                tail = ret.cur;
            }
        return ret;
        }
    iterator erase (iterator pos) {
        iterator ret(pos.pre, pos.cur->next);
        if (pos.cur == tail) // erase back
            if (tail->next == tail) // becomes empty
                tail = ret.pre = ret.cur = 0;
            else
                (tail = ret.pre)->next = ret.cur;
        else if (ret.pre == 0) // erase front
            tail->next = ret.cur;
        else
            ret.pre->next = ret.cur;
        delete pos.cur;
        return ret;
        }
    };