Jerry Coffin <jcoffin@taeus.com> writes:

> The reality is that the STL containers make a fairly explicit tradeoff
> between memory usage and speed, choosing speed as their primary goal.

True

> The vector class is typically implemented so that it can occupy
> roughly twice as much space as you're actually using.

Untrue: this is 1.3, not 2 on most (all) implementations, and
it could be any number > 1 (strictly superior). However the std
encourage implementations to be like most implementations are:
reallocation factor of 2, which means that 0.25 of the space
is unused on average if the vector grows, which gives us the
above 1.3.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern/std-c++/faq.html                  ]

James Kuyper wrote:
>
> Christopher Eltschka wrote:
> ...
> > Well, I never said that it is not possible to use such a list, to
> > define iterators for it, or even that it doesn't conform to the
> > requirements of an STL list. But it doesn't conform to what I would
> > expect from a "doubly linked" list: That given a *node*, you can find
> > out the previous/next nodes. Node that CD2 doesn't state that list<T>
> > is a doubly linked list, but only that it supports bidirectional
> > iterators. Of course a doubly linked list conforms to this reqirement,
> > and probably the writers had exactly this in mind, but that doesn't
> > make every conforming list "doubly linked".
> > Maybe your definition of doubly linked lists is different from mine...
>
> It acts like a doubly linked list.

Our definition of doubly linked list seems indeed to be different.

> As long as you don't have to modify
> the STL code itself, why should you care about the implementation
> details?

If I use STL list, I don't care if it's a doubly linked list. I only
care if it's an STL list. If I care if it's a doubly linked list, I
won't use the STL list.

> The point remains that there does exist an implementation of an
> STL list that requires no more space per node than than an singly linked
> list.

I never argued agains this. I only argued against this implementation
being a doubly linked list. Note that the standard (at least CD2)
doesn't speak of a doubly linked list either in defining the list
template.

[...]
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Christopher Eltschka <celtschk@physik.tu-muenchen.de> writes:

>> > Why is there no singly linked list in the STL?

...

>> The implementation involves the two ends of the list containing actual
>> pointers.  The rest contain the XOR of the two pointers.  To get one

...

Or you can use the vector<slist> that is part of the SGI STL distribution.

--
Paul T. Miller                | paul@elastic.avid.com
Principal Engineer            | Opinions expressed here are my own.
Avid Technology, Inc. Madison - Graphics and Effects Software Group
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern/std-c++/faq.html                  ]

Nathan Myers wrote:
>
> Christopher Eltschka  <celtschk@physik.tu-muenchen.de> wrote:
> >Jerry Coffin wrote:
> >> If you're really
> >> excited about saving space, you can generally implement a doubly
> >> linked list in the same amount of space as a singly linked list.
> >> ...
> >What you describe is not exactly a doubly linked list. You can iterate
> >from the first to the last item, and from the last to the first one.
> >But given an arbitrary pointer to the middle of the list, you cannot
> >get both neighbouring pointers - you cannot even tell, if you are in
> >the middle or at the end of your list!
>
> Sorry, this is not right.  An iterator for such a list is more than
> just a pointer; it contains the information necessary to step forward
> and back.

Well, I never said that it is not possible to use such a list, to
define iterators for it, or even that it doesn't conform to the
requirements of an STL list. But it doesn't conform to what I would
expect from a "doubly linked" list: That given a *node*, you can find
out the previous/next nodes. Node that CD2 doesn't state that list<T>
is a doubly linked list, but only that it supports bidirectional
iterators. Of course a doubly linked list conforms to this reqirement,
and probably the writers had exactly this in mind, but that doesn't
make every conforming list "doubly linked".
Maybe your definition of doubly linked lists is different from mine...
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Christopher Eltschka wrote:
...
> Well, I never said that it is not possible to use such a list, to
> define iterators for it, or even that it doesn't conform to the
> requirements of an STL list. But it doesn't conform to what I would
> expect from a "doubly linked" list: That given a *node*, you can find
> out the previous/next nodes. Node that CD2 doesn't state that list<T>
> is a doubly linked list, but only that it supports bidirectional
> iterators. Of course a doubly linked list conforms to this reqirement,
> and probably the writers had exactly this in mind, but that doesn't
> make every conforming list "doubly linked".
> Maybe your definition of doubly linked lists is different from mine...

