Why is a std::list<int> not sortable?

Question

I am just reading a (printed, German) article about C++ concepts (C++20 that is).

The article gives an example for a function template, using the Sortable concept:

template<typename Cont>
  requires Sortable<Cont>()
void sort(Cont& container) { ... }

And it claims that a compiler would reject the following code:

std::list<int> lst = { 1, 7, 5, 12 };
sort(lst);

with an error like:

ERROR: lst is not random-access container with <

Assuming that the article is correct - why exactly is a list of int values not sortable? To me, a list of whole numbers is like the canonical example when thinking about something "sortable"?!

And no, I am not asking about std::sort. I am asking: why does the concept Sortable not work for a std::list<int>?

Answer 1

And no, I am not asking about std::sort. I am asking: why does the concept Sortable not work for a std::list?

Well, it all depends on how you define the concept Sortable. So in the context of the text which you're reading, it is probably assuming that the Sortable container must operate on random-access-iterator — std::sort for example takes a pair of random-access-iterators; it cannot sort elements of container, say std::list, which doesn't support random-access-iterator.

However, that does not mean that you cannot define your own concept, say FlexySortable (along with an algorithm flexy_sort) that may operate on non-random-access-iterator as well. The text is simply giving an example of a concept to explain the general idea as to how concepts may help you to express your intent and your assumptions directly in the code which the compiler can verify by executing predicates (i.e the concepts).

Answer 2

std::list is mostly a doubly-linked list. So it obviously is not randomly accessible: accessing the n^th element requires O(n) linear time (not constant, i.e. O(1)).

std::vector is randomly accessible; accessing the n^th element requires constant time. So it has a random-access-iterator.

This is a related question.