8

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>?

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • @DylanLawrence Are you sure? I am **not** asking about std::sort. But a **self defined** sort! – GhostCat Nov 22 '17 at 20:02
  • @GhostCat then it doesn't make sense unless the self defined sort was written in such a way as to require random iterators, in which case it's just a special case of why `std::sort` fails. – Dylan Lawrence Nov 22 '17 at 20:04
  • I've never seen `requires` before, and I just looked it up. It's C++20 feature? – realharry Nov 22 '17 at 20:05
  • 1
    @realharry it's part of the much anticipated concepts. Finger crossed it makes C++20. – bolov Nov 22 '17 at 20:06
  • 1
    @realharry I updated my question accordingly. Yes, C++20. – GhostCat Nov 22 '17 at 20:07
  • @DylanLawrence I do not follow you. The function uses the `Sortable` concept. I am asking why this concept doesn't apply to a list of int. I really don't see how that duplicated question is answering that. – GhostCat Nov 22 '17 at 20:08
  • 1
    @bolov It’s been merged into C++20, but I suppose they could un-merge it. – Daniel H Nov 22 '17 at 20:20
  • I'm with op on this one - Q: "Does `std::sort` work on `list`?" A: "No as it would be ineffiecient.". Q: Is a `list` _sortable_? A: It most definitely is. – Mike Vine Nov 22 '17 at 20:21
  • 1
    Note that the most recent Ranges TS draft (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4685.pdf) defines `Sortable` to only require forward iterators. – Sebastian Redl Nov 22 '17 at 20:26
  • 1
    @Rakete1111 although similar, this question deals with **c++20 concepts**, so I feel it is not a duplicate – bolov Nov 22 '17 at 21:18
  • @Rakete1111, *as the author and others point out*, this question is about concepts, and definitely not about `std::sort`. It’s possible, *but irrelevant to the question*, that the `sort` function defined in the article the OP was reading requires random-access iterators or is implemented by calling `std::sort`. But it is not `std::sort`, and there are sorting algorithms which work on non-random-access iterators. – Daniel H Nov 22 '17 at 21:24
  • @bolov But it's a bit like the same thing. This deals with the fact that `std::list` doesn't meet the requirements for `Sortable`, which is also how `std::sort` requires its range to be. The answer in both is "Sortable requires random access iterators, which std::list doesn't have". – Rakete1111 Nov 22 '17 at 21:26
  • 1
    @Rakete1111 more or less. Maybe more. But see Nawaz answer. It deals with defining your own concept, something which doesn't apply to the other questions. – bolov Nov 22 '17 at 21:59

3 Answers3

7

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).

Nawaz
  • 353,942
  • 115
  • 666
  • 851
3

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

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

This is a related question.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • This isn’t a question about `RandomAccessIterator` vs. `ForwardIterator` vs. `BidirectionalIterator`. It’s more related to the question you linked, but that’s still somewhat different. – Daniel H Nov 22 '17 at 21:20
2

The Sortable concept is not defined in the language; you must define it yourself. Presumably it was defined earlier in the chapter?

Note that the Ranges TS, which unlike concepts is not yet part of C++2a, defines a Sortable concept. The only requirement that places on the iterators is from Permutable, which only requires ForwardIterators.

Daniel H
  • 7,223
  • 2
  • 26
  • 41
  • Also helpful. No, the article just started using that concept, without giving any further details. Thus I assumed that *Sortable* is a common "standard" thing. – GhostCat Nov 22 '17 at 20:48
  • @GhostCat, when was the article written? The Ranges TS has been through a bunch of changes, and it’s plausible that an earlier version of `Sortable` did require a random access iterator. – Daniel H Nov 22 '17 at 21:21
  • This article is printed in the iX magazine - December issue. So it is brand new. – GhostCat Nov 23 '17 at 04:47
  • @GhostCat Then I have no idea. It's been that way for at least a year (it looks like it's probably longer, but I don't like GitHub's blame interface enough to find a specific change which might not exist) according to the Git history of https://github.com/ericniebler/stl2/blob/master/iterators.tex. – Daniel H Nov 23 '17 at 05:08
  • That's not the full story; the RAI requirement got pinned to `sort` itself (and friends) instead. – T.C. Nov 23 '17 at 09:12