It acts like a doubly linked list. As long as you don't have to modify
the STL code itself, why should you care about the implementation
details? The point remains that there does exist an implementation of an
STL list that requires no more space per node than than an singly linked
list. That fact argues against providing a singly linked list in the
STL. On the flip side, it is quite clear that all iterator operations
with this implementations are somewhat slower than they would be in a
true doubly linked list, and significantly slower than a true singly
linked list. Therefore the subject line of this thread remains a
reasonable question.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote in message <6baklv$k3j$1@shell7.ba.best.com>...
>Christopher Eltschka  <celtschk@physik.tu-muenchen.de> wrote:
>>Jerry Coffin wrote:
>>> If you're really
>>> excited about saving space, you can generally implement a doubly
>>> linked list in the same amount of space as a singly linked list.
>>> ...
>>What you describe is not exactly a doubly linked list. You can iterate
>>from the first to the last item, and from the last to the first one.
>>But given an arbitrary pointer to the middle of the list, you cannot
>>get both neighbouring pointers - you cannot even tell, if you are in
>>the middle or at the end of your list!
>
>Sorry, this is not right.  An iterator for such a list is more than
>just a pointer; it contains the information necessary to step forward
>and back.

But what do you store in the iterator? And does it still work if you
insert an element between the "current" and "next" nodes of an existing
iterator? I'm no idiot, but I'm having a lot of trouble picturing how
this would work on a dynamic list.

Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Nathan Myers wrote in message <6b9dcj$ncr$1@shell7.ba.best.com>...
...
>The intended use of allocators is to use the right allocator for the
>type you intend to allocate.  If you want an int, get it from an
>allocator<int>.  If you want a node, get it from an allocator<node>.
>Each allocator specialization converts freely to any other.

Each specialization of std::allocator converts freely to any other
specialization of std::allocator, but that does nothing for custom
allocators.

