when list is best

[pauldepstein]

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Paul Epstein

[Phlip]

pauldepstein wrote:

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Is this for a quiz? Use list when random inserts and deletes must take
constant (minimal) time.

Use a vector if you have not yet characterized your performance needs (and
if you never will), because its most common actions (push, pop, iterate),
are all nearly constant time, with a minimal memory footprint.

--
Phlip
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!

[Thomas Tutone]

pa**********@att.net wrote:

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Any situation in which after the container is populated, there are
frequent insertions and deletions other than from either end. Suppose
you have a container of 50 elements. Suppose you want to delete the
twelfth element and replace it with 19 new elements. Suppose you want
to do this repeatedly, and the container changes in this manner
throughout its lifetime. vector and deque would both probably be
ill-suited to this task, whereas list would work fine.

Of course, the only way to know for sure would be to profile your code
and see whether it made a difference.

Best regards,

Tom

[Phlip]

Thomas Tutone wrote:

Of course, the only way to know for sure would be to profile your code
and see whether it made a difference.

In general, only profiling will have the last word on performance.

In the specific case of algorithms dealing with large batches of elements,
you can also calculate the O*n performance formula, where O is the overhead
of each operation, and n is the number of elements. Some sorts, for example,
are O log n. That means n input elements cause log n operations, and the
overhead of each one is O, so O * log n is the total Overhead.

The STL templates help by providing assured O*n performance profiles for
their various operations.

--
Phlip
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!

[Jerry Coffin]

In article <11*********************@m73g2000cwd.googlegroups. com>,
pa**********@att.net says...

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Yes and no. In theory, I can see it for something like a text editor,
where you have a current line in the file, and want to be able to
insert/delete lines quickly wherever that current line happens to be.
The 'current line' mostly gets changed by cursor control keys: back one
line, forward one line, back one screen, forward one screen, to the
beginning of the file, or the end of the file. All of those are
reasonable with a linked list (though the forward/backward one screen is
still linear on the number of lines in a screen).

OTOH, I can barely remember the last time I used a linked list in real
code, and I'd put good odds that even then it wasn't really optimum. I
doubt I've ever written real code for which it was the optimum data
structure.

A linked list is constant for insertion and deletion anywhere in the
list, but linear to get to any spot in the list. If you have some sort
of collection that requires linear searching anyway, that's not a real
loss -- but this is rare, at least IME. If you usually maintain a
"current spot" in the list, that's fine too. The linear search usually
loses more than the constant insertion/deletion gains -- especially
since linked lists have relatively poor locality of reference, as a
rule.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Jerry Coffin]

In article <QC****************@newssvr12.news.prodigy.com>,
ph******@yahoo.com says...

pauldepstein wrote:

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Is this for a quiz? Use list when random inserts and deletes must take
constant (minimal) time.

In that case, a list doesn't work. A random insertion or deletion in a
list is linear, because you have to traverse list to the random spot
(linearly) before you can do the insertion or deletion.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[pauldepstein]

Phlip wrote:

Is this for a quiz?

No

[Howard]

<pa**********@att.netwrote in message
news:11*********************@m73g2000cwd.googlegro ups.com...

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Paul Epstein

Consider a waiting list for liver transplant patients. A queue sounds like
a good first choice: first in, first out. But consider this:

Suppose you need a liver transplant. You may get placed on the list
according to how soon you're likely to need the transplant, not just at the
end because you're the latest to apply. That requires inserting you in a
specific order with in the list, something a list is good for, because it
doesn't have to shuffle everyone behind you backwards in the line. You just
get inserted in the appropriate place.

Suppose someone else waiting for a transplant dies before getting a
transplant. They need to be removed from the list. Again, that's easy with
a list.

Neither operation is easy (or at least efficient) with a vector or deque.

You might also want to merge your waiting list with one from another region.
The list has a merge operation for that. Or ,you may want to re-sort the
list, according to new regulations regarding patient priority. Again, list
provides that ability.

Basically, any situation which would normally call for a doubly-linked list,
the list container is likely to fit the bill best. (Unless you've got a
whiz-bang third-party container which is suited even better, of course! :-))

-Howard

[Gianni Mariani]

pa**********@att.net wrote:

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Paul Epstein

One important property for list is that an iterator to a list element
remains valid for all insertion/deletion operations except for deleting
the element the iterator is pointing to. For a deque or a vector, any
insertions or deletions can invalidate all iterators.

[Jerry Coffin]

In article <wd*******************@bgtnsc05-news.ops.worldnet.att.net>,
al*****@hotmail.com says...

[ ... ]

Consider a waiting list for liver transplant patients. A queue sounds like
a good first choice: first in, first out. But consider this:

First of all, I'd argue with your basic premise. First of all, the
number of people in any given list for organ transplants (whether
hearts, livers, or whatever) is not likely to be large enough that
computation speed is likely to matter. Second, this sort of list tends
to be maintained over a matter of months or years so what you're
generally looking at is a database, not an in-memory data structure.

Even though I doubt any of the details really means much under the
specific circumstances, let's look at them for a moment anyway, in case
they were applied to different circumstances.

Suppose you need a liver transplant. You may get placed on the list
according to how soon you're likely to need the transplant, not just at the
end because you're the latest to apply. That requires inserting you in a
specific order with in the list, something a list is good for, because it
doesn't have to shuffle everyone behind you backwards in the line. You just
get inserted in the appropriate place.

