I wrote a C++20 range view (not a range-v3 view) called trim that, given a range and a unary predicate, returns a new range without the front and back elements that satisfy the predicate. (The range-v3 library has such a view, but it's missing from C++20.)
Here is the implementation (this may not be optimal, but there isn't a lot of documentation on the ranges library, so this is what I could come up with given the limited resources):
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;
}
It works fine. I wrote some tests to make sure it's OK.
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);
}
The problem is, when I apply the views::reverse view after trimming then it no longer works properly.
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);
}
The range {2,3,4,5} becomes {2,3,4}. With reverse applied, it should become {4,3,2}. However, the result is actually {5,4,3,2}.
I expect that views::reverse applies std::make_reverse_iterator() on the begin and end iterators of the trim view. That should perform the following transformation:
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
I am not sure what I am missing here. Any help is appreciated.
Here is the link to a working sample: https://wandbox.org/permlink/4iFNsqiz9Y9Bfm64
First of all, let's start with this:
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_ ; }
All of these overloads do the exact same thing, so let's just reduce down to two:
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_ ; }
Alright now. What's going on here? begin() will adjust both iter_ and end_ to be trimmed, and end() just returns end_.
That's fine and all if you do this:
auto trimmed = some_range | trim(some_pred);
auto b = trimmed.begin();
auto e = trimmed.end();
But what happens if you do this:
auto e = trimmed.end();
auto b = trimmed.begin();
end in this case will be some_range.end(), it won't be the correct end iterator for this range! You need to ensure that begin() and end() don't have any ordering dependencies between them - they always have to return the correct value.
Also, trim(p) can be reduced in its entirety to:
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);
}