为什么Ranges库中的std :: views :: take_while需要一个const谓词? [英] Why does std::views::take_while from the Ranges library require a const predicate?

问题描述

TL; DR:我正在玩 ranges 和 std :: views :: take_while 和 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<<"值:"<<我<<std :: endl;} 

输出:

值:8
值:2

但是，我现在也要处理 5 ，因此循环必须再执行一个迭代步骤.我找不到合适的范围适配器，所以我写了以下有状态的lambda表达式:

  auto cond = [b = true](int i)可变{返回b?b =(i！= 5)，true:假;}; 

此lambda表达式可记住何时违反条件 i！= 5 并在下一次调用时返回 false .然后，我将其传递给 std :: views :: take_while 如下:

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

但是，对于上述代码，编译器会抛出长错误消息.由于无法发现问题，因此我仔细检查了 std的声明::views :: take_while ，发现谓词 Pred 必须为 const .寻找替代方案，我检查了 std :: views :: filter的声明 .有趣的是， Pred 不需要 成为 const .因此，我将上述可变的lambda传递给范围适配器 std :: views :: filter ，如下所示:

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

此代码编译并提供所需的输出:

值:8
值:2
值:5

Wandbox上的代码

这引出我一个问题:为什么 std :: views :: take_while 是一个 const 谓词，而 std :: views :: filter 不?

解决方案

为什么这是个坏主意

让我们生成一个可以编译并查看其实际功能的版本:

  struct MutablePredicate {可变布尔标志= true;自动运算符()(int i)const->布尔{如果(标志){标志=(i！= 5);返回true；} 别的 {返回false；}}};std :: vector< int>v = {8，2，5，6};自动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};自动r = v |std :: views :: take_while(MutablePredicate {});自动它= r.begin();它+ = 2;//这是5断言(它！= r.end());//不会触发，因为我们还没有结束断言(它== r.end());//不会触发，因为我们在最后?? 

这真是奇怪，使这种推理变得不可能.

为什么约束条件不同

C ++ 20中的范围适配器尝试通过围绕" 简单视图 "进行优化来最大程度地减少模板实例化的数量: V V 和 V const 都是具有相同迭代器/前哨类型的范围，则code>是 简单视图 .在这种情况下，适配器不同时提供 begin()和 begin()const ...，而它们只是提供后者(因为在这些情况下没有什么区别，并且 begin()const 始终有效，因此我们就可以做到).

我们的案例是 simple-view ，因为 ref_view< vector< int>> 仅提供 begin()const.无论我们是否将该类型迭代为 const ，我们仍然可以从中获得 vector< int> :: iterator .

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

filter_view 不是 const 可迭代的，因此不必考虑这一点.它只曾用作非常量，因此没有

 pred const 有意义地必须将其视为谓词.
您应该怎么做
因此，如果您实际上不需要惰性评估，我们可以急切地计算结束迭代器:
  auto e = std :: ranges :: find_if(v，[](int i){return i == 5;});如果(e！= v.end()){++ e;}自动r = std :: ranges :: subrange(v.begin()，e);//以某种方式使用r 
但是，如果您确实需要懒惰的评估，执行此操作的一种方法是创建自己的适配器.对于双向+范围，我们可以定义一个前哨值，以便与以下情况匹配迭代器:(a)它位于基础视图的基础的末尾，或者(b)它不在范围的开始，并且先前的迭代器与基础视图的相匹配结束.
类似的事情(仅适用于具有 .base()的视图，因为只有对 and_one 合适的范围才有意义):
 模板< std :: ranges :: bidirectional_range V>需要std :: ranges :: view< V>class and_one_view {V base_ = V();使用B = decltype(base_.base());哨兵班{朋友and_one_view;V * parent_ = nullptr;std :: ranges :: sentinel_t< V>结尾_;std :: ranges :: sentinel_t< B>base_end_;前哨(V * p):parent_(p)，end_(std :: ranges :: end(* parent_))，base_end_(std :: ranges :: end(parent _-> base())){}上市:sentinel()=默认值；自动运算符==(std :: ranges :: iterator_t< V>)const->布尔{返回它== base_end_ ||它！= std :: ranges :: begin(* parent_)&&std :: ranges :: prev(it)== end_;}};上市:and_one_view()=默认值；and_one_view(V b):base_(std :: move(b)){}自动begin()->std :: ranges :: iterator_t< V>{return std :: ranges :: begin(base_);}自动end()->sentinel {return sentinel(& base_);}}; 