If I've given list an allocator of MyAlloc<int>, it can't convert that to
MyAlloc<node>, which is what I want, or even std::allocator<node>, which is
what you seem to be suggesting it should use (and which I very specifically
don't want it to do).  In short, custom allocators don't quite work with
STL, unless I've misunderstood things even worse than I thought possible.

- Brad
--
----------------------------------------------------------------------------
Brad Daniels                  |  Was mich nicht umbringt macht mich hungrig.
Mission Critical Software     |   - Otto Nietzche
Standard disclaimers apply    |     (Friedrich's corpulent brother)
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Brad Daniels wrote in message <6bafo6$mcl$1@news1-alterdial.UU.NET>...
>
>If I've given list an allocator of MyAlloc<int>, it can't convert that
to
>MyAlloc<node>, which is what I want...

That's what the rebind template is for. The container should use

    Allocator::rebind<node>::other

to "rebind" its allocator parameter from the content type to the node
type. For example, "MyAlloc<T>::rebind<node>::other" is always
MyAlloc<node>. Not all compilers, nor all implementations of the
standard library, support this yet.

Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Bradd W. Szonye <bradds@concentric.net> wrote:
>Nathan Myers wrote in message <6baklv$k3j$1@shell7.ba.best.com>...
>>Christopher Eltschka  <celtschk@physik.tu-muenchen.de> wrote:
>>>Jerry Coffin wrote:
>>>> If you're really
>>>> excited about saving space, you can generally implement a doubly
>>>> linked list in the same amount of space as a singly linked list.
>>>> ...
>>>What you describe is not exactly a doubly linked list. You can iterate
>>>from the first to the last item, and from the last to the first one.
>>>But given an arbitrary pointer to the middle of the list, you cannot
>>>get both neighbouring pointers - you cannot even tell, if you are in
>>>the middle or at the end of your list!
>>
>>Sorry, this is not right.  An iterator for such a list is more than
>>just a pointer; it contains the information necessary to step forward
>>and back.
>
>But what do you store in the iterator? And does it still work if you
>insert an element between the "current" and "next" nodes of an existing
>iterator? I'm no idiot, but I'm having a lot of trouble picturing how
>this would work on a dynamic list.

It's fairly common in the STL for insert operations to invalidate
iterators.  What you need in the iterator is pointers to two adjacent
nodes.  XORing either node's "next" member with the other node pointer
gets you a pointer to the next-nearest node.

As Jerry Coffin pointed out, this is all kind of academic, now,
because we have better ways to save space in lists.  But it's fun
to think about.

Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

>Bradd W. Szonye <bradds@concentric.net> wrote:

>>But what do you store in the iterator
>>[for an XOR dlist]? And does it still work if you
>>insert an element between the "current" and "next" nodes of an
existing
>>iterator? I'm no idiot, but I'm having a lot of trouble picturing how
>>this would work on a dynamic list.

Nathan Myers wrote in message <6bbjnl$jmt$1@shell7.ba.best.com>...

>It's fairly common in the STL for insert operations to invalidate
>iterators.  What you need in the iterator is pointers to two adjacent
>nodes.  XORing either node's "next" member with the other node pointer
>gets you a pointer to the next-nearest node.

Okay, that's what I thought, but I wanted some confirmation from
somebody who'd actually used it. There are, of course two disadvantages:
list<> requires that insert() does not invalidate iterators, so an XOR
dlist is not an appropriate implementation for std::list; it would be
fine for my::dlist<>, however, so long as your users are aware of the
invalidation. The other problem is the "fat iterator" problem: bulky
iterators or pointers are a common criticism of object-space-saving
implementations (like my own vptr-in-ptr object model).

I'm starting to take heed of fat iterator problems, not because they
take up too much space--I'm not convinced that mass storage of iterators
is common--but because they're often passed by value. Thin iterators are
good candidates for register storage and easy value passing, fat
iterators are not. So you end up with a minor space and major
performance problem. The XOR iterator is especially nasty because it
requires three pointers, and popular memory managers don't typically
like multiple-of-three sizes.

Personally, I prefer a list structure that uses two links per node and
one node pointer per iterator. One implementation I have in mind for
splay_multiset uses dlists for tree nodes. The requirements for this
dlist include the ability to detect the begining/end of the list through
an iterator without a pointer to the list itself in the iterator. Since
the nodes have an even alignment requirement, I use the unused low bit
of the link pointer to indicate begining/end. Yes, there are lots of
ways to save a bit of space here and there in a list.

Bradd W. Szonye
bradds@concentric.net
http://www.concentric.net/~Bradds
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Brad Daniels <brad.daniels@missioncritical.com> wrote:
>Nathan Myers wrote:
>...
>>The intended use of allocators is to use the right allocator for the
>>type you intend to allocate.  If you want an int, get it from an
>>allocator<int>.  If you want a node, get it from an allocator<node>.
>>Each allocator specialization converts freely to any other.
>
>Each specialization of std::allocator converts freely to any other
>specialization of std::allocator, but that does nothing for custom
>allocators.

Clue:  Allocator::rebind<>.

Of course certain unnameable compilers cannot cope with
the standard rebind or any reasonable variation of it.
Hence, incompatibility.  This too will pass.

Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

[ mod note: This discussion has strayed far from topics that belong
  in this newsgroup, however interesting it may be. Let's keep
  further discussion on-topic. -sdc ]

| The approach described by Mr. Coffin [doubly-linked list with one
| "pointer" per item by XOR'ing], by the way, was patented by IBM.
| Probably it's expired by now.

I first heard about this technique in late 1972/early 1973.  By then it
was "well known".  So, yes, if there was a patent, it's long expired.
However, I have my doubts about the claim:  The PTO didn't accept
software patents until years after this technique was widely discussed,
and it's hard to see how it could have been cast as a hardware technique
(the trick used to get some software patents into the system).

|                                (Extra credit for whoever comes up with
| the patent number!)

Well, a search of the IBM patent server:

 http://www.patents.ibm.com/ibm.html

which at this point has all US patents back to 1971, found nothing.  (I
tried an advanced search for:

 list <NEAR> (store <OR> storage <OR> memory)

in the abstract found exactly one patent:

      5001697 Method to automatically vary displayed object size with
  variations in window size

Of course, it could be described in some bizarre way which I didn't
think of, so others ought to try it.  If the patent does exist, it would
be interesting to see it!

BTW, I long ago spent time trying to understand *why* this technique
works, and in doing so developed a related technique.  Keep the same
single pointer field, but *reverse the pointers* as you traverse the
list.  That is:  Think of the list as passing through your hands.  At
any given time, one node is in your hands.  In general, part of the list
goes off to your right, and part to your left.  You need to keep track
of two links, one to the first node on your left, one to the first node
on your right.  Each further node, however, only has to keep track of
one link:  The nodes on your left have a link going further left, and
those on your right a link going further right.  As you shift to the
right or left, you have to modify the link of the node you're letting go
of to point in the appropriate direction.

The implementation of this is quite trivial, and requires no
manipulation of pointers as anything but pointers.  Of course, you can
only have one iterator traversing the list at a time, since the
traversal is destructive to access anywhere but at the point "currently
in your hands".  So this isn't a generally-applicable technique.  (It
does get used in certain garbage-collection algorithms, however:  During
the mark phase, you flip all the pointers so that each node points to
(the head of a list of) all the nodes that are supposed to point to it.
Then, after the sweep phase, you flip the pointers back.)

The XOR technique simulates the "node in your hand" technique in a non-
destructive fashion.  Essentially, you keep around exactly the data
needed to re-construct the left-hand links on the left side, and
conversely, on demand.
       -- Jerry



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

"Brad Daniels" <brad.daniels@missioncritical.com> writes:

> If I've given list an allocator of MyAlloc<int>, it can't convert that to
> MyAlloc<node>, which is what I want, or even std::allocator<node>, which is
> what you seem to be suggesting it should use (and which I very specifically
> don't want it to do).  In short, custom allocators don't quite work with
> STL, unless I've misunderstood things even worse than I thought possible.

Actually, the standard does provide a way of converting the type
My_Allocator<T> to the type My_Allocator<U>.  It also provides a way
of converting an object of type My_Allocator<T> to an object of type
My_Allocator<U>.  (Which, of course, you also have to be able to do;
converting types isn't enough.)

Conversion of types, unfortunatley, uses some of the ugliest syntax in
the C++ language: if Alloc is an allocator type, then
    typename Alloc::template rebind<T>::other
is the correspoding allocator type for type T.  It's ugly, but it
works.

Conversion of objects just uses ordinary constructor syntax.  If a is
an object of type My_Allocator<T>, then you can just write something
like this.

    My_Allocator<U> a1(a);

The standard is quite explicit about this.  Conversion of types is
described in row 8 of Table 32 (Allocator requirements), and
conversion of objects is described in the third row from the bottom of
the same table.

(I'm referring to the version of the working paper dated 25 November
1997.)



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Jerry Coffin wrote:
>
> In article <w2xbtwp6bju.fsf@woodstock.cis.ohio-state.edu>,
> wenger@cis.ohio-state.edu says...
> >
> > Why is there no singly linked list in the STL?
>
> I suspect it's because it adds relatively little functionality.
>
> > The STL list
> > supports bidirectional iterators with constant time operations
> > so it must be implemented as a doubly linked list.  A singly
> > linked list obviously requires half the pointers of a doubly
> > linked one.
>
> It may be obvious, but it's generally incorrect.  If you're really
> excited about saving space, you can generally implement a doubly
> linked list in the same amount of space as a singly linked list.
> Traversing the list becomes marginally slower due to having to do an
> exclusive or before dereferencing each pointer, but other than that
> about the only penalty is in readability.

There's a major loss of capability here: if you have a pointer to a node
in a list like this you cannot unlink it from the list in constant time.
That is, the usual technique for unlinking a node (null checking
ignored) is:

node->next->prev = prev;
node->prev->next = next;

You can't do this with the xor trick -- you have to walk the list from
one end or the other in order to get the information you need to sort
out the pointers.
 -- Pete
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern/std-c++/faq.html                  ]

Jerry Coffin wrote in message ...
..
>The implementation involves the two ends of the list containing actual
>pointers.  The rest contain the XOR of the two pointers.  To get one
>pointer, you XOR the value with the previous pointer.  I.e. to
>traverse frontward, you start by dereferencing the first pointer.  To
>get to the next item, you XOR the first pointer with the second.
>
>To traverse in reverse, you simply do the same thing, but start with
>the pointer to the end of the list.

That's a really cool hack, but it doesn't strike me as a good idea in any
context where someone might want to use garbage collection.  Any garbage
collection scheme I've ever heard of (and certainly all of the existing
garbage collectors for C++) would tend to free memory at inopportune times
if you used such an approach.  When writing a standard template library,
precluding garbage collection is a bad idea.

I do think it's odd that the STL doesn't have explicit dlist and slist
classes, but unless you use nonstandard custom allocators, malloc overhead
is going to be a bigger deal than keeping around extra pointers.

What I mean by "nonstandard" custom allocators is that allocators allocate
in units of objects, so e.g. calling allocate(5) on an integer allocator
would allocate space for five integers, not five bytes.  This means that the
node allocation can do one of three things:

1. It can ignore your allocator and use the default allocator.
2. It can find the smallest multiple of your object size that is large
enough to hold a node (and given that a node contains an object of your
type, this multiple is at least 2).  Note that it should also make your
object the first element of its node structure to ensure proper alignment.
3. It can call a nonstandard member function in your allocator to allow it
to allocate a given number of bytes.

MSVC++ 5.0's STL takes the third approach, and calls alloc._Charalloc() to
allocate the right amount of memory.  I discovered this fact when I tried to
implement a space-efficient custom allocator class for fixed-size objects.
I ended up having to decide what the size of an allocation unit was by
saving the first size passed to _Charalloc (or the object size if allocate()
was called first).  I then added an assertion to make sure subsequent
allocations were the same size.

It's an annoying kludge, and one of my main gripes with the STL revolves
around the way allocators work/don't work.

- Brad
--
----------------------------------------------------------------------------
Brad Daniels                  |  Was mich nicht umbringt macht mich hungrig.
Mission Critical Software     |   - Otto Nietzche
Standard disclaimers apply    |     (Friedrich's corpulent brother)



[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Brad Daniels <brad.daniels@missioncritical.com> wrote:
>What I mean by "nonstandard" custom allocators is that allocators allocate
>in units of objects, so e.g. calling allocate(5) on an integer allocator
>would allocate space for five integers, not five bytes.  This means that
>the node allocation can do one of three [wrong, thus elided] things: ...

It's not surprising that Mr. Daniels does not understand the
relationship between allocators and containers.  The compiler
he uses is too buggy to implement it correctly anyway.

The intended use of allocators is to use the right allocator for the
type you intend to allocate.  If you want an int, get it from an
allocator<int>.  If you want a node, get it from an allocator<node>.
Each allocator specialization converts freely to any other.

>[Some unspeakable company's] STL takes the [third broken] approach,
>and calls alloc._Charalloc() to allocate the right amount of memory
>[thus bollixing Daniels's code].

Eventually most vendors will support the standard, more or less.
In the meantime we muddle along writing nonportable code.

Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Jerry Coffin wrote:
>
> In article <w2xbtwp6bju.fsf@woodstock.cis.ohio-state.edu>,
> wenger@cis.ohio-state.edu says...
> >
> > Why is there no singly linked list in the STL?
>
> I suspect it's because it adds relatively little functionality.
>
> > The STL list
> > supports bidirectional iterators with constant time operations
> > so it must be implemented as a doubly linked list.  A singly
> > linked list obviously requires half the pointers of a doubly
> > linked one.
>
> It may be obvious, but it's generally incorrect.  If you're really
> excited about saving space, you can generally implement a doubly
> linked list in the same amount of space as a singly linked list.
> Traversing the list becomes marginally slower due to having to do an
> exclusive or before dereferencing each pointer, but other than that
> about the only penalty is in readability.
>
> The implementation involves the two ends of the list containing actual
> pointers.  The rest contain the XOR of the two pointers.  To get one
> pointer, you XOR the value with the previous pointer.  I.e. to
> traverse frontward, you start by dereferencing the first pointer.  To
> get to the next item, you XOR the first pointer with the second.
>
> To traverse in reverse, you simply do the same thing, but start with
> the pointer to the end of the list.

What you describe is not exactly a doubly linked list. You can iterate
from the first to the last item, and from the last to the first one.
But given an arbitrary pointer to the middle of the list, you cannot
get both neighbouring pointers - you cannot even tell, if you are in
the middle or at the end of your list!

You can do sort of a "doubly linked list" by implementing a circular
singly linked list with a special starter node. Then you can get the
previous linked list by going forward (through the special node)
until you find the node which hat your node as next item. Of course,
iterating back is then O(N) instead of O(1). But if you need iterating
back only occasionally and are concerned about size, it may be the
best solution.
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Christopher Eltschka wrote:
>
> Jerry Coffin wrote:

> > If you're really
> > excited about saving space, you can generally implement a doubly
> > linked list in the same amount of space as a singly linked list.
>
> What you describe is not exactly a doubly linked list.

It's a possible implementation of list<> as specified in the
standard. But completly gc unfriendly, which is an issue...

So yes there is room for slist<>, but remember that only the
most usefull containners are included in the std, and the STL
is much more than a 'set' of containners: it's a list of
requirements, so you can trivially express what's a slist<>
in the STL. (And different people will write it in a similar
way.)

But yes I would have like to have std::slist.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Jerry Coffin <jcoffin@taeus.com> wrote:
>If you're really
>excited about saving space, you can generally implement a doubly
>linked list in the same amount of space as a singly linked list
[by XORing pointers].

"You" can't, but compiler vendors can.  It's "undefined behavior" to
convert pointers to integers and back, but of course implementers of
the standard library can engage in all manner of non-standard chicanery,
as long as it actually works for them and presents a standard interface.

Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

In article <6b84sv$amp$1@news1-alterdial.UU.NET>,
brad.daniels@missioncritical.com says...

[ ... ]

> That's a really cool hack, but it doesn't strike me as a good idea in any
> context where someone might want to use garbage collection.  Any garbage
> collection scheme I've ever heard of (and certainly all of the existing
> garbage collectors for C++) would tend to free memory at inopportune times
> if you used such an approach.  When writing a standard template library,
> precluding garbage collection is a bad idea.

I'm not saying it's a particularly good idea under any circumstances.
The reality is that the STL containers make a fairly explicit tradeoff
between memory usage and speed, choosing speed as their primary goal.
The vector class is typically implemented so that it can occupy
roughly twice as much space as you're actually using.  To fit the
requirements, I believe its worst case is always to multiply the used
space by some constant, rather than ever limiting the unused space to
some constant value.

Ultimately, if you decide you have a good enough reason for using a
singly linked list, you can write one yourself fairly easily.  As long
as you follow the basic guidelines for writing a standard container,
it's fairly easy to integrate with other code that uses the built-in
containers.  Basically, it'll only accept one direction of iterators,
but that's about it.  (If you wanted, you could make it accept the
other direction of iterators as well, but getting to the next object
in one direction would be O(1) and in the other direction would be
O(N).

> I do think it's odd that the STL doesn't have explicit dlist and slist
> classes, but unless you use nonstandard custom allocators, malloc overhead
> is going to be a bigger deal than keeping around extra pointers.

I'm not particularly convinced that it's odd at all.  Just for fun
last night I did some looking through code I have handy that uses
lists, (in the standard library or otherwise) and at least with the
memory allocators I normally used, the average overhead of a doubly
linked list compared to a singly linked list looks like it's averaging
somewhere between 10 and 12%.

If links are a significant overhead, you're typically talking about
storing relatively small objects.  In this case, you're probably best
off having a small array of objects in each node, typically adding
another integer type to act as a bitmap showing which objects are used
and which aren't.

Oddly enough, as long as the arrays are fairly small (I've typically
used 16 items) this often speeds things up as well.  Moving an average
of 8 small items to make room for a new one seems to be faster than
calling a memory allocator.

--
    Later,
    Jerry.

The Universe is a figment of its own imagination.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]

Christopher Eltschka  <celtschk@physik.tu-muenchen.de> wrote:
>Jerry Coffin wrote:
>> If you're really
>> excited about saving space, you can generally implement a doubly
>> linked list in the same amount of space as a singly linked list.
>> ...
>What you describe is not exactly a doubly linked list. You can iterate
>from the first to the last item, and from the last to the first one.
>But given an arbitrary pointer to the middle of the list, you cannot
>get both neighbouring pointers - you cannot even tell, if you are in
>the middle or at the end of your list!

Sorry, this is not right.  An iterator for such a list is more than
just a pointer; it contains the information necessary to step forward
and back.

The approach described by Mr. Coffin, by the way, was patented by IBM.
Probably it's expired by now.  (Extra credit for whoever comes up with
the patent number!)

Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Why is there no singly linked list in the STL?  The STL list
supports bidirectional iterators with constant time operations
so it must be implemented as a doubly linked list.  A singly
linked list obviously requires half the pointers of a doubly
linked one.

(I'm sure this has been discussed but it's not in the FAQ.)

--

- Rephael Wenger, Associate Professor, Ohio State U.,
Dept. of Comp. Sci., 2015 Neil Ave., Columbus, OH 43210-1277.
tel: (614) 292-6253. e-mail: wenger@cis.ohio-state.edu


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

Rephael Wenger <wenger@cis.ohio-state.edu> wrote:
>Why is there no singly linked list in the STL?  [...]
>(I'm sure this has been discussed but it's not in the FAQ.)

It has indeed. Several vendors supply an slist<>, but I think the real
answer boils down to this:

1. STL was kept as simple as possible when proposed to the committee, with
the realization that a proposal with all sorts of (nice but arguably)
unnecessary functionality stood a lower chance of being adopted. As it is,
there was a lot of stuff in the proposal, although it was adopted and
refined to its present form.

2. No matter what you add, someone will come up with another "useful"
template. STL/StdLib presents an extensible framework for pretty
seamlessly adding any arbitrary containers that you happen to like...
and/or that vendors would like to supply (such as slist).

Herb


---
Herb Sutter (mailto:herbs@cntc.com)

Current Network Technologies Corp  2695 North Sheridan Way, Suite 150
www.cntc.com www.peerdirect.com    Mississauga Ontario Canada L5K 2N6


[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]

In article <w2xbtwp6bju.fsf@woodstock.cis.ohio-state.edu>,
wenger@cis.ohio-state.edu says...
>
> Why is there no singly linked list in the STL?

I suspect it's because it adds relatively little functionality.

> The STL list
> supports bidirectional iterators with constant time operations
> so it must be implemented as a doubly linked list.  A singly
> linked list obviously requires half the pointers of a doubly
> linked one.

It may be obvious, but it's generally incorrect.  If you're really
excited about saving space, you can generally implement a doubly
linked list in the same amount of space as a singly linked list.
Traversing the list becomes marginally slower due to having to do an
exclusive or before dereferencing each pointer, but other than that
about the only penalty is in readability.

The implementation involves the two ends of the list containing actual
pointers.  The rest contain the XOR of the two pointers.  To get one
pointer, you XOR the value with the previous pointer.  I.e. to
traverse frontward, you start by dereferencing the first pointer.  To
get to the next item, you XOR the first pointer with the second.

To traverse in reverse, you simply do the same thing, but start with
the pointer to the end of the list.



--
    Later,
    Jerry.

The Universe is a figment of its own imagination.
---
[ comp.std.c++ is moderated.  To submit articles: Try just posting with your
                newsreader.  If that fails, use mailto:std-c++@ncar.ucar.edu
  comp.std.c++ FAQ: http://reality.sgi.com/austern/std-c++/faq.html
  Moderation policy: http://reality.sgi.com/austern/std-c++/policy.html
  Comments? mailto:std-c++-request@ncar.ucar.edu
]