424,986 Members | 2,030 Online
Need help? Post your question and get tips & solutions from a community of 424,986 IT Pros & Developers. It's quick & easy.

# when list is best

 P: n/a Can anyone give a realistic example of a task for which the list container works better than vector or deque? Paul Epstein Sep 18 '06 #1
16 Replies

 P: n/a 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!!! Sep 18 '06 #2

 P: n/a 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 Sep 18 '06 #3

 P: n/a 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!!! Sep 18 '06 #4

 P: n/a 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. Sep 18 '06 #5

 P: n/a In article , 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. Sep 18 '06 #6

 P: n/a Phlip wrote: Is this for a quiz? No Sep 18 '06 #7

 P: n/a

 P: n/a 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. Sep 18 '06 #9

 P: n/a In article , 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. Sep 18 '06 #10

 P: n/a 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 Sep 19 '06 #11

 P: n/a Jerry Coffin

 P: n/a In article , ri******@gehennom.invalid says... Jerry Coffin

 P: n/a 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. Sep 19 '06 #14

 P: n/a 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 Sep 19 '06 #15

 P: n/a 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 Sep 19 '06 #16

 P: n/a Jens Theisen wrote: pa**********@att.net writes: >Can anyone give a realistic example of a task for which the listcontainer 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

### This discussion thread is closed

Replies have been disabled for this discussion.