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

Question

Possible duplicate:
Sort list using stl sort function

The C ++ standard library provides a strict linear sequence container, a linear sequence container, an associative container.

std::sort() is available for all kinds of containers. But why only does it provide sorting of the list. std::list::sort() ?

Answer 1

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

std::sort , of course, does not work on associative containers, as you seem to think. What is the point of doing this? Access to associative containers is carried out by the value of their key, and not by position.

As Mike noted, C ++ 11 also has std::forward_list , which is no coincidence that also has its own sorting function.

Answer 2

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

Similarly, you cannot use the std::map or std::set iterators with std::sort . But for this you do not need it, since they are always sorted.

As a side note, there is also std::map::find and the like. This is really not required since you can use all iterators with std::find . But functional versions of members provide optimized algorithms for individual containers, which are more efficient than std::find linear complexity.