为什么标准将borrowed_subrange_t定义为common_range？

Question

C++20 引入了 ranges::borrowed_range，它定义了一个范围的要求，这样一个函数就可以通过值获取它，并且 return 从它获得的迭代器没有悬挂的危险。简而言之（其中参考P2017R1):

A range is a borrowed_range when you can hold onto its iterators after the range goes out of scope.

同时，还引入了类型助手borrowed_subrange_t：

template<ranges::range R>
using borrowed_subrange_t = std::conditional_t<
    ranges::borrowed_range<R>,
    ranges::subrange<ranges::iterator_t<R>>, 
    ranges::dangling
>;

这是一个别名模板，某些受约束的算法（例如 ranges::unique and ranges::find_end）使用它来避免 returning 潜在的悬空迭代器或视图。

当类型R模型borrowed_range时，R的borrowed_subrange_t基本上是subrange<ranges::iterator_t<R>>，这意味着它也是一个 ranges::common_range，因为它只接受一个模板参数，而第二个默认与第一个参数类型相同。

但是好像有些误导，因为有一些subrange类型可以借用但还是不行common_range，考虑下面的代码：

auto r = views::iota(0);
auto s1 = ranges::subrange{r.begin(),     r.begin() + 5};
auto s2 = ranges::subrange{r.begin() + 5, r.end()};

我从 borrowed_range ranges::iota_view 创建了两个 subrange，一个包含前 5 个元素，另一个包含从 itoa_view 开始的所有元素第五元素。它们是 itoa_view 的 subrange，它们显然是借来的：

static_assert(ranges::borrowed_range<decltype(s1)>);
static_assert(ranges::borrowed_range<decltype(s2)>);

所以从某种程度上来说，它们的两个类型都可以看作是itoa_view类型的borrowed_subrange_t，但是根据定义，只有s1的类型是borrowed_subrange_t 类型 r，这也意味着以下代码格式错误，因为 iota_view r 不是 common_range:

auto bsr = ranges::borrowed_subrange_t<decltype(r)>{r}; // ill-formed

为什么标准要保证rangeR的borrowed_subrange_t是common_range，即return类型的begin()和end()是一样的吗？这背后的原因是什么？为什么不更笼统地定义它：

template <ranges::range R>
using borrowed_subrange_t = std::conditional_t<
    ranges::borrowed_range<R>,
    ranges::subrange<
      ranges::iterator_t<R>, 
      std::common_iterator<
        ranges::iterator_t<R>,
        ranges::sentinel_t<R>
      >
    >,
    ranges::dangling
>;

这样做会不会有什么潜在的缺陷和危险？

Answer 1

Why does the standard need to ensure that borrowed_subrange_t of some range R is a common_range, that is, the return type of begin() and end() are the same?

并非所有子范围都以基础范围的标记值结束。

Will there be any potential defects and dangers in doing so?

如果底层范围是一个空类型，因为它是哨兵，所有子范围都将在哨兵处结束，而不是在他们想要的结束处。

Answer 2

引用 Alexander Stepanov 在“从数学到泛型编程”中的话：

When writing code, it’s often the case that you end up computing a value that the calling function doesn’t currently need. Later, however, this value may be important when the code is called in a different situation. In this situation, you should obey the law of useful return: A procedure should return all the potentially useful information it computed.

borrowed_subrange 用于必然遍历整个子范围的算法。所以我们必须计算这个范围的结束迭代器作为执行算法其余部分的副作用。这对用户有用，所以我们应该return它！

对于这些算法中的一些，实际上什至不可能 return 哨兵。例如，ranges::search 必须 return 匹配的子范围 - 但该子范围不必位于初始范围的末尾，因此 return 原始哨兵根本不是一个选项。

对于其他算法，它可能是 return 哨兵的一种选择，但这是一个糟糕的选择。考虑 unique。这里基本上就三种选择：

Return 只是迭代器 (I) 表示此范围的开始（如 std::unique 那样）
Return subrange<I, S>表示完整范围（即刚好通过提供的last）
Return subrange<I> 表示完整范围，包括计算的 I 参考 last.

但我们已经在做能够做到 (3) 的工作，所以这更有价值。没有理由做 (2)。

考虑一个不太抽象的案例，我们实际上有一个哨兵。比方说，我们有一个以 null 结尾的字符串：

struct null_terminated_string {
    char const* p;

    struct sentinel {
        auto operator==(char const* p) const { return *p == '[=10=]'; }
    };

    auto begin() const -> char const* { return p; }
    auto end() const -> sentinel { return {}; }
};

现在，unique 中的 return 哪个更有用：只返回此 null_terminated_string::sentinel 类型的类型或返回 char const* 类型的类型哪个指向空终止符？后者为您提供更多有用的信息（包括，例如，尺寸！）。

最后，这个：

template <ranges::range R>
using borrowed_subrange_t = std::conditional_t<
    ranges::borrowed_range<R>,
    ranges::subrange<
      ranges::iterator_t<R>, 
      std::common_iterator<
        ranges::iterator_t<R>,
        ranges::sentinel_t<R>
      >
    >,
    ranges::dangling
>;

没有意义，因为 common_iterator<iterator_t<R>, sentinel_t<R>> 不是 iterator_t<R> 的标记。应该是这样的：

template <ranges::range R>
using borrowed_subrange_t = std::conditional_t<
    ranges::borrowed_range<R>,
    ranges::subrange<ranges::iterator_t<R>, ranges::sentinel_t<R>>,
    ranges::dangling
>;

并且可能有意义。考虑 ranges::find。现在，它只是 return 一个 iterator_t<R>（或者，更准确地说，是一个 iterator_t<R> 或 dangling）。但是 ranges::find 的不同设计可以做一些不同的事情：它可以 return 从该迭代器开始的子范围并包括整个范围的其余部分（可以说这会更有用）。如果我们想要 ranges::find 这样做，我们 肯定会 想要 return 一个 subrange<iterator_t<R>, sentinel_t<R>>。在这种情况下，我们还没有遍历整个范围，也不想为此付出额外的代价；我们会简单地通过哨兵转发。

只是在<algorithm>中没有任何看起来像这样的算法，那些只是简单地return迭代器而不是子范围到最后的算法。如果我们有这样的算法，我们肯定会有一个使用 sentinel_t<R> 的 borrowed_subrange 版本。但是有了我们现有的算法，就不需要这样的东西了。

为什么标准将borrowed_subrange_t定义为common_range？

Why the standard defines borrowed_subrange_t as common_range?

c++

c++20

range-v3

std-ranges