c++ - 为什么标准将 borrowed_subrange_t 定义为 common_range？

Question

C++20 引入了 ranges::borrowed_range ，它定义了一个范围的要求，这样一个函数可以按值获取它并返回从它获得的迭代器而没有悬空的危险。简而言之(其中引用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 和 ranges::find_end 以避免返回可能悬空的迭代器或 View 。

当输入 R 时型号 borrowed_range , borrowed_subrange_t的 R基本上是一个 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()};

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

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

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

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

为什么标准需要确保borrowed_subrange_t一些range R是 common_range , 即 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

引用 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用于必然遍历整个子范围的算法。所以我们必须计算这个范围的结束迭代器作为执行算法其余部分的副作用。这对用户有用，所以我们应该归还它!

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

对于其他算法，返回哨兵可能是一种选择，但这是一个糟糕的选择。考虑 unique .这里基本上有三个选择:

1. 仅返回指示此范围开始的迭代器 ( I )(与 std::unique 一样)
2. 返回subrange<I, S>表示完整范围(即仅通过提供的 last )
3. 返回subrange<I>表示整个范围，包括计算的 I引用last .

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

---

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

struct null_terminated_string {
    char const* p;

    struct sentinel {
        auto operator==(char const* p) const { return *p == '\0'; }
    };

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

现在，从 unique 返回什么更有用？ : 一个只会给你这个 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 .现在，它只返回一个 iterator_t<R>。 (或者，更准确地说，是 iterator_t<R> 或 dangling )。但是不同的设计 ranges::find可以做一些不同的事情:它可以返回一个从该迭代器开始的子范围，并包括整个范围的其余部分(可以说这会更有用)。如果我们想为 ranges::find 这样做，我们肯定想要返回一个 subrange<iterator_t<R>, sentinel_t<R>> .在这种情况下，我们还没有遍历整个范围，也不想为此付出额外的代价；我们会简单地通过哨兵转发。

只是在<algorithm>中没有类似这样的算法。 ，那些做的只是返回迭代器而不是子范围到最后。如果我们有这样的算法，我们肯定会有一个版本 borrowed_subrange使用 sentinel_t<R> .但是有了我们现有的算法，就不需要这样的东西了。