范围修剪视图的实现不能与反向视图一起使用。

问题描述 投票：1回答：1

我写了一个C++20的范围视图(不是范围-v3视图)，叫做 trim 给定一个范围和一个单元谓词，返回一个没有满足谓词的前后元素的新范围。(range-v3库有这样一个视图，但在C++20中没有。)

下面是实现方法（这可能不是最优的，但是关于range库的文档不多，所以在资源有限的情况下，这是我能想到的）。

namespace rg = std::ranges;

// -------- trim ----------

template<rg::input_range R, typename P> requires rg::view<R>
class trim_view : public rg::view_interface<trim_view<R, P>>
{
private:
    R base_ {};
    P pred_;
    mutable rg::iterator_t<R> iter_ {std::begin(base_)};
    mutable rg::iterator_t<R> end_  {std::end(base_)};
public:
    trim_view() = default;

    constexpr trim_view(R base, P pred)
        : base_(std::move(base)), pred_(std::move(pred)), iter_(std::begin(base_)), end_(std::end(base_))
    {}

    constexpr R base() const &
    {return base_;}
    constexpr R base() && 
    {return std::move(base_);}

    constexpr auto begin()
    {
        while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
        while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
        return iter_;
    }
    constexpr auto begin() const requires rg::range<const R>
    {
        while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
        while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
        return iter_;
    }
    constexpr auto begin() requires rg::random_access_range<R> && rg::sized_range<R>
    {
        while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
        while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
        return iter_;
    }
    constexpr auto begin() const requires rg::random_access_range<const R> && rg::sized_range<const R>
    {
        while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
        while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
        return iter_;
    }

    constexpr auto end()
    { return end_ ; }
    constexpr auto end() const requires rg::range<const R>
    { return end_ ; }
    constexpr auto end() requires rg::random_access_range<R> && rg::sized_range<R>
    { return end_ ; }
    constexpr auto end() const requires rg::random_access_range<const R> && rg::sized_range<const R>
    { return end_ ; }

    constexpr auto size() requires rg::sized_range<R>
    { return std::distance(iter_, end_); }    
    constexpr auto size() const requires rg::sized_range<const R>
    { return std::distance(iter_, end_); }
};

template<class R, typename P>
trim_view(R&& base, P pred)
    -> trim_view<rg::views::all_t<R>, P>;

namespace details
{
    template <typename P>
    struct trim_view_range_adaptor_closure
    {
        P pred_;
        constexpr trim_view_range_adaptor_closure(P pred)
            : pred_(pred)
        {}

        template <rg::viewable_range R>
        constexpr auto operator()(R && r) const
        {
            return trim_view(std::forward<R>(r), pred_);
        }
    } ;

    struct trim_view_range_adaptor
    {
        template<rg::viewable_range R, typename P>
        constexpr auto operator () (R && r, P pred)
        {
            return trim_view( std::forward<R>(r), pred ) ;
        }

        template <typename P>
        constexpr auto operator () (P pred)
        {
            return trim_view_range_adaptor_closure(pred);
        }   
    };

    template <rg::viewable_range R, typename P>
    constexpr auto operator | (R&& r, trim_view_range_adaptor_closure<P> const & a)
    {
        return a(std::forward<R>(r)) ;
    }
}

namespace views
{
    inline static details::trim_view_range_adaptor trim;
}

它工作得很好。我写了一些测试来确保它是确定的。

template <typename P>
void are_equal(std::vector<int> const & input, std::vector<int> const & output, P&& pred)
{
    std::size_t index = 0;
    for(auto  i : input | views::trim(std::forward<P>(pred)))
    {
        assert(i == output[index]);
        index++;
    }
    assert(index == output.size());
}

int main()
{
    auto is_odd = [](const int x){return x%2==1;};

    are_equal({}, {}, is_odd);
    are_equal({1}, {}, is_odd);    
    are_equal({1,3,5}, {}, is_odd);
    are_equal({2}, {2}, is_odd);
    are_equal({2,4}, {2,4}, is_odd);
    are_equal({2,3,4}, {2,3,4}, is_odd);
    are_equal({1,2,3,4}, {2,3,4}, is_odd);
    are_equal({1,1,2,3,4}, {2,3,4}, is_odd);
    are_equal({2,3,4,5}, {2,3,4}, is_odd);
    are_equal({2,3,4,5,5}, {2,3,4}, is_odd);
    are_equal({1,2,3,4,5}, {2,3,4}, is_odd);
    are_equal({1,1,2,3,4,5,5}, {2,3,4}, is_odd);
}