出于演示目的，我们可以使用libstdc ++的内部对象进行管道传递:
  struct AndOne:std :: views :: __ adaptor :: __ RangeAdaptorClosure{模板< std :: ranges :: viewable_range R>需要std :: ranges :: bidirectional_range< R>constexpr auto operator()(R& r)const {return and_one_view< std :: views :: all_t< R>(std :: forward< r));}};内联constexpr AndOne and_one; 
现在，由于我们遵守所有库组件的所有语义约束，因此我们可以将适应范围用作范围:
  std :: vector< int>v = {8，2，5，6};自动r = v |std :: views :: take_while([](int i){return i！= 5;})|and_one;fmt :: print("First:{} \ n"，r);//打印{8，2，5}fmt :: print("Second:{} \ n"，r);//同时输出{8，2，5} 
 演示.
TL;DR: I'm playing around with ranges and the corresponding range adaptors from the Ranges library. Both range adaptors std::views::take_while and std::views::filter take a predicate to exclude certain elements from the input sequence. Why does take_while take a const predicate while filter does not?
Background story
I have an std::vector<int> and want to iterate over it, but I want to stop iterating when hitting a 5. By using the range adaptor std::views::take_while I can implement that as follows:
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;
}
Output:

Value: 8

Value: 2
However, I now want to process the 5 as well, so the loop must run one iteration step further. I didn't find a suitable range adaptor, so I wrote the following stateful lambda expression:
auto cond = [b = true](int i) mutable {
    return b ? b = (i != 5), true : false;
};
This lambda expression remembers when the condition i != 5 is violated and returns false on the next call. I then passed it to the std::views::take_while as follows:
for (int i : v | std::views::take_while(cond)) {
    std::cout << "Value: " << i << std::endl;
}
However, for the above code, the compiler throws a 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. Interestingly, Pred is not required to be const here. So I passed the above mutable lambda to the range adaptor std::views::filter as follows:
for (int i : v | std::views::filter(cond)) {
    std::cout << "Value: " << i << std::endl;
}
This code compiles and gives the desired output:

Value: 8

Value: 2

Value: 5
Code on Wandbox
This leads me to my question: Why does std::views::take_while a const predicate, while std::views::filter does not?
解决方案
Why this is a bad idea
Let's produce a version that compiles and see what it actually does:
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);
This prints {8, 2, 5} the first time, as desired. And then {} the second time. Because of course, we modified the predicate and so we get different behavior entirely. This completely breaks the semantics of this range (because your predicate fails to be equality-preserving), and all sorts of operations just totally fail as a result.
The resulting take_view is a random-access range. But just think about what happens when you use iterators into it:
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??
This is all sorts of weird and makes reasoning about this impossible.
Why the difference in constraints
The range adaptors in C++20 try to minimize the number of template instantiations by optimizing around "simple-view": V is a simple-view if both V and V const are ranges with the same iterator/sentinel types. For those cases, adaptors don't provide both begin() and begin() const... they just provide the latter (since there's no difference in these cases, and begin() const always works, so we just do it).
Our case is a simple-view, because ref_view<vector<int>> only provides begin() const. Whether we iterate that type as const or not, we still get vector<int>::iterators out of it.
As a result, take_while_view in order to support begin() const needs to require that Pred const is a unary predicate, not just Pred. Since Pred has to be equality-preserving anyway, it's simpler to just require that Pred const is a unary predicate rather than potentially supporting begin() /* non-const */ if only Pred but not Pred const is a unary predicate. That's just not an interesting case worth supporting.
filter_view is not const-iterable, so it doesn't have to this consideration. It's only ever used as non-const, so there's no Pred const that it ever meaningfully has to consider as being a predicate.
What you should do instead
So if you don't actually need lazy evaluation, we can eagerly calculate the end iterator:
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
But if you do need lazy evaluation, one way to do this is create your own adaptor. For a bidirectional+ range, we can define a sentinel such that we match the iterator if either (a) it's at the end of the underlying view's base or (b) it's not at the beginning of the range and the previous iterator matches the underlying view's end.
Something like this (will only work on views that have a .base() since it only makes sense to and_one an adapted range):
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_); }
};
which for the purposes of demonstration we can make pipeable with libstdc++'s internals:
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;
And now, because we adhere to all the semantic constraints of all the library components, we can just use the adapted range as a range:
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谓词?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！