P
pauldepstein
Can anyone give a realistic example of a task for which the list
container works better than vector or deque?
Paul Epstein
container works better than vector or deque?
Paul Epstein
P
Phlip
pauldepstein said:
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.
T
Thomas Tutone
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
P
Phlip
Thomas said:
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.
J
Jerry Coffin
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.
J
Jerry Coffin
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.
P
pauldepstein
Phlip said:
No
H
Howard
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
G
Gianni Mariani
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.
J
Jerry Coffin
[ ... ]
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
G
Gianni Mariani
Jerry Coffin wrote:
....
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
....
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
M
Marcus Kwok
Jerry Coffin said:
There is also std:
riority_queue which may have been a better choicefor this example.
J
Jerry Coffin
There is also std:
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...
J
Jerry Coffin
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).
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.
J
Jens Theisen
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
T
Thomas Tutone
Gianni said:
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
K
Kai-Uwe Bux
Jens said:
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