为什么std::common_iterator只是std::forward_iterator?
C++20 引入了std::common_iterator能够将元素的非公共范围(迭代器和哨兵的类型不同)表示为公共范围(它们相同)的 a ,其概要定义为:
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)>);
ris random_access_range,所以 C++20 等约束算法ranges::binary_search可以使用这个 trait 对其执行更高效的操作,但是为了让旧std算法能够应用它,我们需要使用views::common将其转换为common_range. 但是,它也退化为 a forward_range,从而降低了算法的效率。
为什么标准只定义common_iterator为forward_iterator最多?这背后有何考虑?
回答
如果您有一个非通用范围的迭代器,并且需要将其转换为通用范围,那么您基本上有两种选择。
您可以通过连续递增开始迭代器直到它等于哨兵来计算结束迭代器是什么,或者您可以做一些技巧。common_iterator是为后者。
这很重要,因为连续递增开始迭代器有两个缺陷。首先,如果它不是至少一个前锋范围,你就不能这样做。其次......如果范围是无限的会发生什么?因为那是 C++20 范围内的事情。事实上,这种可能性是我们拥有哨兵类型的最重要原因之一。
那么诡计多端。然而,在这种情况下,“诡计”意味着创建一个新的迭代器类型,用于开始和哨兵。因此,它必须同时具有这两者的局限性。哨兵基本上必须假装它是一个迭代器。
迭代器可以递增;哨兵不能。但是,无论如何都不允许增加范围的结束迭代器,因此您可以假装common_iterator允许增加结束。同样,您不能取消引用哨兵,但也不能取消引用结束迭代器。所以它可以假装它可以被取消引用,即使没有算法会这样做。
这意味着对于前向范围,除了针对某个其他迭代器测试结束迭代器之外,您不能做任何事情。简而言之,对于前向范围,结束迭代器也可能是一个哨兵。
但对于更高级别的范围,情况并非如此。明确允许采用双向范围的算法将结束迭代器向后移动。但是你不能对假装它是迭代器的哨兵这样做。
这就是为什么common_iterator范围不能高于前向范围的原因。