Re: [boost] Hash tables and singly linked lists

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-16 20:13:21

On Tue, 16 Jan 2001, Matthew Austern wrote:

> A good point.  That sounds like a useful data structure; it has
> all of the advantages of an slist with a pointer to the last element,
> and fewer of the disadvantages.  (It still has the disadvantage of
> increased iterator fragility.)

Yes.  About as bad as deque in general and worse at the ends.

Something that I did not think of until later.  It meets the
requirements for std::queue.  No surprise, since it is the
classical linked queue plus an unusual iterator.  It should
be better space and worst case time than any of the standard
containers in that role.  Average time may not be as good as deque.

I will be interested in your timings.  I am about to get swamped
and will likely be quiet if not silent for the next four months.

John