ansaurus

Question

Answer 1

A:

Good explanantion of std::sort here
Although you could define your own vector class with it's own sort() algorithm it's generally more versatile to have the algorithms separate so they can operate on different containers.

Martin Beckett 2010-02-01 22:27:12

Answer 2

+15 A:

std::sort is a function template that works with any pair of random-access iterators. Consequently, the algorithm implemented by std::sort is tailored (optimized) for random access. Most of the time it is going to be some flavor of quick-sort.

std::list::sort is a dedicated list-oriented version of sort. std::list is a container that does not support [efficient] random access, which means that you can't use std::sort with it. This creates the need for a dedicated sorting algorithm. Most of the time it will be implemented as some flavor of merge-sort.

AndreyT 2010-02-01 22:28:41

only list has a sort? vector does not have?

skydoor 2010-02-01 22:34:09

`std::vector` doesn't have its own `sort`. `std::vector` is a random-access container, which means that `std::sort` will work perfectly fine with it.

AndreyT 2010-02-01 22:36:20

Interestingly, the fastest way to sort a list isn't actually to merge sort. In practice it's faster to copy the list into a vector, quicksort that, then copy it back. The reason for this is because of the added cache coherency of a vector.

Peter Alexander 2010-02-02 02:10:26

Note that `std::partition` is limited to N/2 swaps complexity even for bidirectional iterators. So you can implement a generic O(N log N) quicksort for all bidirectional iterators. Really, it's strange that `std::sort` isn't specialized for bidirectional iterators in lieu of `std::list::sort`.

Potatoswatter 2010-02-02 02:23:00

@Poita_: That's far from certain, and you mean spatial locality, not cache coherency.

Potatoswatter 2010-02-02 02:24:28

@Poita_: I'd say that this claim is rather questionable. For small containers it might not matter. For large ones the cache behavior of a vector might easily be as bad as that of the list. It actually depends more on the algorithm than on the data structure. And, of course, it depends on how the list is laid out in memory as well.

AndreyT 2010-02-02 02:27:08

@Potatoswatter: Linked list is sorted by relinking the nodes. So the algorithm needs to know more about the container than just have a pair of its bidirectional iterators. `std::sort` works by assigning data around between iterators. Having the same for std::list would be rather undesirable.

UncleBens 2010-02-02 08:09:27

@Uncle: yeah, I realized that after reading your answer :P

Potatoswatter 2010-02-02 10:50:08

@Uncle: although if `iter_swap` only took modifiable `iterator` references, you could implement any reordering algorithm on `list::iterator` without ever swapping values.

Potatoswatter 2010-02-03 19:36:30

How? As far as I know list::iterators don't allow public access to `__List_Node` objects (whatever they are called) which it encapsulates.

UncleBens 2010-02-03 20:11:12

Answer 3

+1 A:

std::list includes a sort() member, because there are ways to do sorting efficiently that work for lists, but almost nothing else. If you tried to use the same sorting implementation for a list as everything else, one of them wouldn't work very well, so they provide a special one for list.

Most of the time, you should use std::sort, and forget that std::list even exists. It's useful in a few very specific circumstances, but they're sufficiently rare that using it is a mistake at least 90% of the time that people think they should.

Edit: The situation is not that using std::list::sort is a mistake, but that using std::list is usually a mistake. There are a couple of reasons for this. First of all, std::list requires a couple of pointers in addition to space for each item you store, so unless your data is fairly large, it can impose a substantial space overhead. Second, since each node is allocated individually, traversing nodes tends to be fairly slow (locality of reference is low, so cache utilization tends to be poor). Finally, although you can insert or delete an element from the middle of a list with constant complexity, you (normally) need to use a linear-complexity traversal of the list to find the right point at which to insert or delete that item. Couple that with the poor cache utilization, and you get insertions and deletions in the middle of a linked list usually being slower than with something like a vector or deque.

The other 10% of the time (or maybe somewhat less than that) is when you can reasonably store a position in the list in the long term, and (at least typically) plan on making a number of insertions and deletions at (close to) that same point, without traversing the linked list each time to find the right place. If you make enough modifications to the list at (or close to) the same place, you can amortize the list traversal over a number of insertions and deletions. If you make enough modifications at (close to) the same place, you can come out ahead.

That can work out well in a few cases, but forces you to store more "state" data for a long period of time, mostly to make up for the deficiencies in the data structure itself. To the extent possible, I prefer to make individual operations close to pure and atomic, so they minimize dependence (and effect) on long-term data. In the single-threaded case, this mostly helped modularity, but with multi-core, multithreaded (etc.) programming, it can also have a substantial effect on efficiency and difficulty of development. Access to that long-term data generally requires thread synchronization.

That's not to say that avoiding list will automatically make your programs lots faster, or anything like that -- just that I find situations where it's really useful to be quite rare, and a lot of situations that seem to fit what people have been told about when a linked list will be useful, really aren't.

Jerry Coffin 2010-02-01 22:30:03

Could you elaborate on why using `std::list<T>::sort` is a mistake 90% of the time (especially if the other implementation "wouldn't work very well") and what the useful 10% cases are?

jamesdlin 2010-02-01 22:36:35

Generally I don't use std::list either, but - you can do multiple deletions during one traversal, you can do splicing with it, it doesn't move its data around if that is very expensive, it doesn't invalidate its iterators a lot etc.

UncleBens 2010-02-01 23:05:00

Answer 4

A:

std::sort only works with random-access iterators. That limits it to arrays, vector and deque (and user-defined types which provide random access).

std::list is a linked list which doesn't support random access. The generic sort function doesn't work for it. And even if it did, it would be suboptimal. A linked list is not sorted by copying data from node to node - it is sorted by relinking the nodes.

std::sort also wouldn't work for other containers (sets and maps), but those are always sorted anyway.

UncleBens 2010-02-01 22:59:19

ansaurus

tags:

views:

answers:

sort() function in C++

related questions