问题是，当我应用 views::reverse 视图在修剪后就不能再正常工作了。

template <typename P>
void are_equal_reverse2(std::vector<int> const & input, std::vector<int> const & output, P&& pred)
{
    std::size_t index = 0;
    for(auto  i : input | views::trim(std::forward<P>(pred)) | rg::views::reverse)
    {
        assert(i == output[index]);
        index++;
    }
    assert(index == output.size());
}

int main()
{
    auto is_odd = [](const int x){return x%2==1;};

    // OK
    are_equal_reverse2({}, {}, is_odd);
    are_equal_reverse2({1}, {}, is_odd);
    are_equal_reverse2({1,3,5}, {}, is_odd);
    are_equal_reverse2({2}, {2}, is_odd);
    are_equal_reverse2({2,4}, {4,2}, is_odd);
    are_equal_reverse2({2,3,4}, {4,3,2}, is_odd);
    are_equal_reverse2({1,2,3,4}, {4,3,2}, is_odd);
    are_equal_reverse2({1,1,2,3,4}, {4,3,2}, is_odd);

    // fail
    are_equal_reverse2({2,3,4,5}, {4,3,2}, is_odd);
    are_equal_reverse2({2,3,4,5,5}, {4,3,2}, is_odd);
    are_equal_reverse2({1,2,3,4,5}, {4,3,2}, is_odd);
    are_equal_reverse2({1,1,2,3,4,5,5}, {4,3,2}, is_odd);
}

范围{2,3,4,5}变成{2,3,4}。在反向应用时，它应该变成{4,3,2}。然而，结果实际上是{5,4,3,2}。

我希望 views::reverse 适用 std::make_reverse_iterator() 的开始和结束迭代器上。这应该会执行下面的转换。

trim_view        reverse_view (expected)      reverse_view (actual)
--------------------------------------------------------------------
2 3 4 5 _         _ 2 3 4 5                   _ 2 3 4 5
^     ^           ^     ^                     ^       ^
|     |      =>   |     |                     |       |
|     end_        rend  |                     rend    |
iter_                   rbegin                        rbegin

我不知道我错过了什么。希望得到任何帮助。

下面是一个工作示例的链接。https:/wandbox.orgpermlink4iFNsqiz9Y9Bfm64。

c++ stl c++20 range-v3
1个回答
2
投票

首先，让我们从这个开始。

constexpr auto begin()
{
    while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
    while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
    return iter_;
}
constexpr auto begin() const requires rg::range<const R>
{
    while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
    while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
    return iter_;
}
constexpr auto begin() requires rg::random_access_range<R> && rg::sized_range<R>
{
    while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
    while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
    return iter_;
}
constexpr auto begin() const requires rg::random_access_range<const R> && rg::sized_range<const R>
{
    while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
    while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
    return iter_;
}

constexpr auto end()
{ return end_ ; }
constexpr auto end() const requires rg::range<const R>
{ return end_ ; }
constexpr auto end() requires rg::random_access_range<R> && rg::sized_range<R>
{ return end_ ; }
constexpr auto end() const requires rg::random_access_range<const R> && rg::sized_range<const R>
{ return end_ ; }

所有这些重载做的事情都是一样的 所以我们把它缩减到两个吧

constexpr auto begin() const
{
    while(iter_ != std::end(base_) && pred_(*iter_)) {iter_ = std::next(iter_);} 
    while(end_ != iter_ && pred_(*std::prev(end_))) {end_ = std::prev(end_);}
    return iter_;
}

constexpr auto end() const
{ return end_ ; }

好了 这里发生了什么？begin() 将调整两个 iter_ 和 end_ 要修剪，和 end() 只是返回 end_.

如果你这样做，这很好，所有。

auto trimmed = some_range | trim(some_pred);
auto b = trimmed.begin();
auto e = trimmed.end();

但如果你这样做，会发生什么？

auto e = trimmed.end();
auto b = trimmed.begin();

end 在这种情况下，将是 some_range.end()，它不会是这个范围的正确结束迭代器! 你需要确保 begin() 和 end() 之间没有任何排序依赖关系--它们总是要返回正确的值。

另外， trim(p) 可以将其全部还原为：

template <rg::viewable_range R, typename P>
constexpr auto operator ()(R && r, P pred)
{
    auto negated = std::not_fn(pred);
    auto f = rg::find_if(r, negated);
    auto l = rg::find_if(r | std::views::reverse, negated).base();
    return rg::subrange(f, l);
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.