5

TL;DR：我正在使用Ranges库中的范围和相应的范围适配器。范围适配器和谓词都从输入序列中排除某些元素。为什么带谓词而不带谓词？std::views::take_whilestd::views::filtertake_whileconstfilter

背景故事

我有一个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;
}

输出：

值：8
值：2

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

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

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

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

但是，对于上面的代码，编译器会抛出一个很长的错误消息。由于无法发现问题，我仔细检查了 of 的声明，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 << "Value: " << i << std::endl;
}

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

值：8
值：2
值：5

魔杖盒上的代码

这引出了我的问题：为什么谓词std::views::take_while有，而没有？conststd::views::filter

4

2 回答 2

4

为什么这是一个坏主意

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

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-viewVV constbegin()begin() constbegin() const

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

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

filter_view是不可const迭代的，因此不必考虑这个问题。它只用作非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) 它不在范围的开头并且前一个迭代器匹配底层视图的结尾。

像这样的东西（只适用于具有 a 的视图，因为它只对适应的范围.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

演示。

于 2021-04-09T16:28:58.223 回答
1

Astd::indirect_unary_predicate必须是 a std::predicate，它必须是astd::regular_invocable。这需要：

调用函数调用表达式应保持相等（[concepts.equality]）并且不得修改函数对象或参数。

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

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

于 2021-04-09T15:56:35.153 回答