filter_viewがconst-iterableではない理由

発端

• C++20でfilter_viewがconstの時にrangeコンセプトを満たさないのは何故？ - stackoverflow

キャッシュしてるから？でも他のもしてるじゃん。なんで・・・

本当に全てのviewがconst-iterable？
→NO

range adopterだけ見ても、drop_while_viewもconst-iterableではない。

• C++20 Range Adaptors and Range Factories

filter_view

• 指定された条件を満たさない要素を落とす
• begin()の呼び出しは、まず一番最初の条件を満たす要素までイテレータを進めて、それを返す
• その際、求めたイテレータをキャッシュする

drop_while_view

• 指定された条件を満たす要素を先頭から取り除く
• begin()の呼び出しは、まず一番最初の条件を満たさない要素までイテレータを進めて、それを返す
• その際、求めたイテレータをキャッシュする

共通点は、begin()ではベースのrangeのイテレータを場合によってはある程度進めてしまう事、そしてその結果をキャッシュすること。

キャッシュが問題なのか？

drop_viewもbegin()の呼び出しで指定された数イテレータを進めてそれを返し、求めたイテレータはキャッシュする。

キャッシュ動作の有無はconst-iterableとは関係ない？

標準ライブラリのクラスのメンバ関数に対するconst修飾は、スレッドセーフであることを表明する。

• const, mutableキーワードとスレッド安全性 - yohhoyの日記

viewがキャッシュ機構を持ちbegin()がそれを利用する場合、begin()はconstではいられず、constメンバ関数であるためには追加の同期を必要とする。多くの場合それはユーザーの責任によって行われる。

そのため、キャッシュ機構を持つviewは本来const-iterableとはならない。

では逆に、なぜdrop_viewはconst-iterableなのか？

namespace std::ranges {
  template<view V>
  class drop_view : public view_interface<drop_view<V>> {
  public:
    constexpr auto begin()
      requires (!(simple-view<V> && random_access_range<V>));
    constexpr auto begin() const
      requires random_access_range<const V>;
  };
}

drop_viewのbegin()メンバ関数のconstオーバーロードは制約されており、ベースのrange（をconst修飾したもの）がrandom_access_rangeである場合にのみ利用可能となる。

すなわち、ベースのrangeのイテレータがrandom access iteratorであるときにのみ、drop_viewはconst-iterableである。

なぜかというと、ランダムアクセスイテレータの進行は範囲の長さや進む距離によらず一定（O(1)）で行うことができる。すなわち、キャッシュ機構を用いなくてもrangeコンセプトの意味論要件（呼び出しは償却定数時間であること）を満たすことができる。

従って、drop_viewはベースのrangeがrandom_access_rangeである場合、そのbegin()の呼び出しはキャッシュ機構を使用せず、それによってconstオーバーロードが提供可能であり、あとはベースのrangeがconst-iterableならば、drop_viewもconst-iterableとる。

filter_viewとdrop_while_viewはいずれも、落とす（残す）要素の数を指定するのではなく、条件をしていする。

満たすものを残すのか落とすのかの差異はあれど、begin()の呼び出しで返すイテレータは指定された条件で決まる。すなわち、一番先頭かもしれないし終端になるかもしれない。

従って、ベースのrangeが何であっても、条件に合う要素を見つけるまで必ず要素を一つづつ見て行く必要がある。そこでは、ベースのrangeの長さをNとすると最大でO(N)の時間がかかる。

drop_viewの時とは異なり、random_access_rangeであったとしても見るべき要素の数は変わらず、キャッシュ機構の利用が避けられない。すなわち、begin()のconstオーバーロードを提供できない。

filter_view（とdrop_while_view）がconst-iterableではない（begin()/end()のconstオーバーロードがない）のは、どんな場合でもキャッシュの利用が避けられず、追加の同期なしではスレッドセーフ性を保証できないため。だと思われる。

FYI: P0896R4 The One Ranges Proposal(Adopted 2018-11) から P0789R3 Range Adaptors and Utilities と辿ったところ、Design Considerations > The filter adaptor is not const-iterableに背景説明がありました。

4. Compute the first position once in begin on demand and cache the result, without synchronization. The downside of this approach is that begin cannot be const without violating [res.on.data.races].

None of these are great options, and this particular design point has been discussed at extensive length (see range-v3#385) in the context of the filter view and an assortment of other adaptors that are unable to provide const iteration. The general consensus is that option (4) above is the least bad option, and is consistent with the perspective that adaptors are lazily-evaluated algorithms: some algorithms can be implemented without the need to maintain mutable state. Others cannot.

drop_while_viewは別提案 P1035R7 Input Range Adaptors(Adopted 2019-07) 経由でしたが、filter同様にonihusbeさん考察通りだと思われます。