为什么 std::list<int> 不可排序？

Question

我正在阅读一篇关于 C++ 概念（即 C++20，即印刷版）的文章。

文章给出了函数模板的例子，使用了Sortable概念：

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

它声称编译器会拒绝以下代码：

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

错误如：

ERROR: lst is not random-access container with <

假设这篇文章是正确的 - 为什么 list 的 int 值不能排序？对我来说，整数列表就像思考某事时的典型例子 "sortable"?!

不，我不是在问 std::sort。我在问：为什么概念可排序不适用于 std::list<int>？

Answer 1

std::list 大部分是 doubly-linked list。所以它显然不是随机访问的：访问第 n^th 元素需要 O(n) 线性时间（不是常数，即 O(1)).

std::vector是随机访问的；访问第 n^th 个元素需要常数时间。所以它有一个随机访问迭代器。

This 是一个相关问题。

Answer 2

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

好吧，这完全取决于如何定义概念 Sortable。因此，在您正在阅读的文本的上下文中，可能假设 Sortable 容器必须在随机访问迭代器上运行——例如 std::sort 需要一对随机访问迭代器；它不能对容器元素进行排序，比如 std::list，它不支持随机访问迭代器。

但是，这 not 意味着您不能定义自己的概念，比如 FlexySortable（连同算法 flexy_sort) 也可以在 non-random-access-iterator 上运行。文本只是给出一个一个概念的例子来解释关于概念如何可能的一般想法帮助您直接在代码中表达您的意图和假设，编译器可以通过执行谓词（即概念）来验证这些代码。

Answer 3

Sortable 概念未在语言中定义；你必须自己定义它。大概是在本章前面定义的吧？

注意 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，它只需要 ForwardIterators。

为什么 std::list<int> 不可排序？

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

c++

list

c++-concepts

c++20