All of these operations require that you find the right place in the
list before you can do the insertion or deletion -- and in a linked
list, that search will be linear.

Suppose someone else waiting for a transplant dies before getting a
transplant. They need to be removed from the list. Again, that's easy with
a list.

Maybe -- if the record for that person contains an iterator to the right
item in the list, it can be efficient. Otherwise it also requires a
(linear) search for the correct item in the list before the item can be
deleted.

Neither operation is easy (or at least efficient) with a vector or deque.

That depends on what you call "efficient". I'd agree that neither a
vector nor a deque is probably ideal for the situation, but they're
probably both going to be faster than a linked list anyway.

Under the circumstances, what you probably want is map, with the
priority as the key and a pointer to the patient's data as the
associated data. This allows your insertions and deletions to be
logarithmic instead of linear.

You might also want to merge your waiting list with one from another region.
The list has a merge operation for that. Or ,you may want to re-sort the
list, according to new regulations regarding patient priority. Again, list
provides that ability.

Both set and map allow merging to be done quickly as well. Changing
regulations takes long enough that optimizing for it is almost certain a
mistake. Nonetheless, it should be O(N lg N) for just about any data
structure you use.

Basically, any situation which would normally call for a doubly-linked list,
the list container is likely to fit the bill best. (Unless you've got a
whiz-bang third-party container which is suited even better, of course! :-))

Yes, but what situation does call for a doubly-linked list? So far, I've
seen few or none, and based on your example, I have to guess you haven't
either.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Gianni Mariani]

Jerry Coffin wrote:
....

>
Yes, but what situation does call for a doubly-linked list? So far, I've
seen few or none, and based on your example, I have to guess you haven't
either.

I have used list<>s for:

a) work queues - i.e. items of work that may be removed before being done.

b) message queues - i.e. a list of messages that need to be diced and
spliced.

c) client objects - i.e. each client of a service is an item in a list

[Marcus Kwok]

Jerry Coffin <jc*****@taeus.comwrote:

Under the circumstances, what you probably want is map, with the
priority as the key and a pointer to the patient's data as the
associated data.

There is also std::priority_queue which may have been a better choice
for this example.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply

[Jerry Coffin]

In article <ee**********@news-int2.gatech.edu>,
ri******@gehennom.invalid says...

Jerry Coffin <jc*****@taeus.comwrote:

Under the circumstances, what you probably want is map, with the
priority as the key and a pointer to the patient's data as the
associated data.

There is also std::priority_queue which may have been a better choice
for this example.

I thought of that, and for all but one point, it would be the clear
choice -- priority_queue doesn't (directly) support removal from the
middle of the list. You could still do it, but not particularly cleanly
-- since priority_queue is an adapter, usually instantiated over dequeue
or vector, you can still remove from the middle of the underlying
container, and then re-build the priority_queue. It's comparitively ugly
though...

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Jerry Coffin]

In article <450fd5b5$0$13674$5a62ac22@per-qv1-newsreader-
01.iinet.net.au>, gi*******@mariani.ws says...

Jerry Coffin wrote:
...

Yes, but what situation does call for a doubly-linked list? So far, I've
seen few or none, and based on your example, I have to guess you haven't
either.

I have used list<>s for:

a) work queues - i.e. items of work that may be removed before being done.

Okay this might be reasonable -- but I'm left wondering: do really
remove unfinished items often enough to optimize for that at the expense
of virtually everything else?

Most times I build something like this, it ends up holding pointers to
some sort of structure that describes each work item. In that case, it's
usually perfectly reasonable to simply set the pointer to NULL, and not
worry about removing it until it gets to the head of the queue (of
course, the structure it points at can be destroyed immediately).

b) message queues - i.e. a list of messages that need to be diced and
spliced.

c) client objects - i.e. each client of a service is an item in a list

Without a bit more information, it's hard to say with certainty, but
nothing in your description of either of these seems to give a strong
indication that a list would be particularly optimum for them either.
I'm not saying they _couldn't_ be, but I don't see anything in your
description to indicate that they actually are.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Jens Theisen]

pa**********@att.net writes:

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Mergesort can be implemented in-situ on lists, but not on deques and
vectors.

Not sure if this counts as a realistic example though.

Jens

[Thomas Tutone]

Gianni Mariani wrote:

pa**********@att.net wrote:

Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Paul Epstein

One important property for list is that an iterator to a list element
remains valid for all insertion/deletion operations except for deleting
the element the iterator is pointing to. For a deque or a vector, any
insertions or deletions can invalidate all iterators.

To me, this is perhaps the most compelling justification to use a list.
As is the case with iterators, pointers and references are also not
invalidated when inserting or deleting an inner element - in contrast
to vectors and deques.

Best regards,

Tom

[Kai-Uwe Bux]

Jens Theisen wrote:

pa**********@att.net writes:

>Can anyone give a realistic example of a task for which the list
container works better than vector or deque?

Mergesort can be implemented in-situ on lists, but not on deques and
vectors.

Not sure if this counts as a realistic example though.

It does. In fact, it generalizes quite a bit: with std::list<reordering
elements does not involve copying them around. That can translate into a
performance gain for objects that are costly to copy or move. [This is to
be taken with a grain of salt: many standard reordering procedures can be
expressed in terms of swap operations which usually can be implemented
efficiently even for big objects.]
Best

Kai-Uwe Bux