为什么 std::ranges::filter_view 对象必须是非常量才能查询其元素？

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
    }
}

参见：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()
      |       ^~~~~

为什么 std::ranges::filter_view 对象必须是非常量才能查询其元素？

Answer 1

为了提供 range 所需的分摊常数时间复杂度，filter_view::begin 将结果缓存在 *this 中。这修改了 *this 的内部状态，因此不能在 const 成员函数中完成。

Answer 2

这里的时间复杂度要求来自[range.filter.view]中filter_view::begin()的描述：

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.

也就是说，实现需要在内部缓存ranges::find_if找到的满足谓词的迭代器，这使得后续对begin()的每次调用都可以简单地return缓存恒定时间的值，就像 libstdc++ 所做的那样：

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)};
  }
};

由于第一次调用begin()时需要在filter_view里面设置缓存值，所以导致begin()无法被const限定。

值得注意的是，具有类似时间复杂度要求的其他范围适配器包括drop_view, drop_while_view, split_view, reverse_view, and C++23's chunk_by_view。

其中，drop_while_view、split_view和chunk_by_view是从未const-iterable，因为他们没有const-qualified begin(), 就像 filter_view.

为什么 std::ranges::filter_view 对象必须是非常量才能查询其元素？

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

c++

standards

constants

c++20

std-ranges