为什么 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()中 的描述：

\n

\n

constexpr iterator begin();

\n

返回：{*this, ranges\xe2\x80\x8b::\xe2\x80\x8bfind_\xc2\xadif(base_\xc2\xad, ref(*pred_\xc2\xad))}.

\n

备注: 为了提供模型\nrange时概念所需的摊余常量时间复杂度，该函数将结果缓存在 \n 中以供后续调用使用。filter_\xc2\xadviewforward_\xc2\xadrangefilter_\xc2\xadview

\n

\n

也就是说，实现需要在内部缓存满足ranges\xe2\x80\x8b::\xe2\x80\x8bfind_if谓词的迭代器，这使得后续的每次调用都begin()可以在常数时间内简单地返回缓存的值，就​​像libstdc++所做的那样：

\n

template<input_range _Vp, indirect_unary_predicate<iterator_t<_Vp>> _Pred>\nclass filter_view : public view_interface<filter_view<_Vp, _Pred>> {\n  _Vp _M_base = _Vp();\n  __box<_Pred> _M_pred;\n  _CachedPosition<_Vp> _M_cached_begin;\n\npublic:\n  // ...\n  constexpr _Iterator\n  begin() {\n    if (_M_cached_begin._M_has_value())\n      return {this, _M_cached_begin._M_get(_M_base)};\n   \n    auto __it = ranges::find_if(_M_base, std::ref(*_M_pred));\n    _M_cached_begin._M_set(_M_base, __it);\n    return {this, std::move(__it)};\n  }\n};\n

\n

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

\n

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

\n

其中，drop_while_view、split_view和永远不会chunk_by_view被const-iterable，因为它们没有 const 限定，就像 一样。begin()filter_view

\n