7

我只是在阅读一篇关于 C++ 概念（即 C++20）的（印刷的，德语的）文章。

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

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

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

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

出现如下错误：

错误：lst 不是带有 < 的随机访问容器

假设这篇文章是正确的 - 为什么int值列表究竟是不可排序的？对我来说，整数列表就像考虑“可排序”事物时的典型示例？！

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

4

3 回答 3

7

不，我不是在问std::sort。我在问：为什么 Sortable 的概念不适用于 std::list？

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

但是，这并不意味着您不能定义自己的概念，比如FlexySortable（以及算法flexy_sort）也可以在非随机访问迭代器上运行。文本只是给出一个概念的例子来解释概念如何帮助您直接在代码中表达您的意图和假设的一般概念，编译器可以通过执行谓词（即概念）来验证这些代码。

于 2017-11-22T20:13:42.463 回答
3

std::list主要是一个双向链表。所以它显然不是随机访问的：访问第 n个元素需要 O(n) 线性时间（不是恒定的，即 O(1)）。

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

这是一个相关的问题。

于 2017-11-22T20:11:55.263 回答
2

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

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.

于 2017-11-22T20:26:51.020 回答