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

Question

#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?

Answer 1

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.

Answer 2

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.