why only std::list::sort()?

Question

Possible Duplicate:
Sort list using stl sort function

The C++ standard library gives strict linear sequence container, linear sequence container, associative container.

std::sort() is available for all kinds of containers. But why only it provides sort for list. std::list::sort()?

presumably because there can be a more optimal implementation that can utilise implementation details of list - which may not be available to the general sort function — Nim, Nov 03 '11 at 14:00
An explanation is given [here](http://stackoverflow.com/questions/2432857/sort-list-using-stl-sort-function). — Vlad, Nov 03 '11 at 14:02

Benjamin Lindley · Accepted Answer · 2011-11-03T14:10:35.617

13

std::sort only works on random access containers. And the only non-random access container in the standard library that it makes sense to sort is std::list.

std::sort certainly doesn't work on associative containers as you seem to think. What sense would that make? Associative containers are accessed by the value of their key, not by position.

As noted by Mike, C++11 also has std::forward_list, which, by no accident, also has it's own sort function.

edited Nov 03 '11 at 14:10

answered Nov 03 '11 at 14:03

Benjamin Lindley

101,917
9
204
274

Also `std::forward_list` these days. – Mike Seymour Nov 03 '11 at 14:10
Also note that the complexity guarantees are different for list sort and standard sort. – Kerrek SB Nov 03 '11 at 14:27
@KerrekSB: as per C++11 both are O(N log N). – Yakov Galka May 18 '12 at 12:49
1

@ybungalobill: Yes, you're right. The key difference is that `std::sort` reassigns elements, while `std::list::sort` moves *nodes* around without touching their values. – Kerrek SB May 18 '12 at 15:59

Christian Rau · Answer 2 · 2011-11-03T14:19:43.647

std::sort only works for random access iterators, but a std::list only provides biderectional iterators. Since it therefore cannot be used with std::sort, it needs its own implementation, which is also likely to be more optimized for a doubly linked list.

Likewise you cannot use std::map or std::set iterators with std::sort. But for these you don't need it anyway, as they are always sorted.

As a side note, there are also std::map::find and the like. These are indeed not required, as you can use all iterators with std::find. But the member function versions provide optimized algorithms for the individual containers, which are more efficient than std::find's linear complexity.

why only std::list::sort()?

2 Answers2

Related