50 
#include <ranges>
#include <iostream>
#include <string_view>

using namespace std::literals;

int main()
{
    auto fn_is_l = [](auto const c) { return c == 'l'; };

    {
        auto v = "hello"sv | std::views::filter(fn_is_l);
        std::cout << *v.begin() << std::endl; // ok
    }

    {
        auto const v = "hello"sv | std::views::filter(fn_is_l);
        std::cout << *v.begin() << std::endl; // error
    }
}

See: https://godbolt.org/z/vovvT19a5

<source>:18:30: error: passing 'const std::ranges::filter_view<
                       std::basic_string_view<char>, main()::
                       <lambda(auto:15)> >' as 'this' argument discards
                       qualifiers [-fpermissive]
   18 |         std::cout << *v.begin() << std::endl; // error
      |                       ~~~~~~~^~
In file included from <source>:1:/include/c++/11.1.0/ranges:1307:7: 
     note: in call to 'constexpr std::ranges::filter_view<_Vp, 
           _Pred>::_Iterator std::ranges::filter_view<_Vp, Pred>
           ::begin() [with _Vp = std::basic_string_view<char>; _Pred =
           main()::<lambda(auto:15)>]'
 1307 |       begin()
      |       ^~~~~

Why must a std::ranges::filter_view object be non-const for querying its elements?

Improve this question
2
  • 2
    Have you tried using cbegin() instead? Commented May 24, 2021 at 6:06
  • no cbegin member for a std::ranges::view object by default. Commented May 24, 2021 at 6:07

2 Answers 2

Reset to default
38

In order to provide the amortized constant time complexity required by range, filter_view::begin caches the result in *this. This modifies the internal state of *this and thus cannot be done in a const member function.

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

That's curious if the result with or without the cache can be guaranteed to be the same. (Can it?) then mutable is an option right? const is all about the external api to an object not the internal state. It is non trivial to use mutable keyword correctly but it can be done.
@bradgonesurfing Right, technically this is possible, but this requires thread synchronization (to meet the requirement for const functions), which is deemed too expensive.
Is it not allowed to do the caching on a per-thread basis?
@dan04 - that no longer meets the time complexity requirements, at least from a pedantic point of view.
FYI: P0789R3 1.3.1 "The filter adaptor is not const-iterable" explains the design decision of filter_view.
|
9

The time complexity requirement here comes from the description of filter_view::begin() in [range.filter.view]:

constexpr iterator begin();

Returns: {*this, ranges​::​find_­if(base_­, ref(*pred_­))}.

Remarks: In order to provide the amortized constant time complexity required by the range concept when filter_­view models forward_­range, this function caches the result within the filter_­view for use on subsequent calls.

That is to say, the implementation needs to internally cache the iterator found by ranges​::​find_if that satisfies the predicate, which allows each subsequent call to begin() to simply return the cached value in constant time, just like libstdc++ does:

template<input_range _Vp, indirect_unary_predicate<iterator_t<_Vp>> _Pred>
class filter_view : public view_interface<filter_view<_Vp, _Pred>> {
  _Vp _M_base = _Vp();
  __box<_Pred> _M_pred;
  _CachedPosition<_Vp> _M_cached_begin;

public:
  // ...
  constexpr _Iterator
  begin() {
    if (_M_cached_begin._M_has_value())
      return {this, _M_cached_begin._M_get(_M_base)};
   
    auto __it = ranges::find_if(_M_base, std::ref(*_M_pred));
    _M_cached_begin._M_set(_M_base, __it);
    return {this, std::move(__it)};
  }
};

Since it needs to set the cache value inside filter_view when calling begin() for the first time, this makes the begin() unable to be const-qualified.

It is worth noting that other range adaptors with similar time complexity requirements include drop_view, drop_while_view, split_view, reverse_view, and C++23's chunk_by_view.

Among them, drop_while_view, split_view and chunk_by_view are never const-iterable, because they do not have a const-qualified begin(), just like filter_view.

Improve this answer

1 Comment

That's really helpful, particularly the list of other similar classes. Thank you for this.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.