In article <01be4d93$6bc29c80$88f5accf@tabtieng>, Thepthai Tabtieng
<tabtieng@FOOBARerols.com> writes
>John Aldridge <jpsa@jjdash.demon.co.uk> wrote in article
><qEOlpGAWE4s2EwFc@jjdash.demon.co.uk>...
>> In article <01be499b$f66ab760$d1e87ad1@tabtieng>, Thepthai Tabtieng
>> <tabtieng@FOOBARerols.com> writes
>> >
>> >I'm fairly new to STL and stdc++, but is there a singly linked list class
>> >that has a constant time append() method, ala SLList in libg++.  I would
>> >like to be able to traverse the list in the same order as how the data
>> >being put in the list and at the same time don't want to use doubly linked
>> >list.
>>
>> The straight answer is no.
>>
>> However, I'm curious as to why you want one.  For all the applications
>> for which I used to use a singly linked list, the standard deque
>> template class provides a superior solution.
>
>I'm not following what you are trying to get at, but as I said it
>before I want to be able to traverse the items in the list in the same
>order as how the data is being put in the list.  For this I need the
>append function, push_front will present me with data in reverse
>order.  I love the implementation of SLList in libg++ where it is a
>circular link list with a pointer to tail instead of the head.  push,
>pop_front and append are all constant time operation in the scheme.

That's exactly the point I was trying to make.  With a deque,
push_front, pop_front, push_back, pop_back and iteration in either
direction _are_ constant time operations.  And it typically doesn't use
_any_ extra space for pointers (well, hardly any :-).
--
Cheers,
John


[ 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              ]

Thepthai Tabtieng wrote:
....
> I'm not following what you are trying to get at, but as I said it
> before I want to be able to traverse the items in the list in the same
> order as how the data is being put in the list.  For this I need the
> append function, push_front will present me with data in reverse
> order.  I love the implementation of SLList in libg++ where it is a

If you want to retrieve the data in the same order it was put in, then
you just have to use the right iterator. If you append to the deque
using push_front(), then you should take it off with pop_back(), and
traverse the list using

 foreach(fifo.rbegin(), fifo.rend(), /* whatever */);

or whatever the appropriate algorithms is. If you append using
push_back(), the you should take it off with pop_front(), and traverse
the list in the more conventional way:

 foreach(fifo.begin(), fifo.end(), /* whatever */);

....
> virtually no lost in performance.  I could use list class which is a
> doubly linked list, but I don't want to pay an extra word of space for
> each item,  I don't need to insert or delete stuff from the list for

If the space is that important to you, then you will have to implement
your own singly linked list, which is annoying.


[ 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              ]

I'm fairly new to STL and stdc++, but is there a singly linked list class
that has a constant time append() method, ala SLList in libg++.  I would
like to be able to traverse the list in the same order as how the data
being put in the list and at the same time don't want to use doubly linked
list.

Maybe I'll do a new one myself.


[ 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              ]

In article <01be499b$f66ab760$d1e87ad1@tabtieng>,
  "Thepthai Tabtieng" <tabtieng@FOOBARerols.com> wrote:
>
>
> I'm fairly new to STL and stdc++, but is there a singly linked list class
> that has a constant time append() method, ala SLList in libg++.  I would
> like to be able to traverse the list in the same order as how the data
> being put in the list and at the same time don't want to use doubly linked
> list.

There's no standard singly-linked list class. If you don't mind
something non-standard, you might want to consider SGI's STL,
which includes slist<T,Alloc>.

However, consider the fact that singly-linked lists offer far
fewer services than list<T,Alloc>. The biggest difference is
that a list offers bidirectional iterators, while an slist can
offer only forward iterators. There are certain algorithms
that can use bidirectional operators but not forward iterators;
for instance, inplace_merge, next_permutation, and reverse.
These algorithms will not work with singly-linked lists.

A singly-linked list has an overhead of one pointer per node,
while list<> has an overhead of two pointers per node. Are
your memory constraints really so rigid that the extra pointer
is unacceptable?

> Maybe I'll do a new one myself.

Rolling your own robust singly-linked list, in a manner that meets
the standard requirements for a container, might not be as easy as
you think it is.

The biggest problem is the way the standard defines insert:

    insert(p,t)          Inserts a copy of [element] t before
                         [the element pointed to by iterator] p

By definition, a singly-linked list contains a next pointer but
not a prev pointer. In order to insert a new node BEFORE a given
node, you must find the PREVIOUS node and adjust it's next pointer.
In order to find the PREVIOUS node, you must walk the entire list.
The result is that insert(p,t) is linear speed O(n) instead of
amortized constant speed O(1).

There are two techniques to avoid the problem, and you would be
wise to use them both. First, you should follow the SGI example by
creating a member function insert_after(p,t). Unlike insert(), this
function would insert member t AFTER the element pointed to by p.
This could be done in amortized constant time O(1).

The second technique is to recognize a special case for adding
elements to the end. Your list container would contain a pointer
to the last element. In insert(p,t), if p==end(), then you would
do the equivalent of insert_after(last,t). This is also what
your append(t) would do, although a better name would be
push_back(t) to match the rest of the standard containers.

----
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own
---
[ 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              ]

In article <01be499b$f66ab760$d1e87ad1@tabtieng>, Thepthai Tabtieng
<tabtieng@FOOBARerols.com> writes
>
>I'm fairly new to STL and stdc++, but is there a singly linked list class
>that has a constant time append() method, ala SLList in libg++.  I would
>like to be able to traverse the list in the same order as how the data
>being put in the list and at the same time don't want to use doubly linked
>list.

The straight answer is no.

However, I'm curious as to why you want one.  For all the applications
for which I used to use a singly linked list, the standard deque
template class provides a superior solution.

It puzzles me that the books seem to stress the point that you can
push/pop_front on a deque, and that this is what makes it distinctive
and useful.

In fact, the feature that makes it most useful in my experience is that
it efficiently handles collections of a size which is both _not_ known
in advance, and unbounded.  The second (related) property which makes it
the container of choice in many circumstances is that existing elements
don't move when new ones are appended.  This means that you can safely
hang on to pointers to them.
--
Cheers,
John


[ 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              ]

John Aldridge <jpsa@jjdash.demon.co.uk> wrote in article
<qEOlpGAWE4s2EwFc@jjdash.demon.co.uk>...
>
> In article <01be499b$f66ab760$d1e87ad1@tabtieng>, Thepthai Tabtieng
> <tabtieng@FOOBARerols.com> writes
> >
> >I'm fairly new to STL and stdc++, but is there a singly linked list class
> >that has a constant time append() method, ala SLList in libg++.  I would
> >like to be able to traverse the list in the same order as how the data
> >being put in the list and at the same time don't want to use doubly linked
> >list.
>
> The straight answer is no.
>
> However, I'm curious as to why you want one.  For all the applications
> for which I used to use a singly linked list, the standard deque
> template class provides a superior solution.

I'm not following what you are trying to get at, but as I said it
before I want to be able to traverse the items in the list in the same
order as how the data is being put in the list.  For this I need the
append function, push_front will present me with data in reverse
order.  I love the implementation of SLList in libg++ where it is a
circular link list with a pointer to tail instead of the head.  push,
pop_front and append are all constant time operation in the scheme.
So if you still want to treat it like a FIFO stack you still can with
virtually no lost in performance.  I could use list class which is a
doubly linked list, but I don't want to pay an extra word of space for
each item,  I don't need to insert or delete stuff from the list for
this particular application.
---
[ 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              ]