Why does vector not have sort() method as a member function of vector, while list does?

Question

There is a sort() method for lists in STL. Which is absurd, because I would be more inclined to sort an array/vector. Why isn't sort() provided for vector? Is there some underlying philosophy behind the creation of the vector container or its usage, that sort is not provided for it?

Answer 1

As has already been said, the standard library provides a nonmember function template that can sort any range given a pair of random access iterators.

It would be entirely redundant to have a member function to sort a vector. The following would have the same meaning:

std::sort(v.begin(), v.end());
v.sort();

One of the first principles of the STL is that algorithms are not coupled to containers. How data is stored and how data is manipulated should be as loosely coupled as possible.

Iterators are used as the interface between containers (which store data) and algorithms (which operate on the data). In this way, you can write an algorithm once and it can operate on containers of various types, and if you write a new container, the existing generic algorithms can be used to manipulate its contents.

The reason that std::list provides its own sort function as a member function is that it is not a random accessible container; it only provides bidirectional iterators (since it is intended to represent a doubly linked list, this makes sense). The generic std::sort function requires random access iterators, so you cannot use it with a std::list. std::list provides its own sort function in order that it can be sorted.

In general, there are two cases in which a container should implement an algorithm:

• If the generic algorithm cannot operate on the container, but there is a different, container-specific algorithm that can provide the same functionality, as is the case with std::list::sort.

• If the container can provide a specific implementation of the algorithm that is more efficient than the generic algorithm, as is the case with std::map::find, which allows an element to be found in the map in logarithmic time (the generic std::find algorithm performs a linear search because it cannot assume the range is sorted).