 # Boost :

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;
}
};