Re: why not

["Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>]

"Matthew Heaney" <mheaney@on2.com> wrote in message
news:tu2t7oiig3e9d9@corp.supernews.com...
>
> If you need to traverse backwards, you need a doubly-linked list.
>
Obviously. Just an observation that a singly linked list would save the
overhead of extra pointers and many structures (stacks, single-ended-queues)
might benefit from the lack of the extra pointer. However, in most
instances, I'd think that the extra pointer overhead would be small enough
that you might just as well have it there plus all the operations you
*don't* need for a simple stack, just because then you've got a single
package that does the whole job.


> Of course, the STL has std::slist, which is a singly-linked list.  There
> wouldn't be any harm in including that in the library too.
>
Yes there would. Start working through all the combinations of stuff that
are being proposed:

(((Single List/Double List) * (Sorted/Unsorted)) + Map) *
(Bounded/Unbounded) * (Task Safe/Task Unsafe)

Thats 20 variants right there. We can easily envision other variants such as
Private/Limited-Private or Inherited/Generic. That's 80. The problem is to
get the number of variants down to some manageable level that covers some
reasonable amount of turf and will satisfy the largest possible body of
users. Too many variants makes it a) complex and b) unlikely to be realized.

That's why I would suggest limiting the first cut to a Double List
(Sorted/Unsorted) & Map of Unbounded, Task Unsafe variety. That gets you
down to 3 key packages that would probably cover a large percentage of the
uses.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/