为什么 Ranges 库中的 std::views::take_while 需要一个 const 谓词？

Question

TL;DR: 我在玩 ranges 和相应的 range 适配器 从 Ranges library. Both range adaptors std::views::take_while and std::views::filter 中获取谓词以从输入序列中排除某些元素。为什么 take_while 采用 const 谓词而 filter 不采用？

背景故事

我有一个 std::vector<int> 并想迭代它，但我想在点击 5 时停止迭代。通过使用范围适配器 std::views::take_while 我可以实现如下：

std::vector<int> v { 8, 2, 5, 6 };

for (int i : v | std::views::take_while([](int i) { return i != 5; })) {
    std::cout << "Value: " << i << std::endl;
}

输出：

Value: 8
Value: 2

但是，我现在也想处理 5，因此循环必须运行进一步迭代一步。我没有找到合适的范围适配器，所以我写了以下有状态的 lambda 表达式：

auto cond = [b = true](int i) mutable {
    return b ? b = (i != 5), true : false;
};

此 lambda 表达式会记住何时违反条件 i != 5，并在下一次调用时记住 returns false。然后我将它传递给 std::views::take_while 如下：

for (int i : v | std::views::take_while(cond)) {
    std::cout << "Value: " << i << std::endl;
}

但是，对于上面的代码，编译器会抛出一个long error message. Since I couldn't spot the problem, I closely inspected the declaration of std::views::take_while and found that the predicate Pred must be const. Looking for an alternative, I checked the declaration of std::views::filter。有趣的是，Pred 在这里 而不是 必须是 const。所以我将上面的可变 lambda 传递给范围适配器 std::views::filter，如下所示：

for (int i : v | std::views::filter(cond)) {
    std::cout << "Value: " << i << std::endl;
}

此代码编译并给出所需的输出：

Value: 8
Value: 2
Value: 5

Code on Wandbox

这引出了我的问题：为什么 std::views::take_while 是 const 谓词，而 std::views::filter 不是？

Answer 1

一个std::indirect_unary_predicate要求是一个std::predicate，要求是a std::regular_invocable。需要：

The invoke function call expression shall be equality-preserving ([concepts.equality]) and shall not modify the function object or the arguments.

您的 lambda 不是“保持相等”，因为相同的输入可以产生不同的输出，并且它肯定会修改函数对象。由于你的类型不满足概念的非句法条件，你的代码有UB。

所以真的，一个是 const 而另一个不是并不重要；这些概念有效地要求他们表现得像 const.

Answer 2

为什么这是个坏主意

让我们生成一个可以编译的版本，看看它实际做了什么：

struct MutablePredicate {
    mutable bool flag = true;

    auto operator()(int i) const -> bool {
        if (flag) {
            flag = (i != 5);
            return true;
        } else {
            return false;
        }
    }
};

std::vector<int> v = {8, 2, 5, 6};
auto r = v | std::views::take_while(MutablePredicate{});

fmt::print("First: {}\n", r);
fmt::print("Second: {}\n", r);

这会根据需要第一次打印 {8, 2, 5}。然后 {} 第二次。当然，因为我们修改了谓词，所以我们得到了完全不同的行为。这完全打破了这个范围的语义（因为你的谓词不能保持相等），结果所有类型的操作都完全失败。

生成的 take_view 是一个随机访问范围。但是想想当你使用迭代器时会发生什么：

std::vector<int> v = {8, 2, 5, 6};
auto r = v | std::views::take_while(MutablePredicate{});

auto it = r.begin();
it += 2;                // this is the 5
assert(it != r.end());  // does not fire, because we're not at the end
assert(it == r.end());  // does not fire, because we're at the end??

这太奇怪了，无法推理。

为什么约束不同

C++20 中的范围适配器尝试通过围绕“simple-view”进行优化来最小化模板实例化的数量：V 是一个 simple-view 如果 V 和 V const 都是具有相同 iterator/sentinel 类型的范围。对于这些情况，适配器不提供 begin() 和 begin() const...它们只是提供后者（因为在这些情况下没有区别，并且 begin() const总是有效，所以我们就这样做了）。

我们的案例是simple-view，因为ref_view<vector<int>>只提供了begin() const。无论我们是否将该类型迭代为 const，我们仍然会从中得到 vector<int>::iterators。

因此，take_while_view 为了支持 begin() const 需要要求 Pred const 是一元谓词，而不仅仅是 Pred。由于 Pred 无论如何都必须保持相等性，因此仅要求 Pred const 是一元谓词而不是可能支持 begin() /* non-const */ if only 更简单Pred 但不是 Pred const 是一元谓词。这不是一个值得支持的有趣案例。

filter_view 不是 const-iterable，所以不必考虑这个。它仅用作非 const，因此没有 Pred const 必须有意义地考虑为谓词。

你应该怎么做

所以如果你实际上不需要惰性计算，我们可以急切地计算结束迭代器：

auto e = std::ranges::find_if(v, [](int i){ return i == 5; });
if (e != v.end()) {
    ++e;
}
auto r = std::ranges::subrange(v.begin(), e);
// use r somehow

但是如果您确实需要惰性求值，一种方法是创建您自己的适配器。对于双向+范围，我们可以定义一个哨兵，这样我们就可以匹配迭代器，如果（a）它位于基础视图基的末尾或（b）它不在范围的开头并且前一个迭代器匹配基础视图的结束。

类似这样的东西（仅适用于具有 .base() 的视图，因为它仅对 and_one 适应范围有意义）：

template <std::ranges::bidirectional_range V>
    requires std::ranges::view<V>
class and_one_view {
    V base_ = V();
    using B = decltype(base_.base());

    class sentinel {
        friend and_one_view;
        V* parent_ = nullptr;
        std::ranges::sentinel_t<V> end_;
        std::ranges::sentinel_t<B> base_end_;

        sentinel(V* p)
            : parent_(p)
            , end_(std::ranges::end(*parent_))
            , base_end_(std::ranges::end(parent_->base()))
        { }
    public:
        sentinel() = default;
        auto operator==(std::ranges::iterator_t<V> it) const -> bool {
            return it == base_end_ ||
                it != std::ranges::begin(*parent_) && std::ranges::prev(it) == end_;
        }
    };
public:
    and_one_view() = default;
    and_one_view(V b) : base_(std::move(b)) { }

    auto begin() -> std::ranges::iterator_t<V> { return std::ranges::begin(base_); }
    auto end() -> sentinel { return sentinel(&base_); }
};

出于演示的目的，我们可以使用 libstdc++ 的内部结构进行管道化：

struct AndOne : std::views::__adaptor::_RangeAdaptorClosure
{
    template <std::ranges::viewable_range R>
        requires std::ranges::bidirectional_range<R>
    constexpr auto operator()(R&& r) const {
        return and_one_view<std::views::all_t<R>>(std::forward<R>(r));
    }
};
inline constexpr AndOne and_one;

现在，因为我们遵守所有库组件的所有语义约束，我们可以只使用适应范围作为范围：

std::vector<int> v = {8, 2, 5, 6};
auto r = v | std::views::take_while([](int i){ return i != 5; })
           | and_one;

fmt::print("First: {}\n", r);   // prints {8, 2, 5}
fmt::print("Second: {}\n", r);  // prints {8, 2, 5} as well

Demo.

为什么 Ranges 库中的 std::views::take_while 需要一个 const 谓词？

Why does std::views::take_while from the Ranges library require a const predicate?

c++

predicate

c++20

std-ranges

背景故事

为什么这是个坏主意

为什么约束不同

你应该怎么做