9

C++20 引入了一个std::common_iterator能够将非公共元素范围（迭代器和哨兵的类型不同）表示为公共范围（它们相同）的元素，其概要定义为：

template<input_­or_­output_­iterator I, sentinel_­for<I> S>
    requires (!same_­as<I, S> && copyable<I>)
class common_iterator {
  // ...
 private:
  variant<I, S> v_;   // exposition only
};

它对于与期望范围的开始和结束具有相同类型的遗留代码交互很有用。

在[iterators.common#common.iter.types-1.1]中，其iterator_­concept定义为：

iterator_­concept表示forward_­iterator_­tag如果I模型 forward_­iterator；否则表示input_­iterator_­tag。

为什么common_iterator最多只能是 a forward_iterator，而不能完全iterator_concept基于I's来定义它iterator_category？例如，如果I是random_asscess_iterator，那么common_iterator<I, S>是random_asscess_iterator，等等。

似乎这在技术上是可行的，因为common_iterator仅用于std::variant键入擦除I和S.

考虑以下（godbolt）：

auto r = views::iota(0) | std::views::take(5);
static_assert( ranges::random_access_range<decltype(r)>);

auto cr = r | views::common;
static_assert(!ranges::random_access_range<decltype(cr)>);
static_assert( ranges::forward_range<decltype(cr)>);

r是random_access_range，所以 C++20 约束算法比如ranges::binary_search可以使用这个 trait 对其执行更高效的操作，但是为了使旧std算法能够应用它，我们需要使用views::common将它转换为common_range. 但是，它也会退化为 a forward_range，这会降低算法的效率。

为什么标准最多只定义common_iterator为forward_iterator？这背后的考虑是什么？

4

3 回答 3

6

如果你有一个非常规范围的迭代器，并且你需要将它转换成一个公共范围，那么你基本上有两种选择。

您可以通过连续递增开始迭代器直到它等于哨兵来计算结束迭代器的值，或者您可以做一些诡计。common_iterator是为后者。

这很重要，因为连续递增开始迭代器有两个缺陷。首先，如果它至少不是一个向前的范围，你就不能这样做。第二......如果范围是无限的会发生什么？因为那是 C++20 范围内的事情。事实上，这种可能性是我们拥有哨兵类型的最重要原因之一。

那么诡计多端。然而，在这种情况下，“诡计”意味着创建一个新的迭代器类型，用于开始和哨兵。因此，它必须具有这两个方面的局限性。哨兵基本上必须假装它是一个迭代器。

迭代器可以递增；哨兵不能。但是，无论如何，您都不允许增加范围的结束迭代器，因此您可以假装允许增加结束common_iterator。同样，您不能取消引用哨兵，但也不能取消引用结束迭代器。所以它可以假装它可以被取消引用，即使没有算法会这样做。

这意味着对于前向范围，除了针对其他迭​​代器测试结束迭代器之外，您不能做任何事情。简而言之，对于前向范围，结束迭代器也可以是哨兵。

但对于更高级别的范围，情况并非如此。明确允许采用双向范围的算法向后移动结束迭代器。但是你不能对假装它是迭代器的哨兵这样做。

这就是为什么common_iterator范围不能高于前向范围的原因。

于 2021-05-15T14:07:53.493 回答
4

正如@daves 提到的，结束迭代器是一个迭代器。

如果您的迭代器支持--（就像所有比 forward 更强大的东西），那么您的通用迭代器必须能够--从包装的哨兵中获取。

哨兵不支持--；你会以某种方式伪造它。在许多情况下，这需要 O(n) 的工作；基本上扫描哨兵并将其变成迭代器。这太糟糕了。

于 2021-05-15T13:58:25.800 回答
1

哨兵的概念与其他语言中已知的迭代器密切相关，它支持推进和测试您是否到达终点。一个很好的例子是一个以零结尾的字符串，当您到达时您会停下来\0但事先不知道大小。

我的假设是，std::forward_iterator对于需要将 C++20 迭代器与哨兵转换以调用旧算法的用例，将其建模为 a 就足够了。

我还认为应该有可能提供一个通用实现来检测迭代器提供更多功能的情况。它会使标准库中的实现复杂化，也许这是反对它的论点。在通用代码中，您仍然可以自己检测特殊情况以避免包装随机访问迭代器。

但据我了解，如果您处理性能关键代码部分，则应小心将所有内容包装为 a std::common_iterator，除非需要。variant如果底层引入了一些开销，我不会感到惊讶。

于 2021-05-15T13:02:46.017 回答