32 
#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 对象必须是非常量才能查询其元素？

4

2 回答 2

24

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

于 2021-05-24T06:17:22.887 回答
4

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

constexpr iterator begin();

回报：{*this, ranges​::​find_­if(base_­, ref(*pred_­))}。

备注：为了提供模型 range时概念所需的摊销常数时间复杂度，此函数将结果缓存在 中， 以供后续调用使用。filter_­viewforward_­rangefilter_­view

也就是说，实现需要在内部缓存ranges​::​find_if满足谓词的迭代器，这使得每个后续调用都begin()可以简单地以恒定时间返回缓存的值，就​​像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)};
  }
};

由于第一次filter_view调用时需要在里面设置缓存值，这使得无法-qualified。begin()begin()const

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

其中drop_while_view,split_view和永远不是chunk_by_viewconst -iterable ，因为它们没有 const-qualified ，就像.begin()filter_view

于 2022-02-19T10:12:13.253 回答