RangeとViewとconst修飾 - yohhoyの日記

C++20 RangesライブラリのRangeとViewとconst修飾の関係についてメモ。

まとめ：

対象Rangeのconst修飾（要素の変更可否）と、Viewのconst修飾（const-iterableの可否）は異なる概念である。
C++20標準ライブラリ提供の一部Rangeアダプタでは、const修飾によりViewとして機能しなくなるものがある。
- 具体例：std::views::filter, std::views::drop_while
Viewを受け取るパラメータでは不用意にconst修飾を行わないこと。
- Viewは定義上「軽量にコピー／ムーブ」されるオブジェクトのため、パラメータ型は非constな値型とすればよい。

下記コードのようにViewをconst修飾しても、対象Range要素がconst修飾されていなければ要素値を書き換え可能。要素書き換えから保護するには、対象Range側をconst修飾する（ここではstd::as_constを利用）。*1

2022-08-24追記：C++2b(C++23)標準ライブラリにはstd::views::as_constレンジアダプタが追加され、view2はa | std::views::as_const | std::views::take(3)とも書ける。

#include <ranges>
#include <utility>  // as_const

int a[] = {1, 2, 3, 4, 5};
// Rangeに対するconst-View：要素を変更可能
const auto view1 = a | std::views::take(3);
for (auto& e: view1) {
  e *= 2;  // OK
}
// a == {2, 4, 6, 4, 5}

// const-Rangeに対するView：要素変更は不可能
auto view2 = std::as_const(a) | std::views::take(3); 
for (auto& e: view2) {
  e *= 2;  // NG: ill-formed
}

const性(const-ness)に関するRangeとViewとの関係性は、コンテナ(container)に対するイテレータ(iterator)、配列(array)に対するポインタ(pointer)に相当する。イテレータやポインタが指す先のconst性は重要視されるが、イテレータやポインタそのものをconst修飾する必要性は低い。

例1：コンテナVec=std::vector<T>に対するVec::const_iteratorとconst Vec::iterator
例2：配列T[N]に対するconst T *とT * const

C++20標準ライブラリRangeアダプタstd::views::filterは const-iterable でないため、関数f0のようにViewをconst修飾(const View&)するとfilterが適用されたViewを受け取れず、汎用アルゴリズムとしての一般性が失われる*2。コンテナCとイテレータのアナロジーで解釈すると：関数f0はconst C::iterator&を、関数f1はC::iteratorを受け取るインタフェースに相当する。

#include <iostream>
#include <ranges>

// const-View参照を引数にとる関数テンプレート
template <std::ranges::view View>
void f0(const View& view)
{
  for (const auto& e : view)
    std::cout << e;
}

// Viewを引数にとる関数テンプレート
template <std::ranges::view View>
void f1(View view)
{
  for (const auto& e : view)
    std::cout << e;
}

int a[] = {1, 2, 3, 4, 5};
auto take3  = std::views::take(3);
auto is_odd = std::views::filter([](int n){ return n % 2; });

f0(a | take3);   // OK: "123"
f0(a | is_odd);  // NG: ill-formed

f1(a | take3);   // OK: "123"
f1(a | is_odd);  // OK: "135"

Rangeアダプタfilterとdrop_whileが const-iterable でないのは、Range要件「beginイテレータ取得は償却定数時間(amortized constant time)」を満たしつつ「const操作のスレッド安全性を担保するオーバーヘッド追加を避ける」というライブラリ設計上の選択による。

C++20 24.4.2/p1, 3より引用（下線部は強調）。

1 The range concept defines the requirements of a type that allows iteration over its elements by providing an iterator and sentinel that denote the elements of the range.
template<class T>
  concept range =
    requires(T& t) {
      ranges::begin(t);
      ranges::end(t);
    };
3 Given an expression t such that decltype((t)) is T&, T models range only if

[ranges::begin(t), ranges::end(t)) denotes a range (23.3.1),

both ranges::begin(t) and ranges::end(t) are amortized constant time and non-modifying, and

if the type of ranges::begin(t) models forward_iterator, ranges::begin(t) is equality-preserving.

C++20採択済み(PDF)P0896R4にマージされた提案文書P0789R3 Design Considerations, 1.3.1/p3-4より一部引用（下線部は強調）。

1.3.1 The filter adaptor is not const-iterable
3 The filter view, which skips elements that fail to satisfy a predicate, needs to do an O(N) probe to find the first element that satisfies the predicate so that begin can return it. The options are:

Compute this position on adaptor construction. This solution has multiple problems. First, constructing an adaptor should be O(1). Doing an O(N) probe obviously conflicts with that. Second, the probe would return a position in the source range, but when the filter view is copied, the iterator becomes invalid, lest it be left pointing to an element in the source range. That means that copies and moves of the filter view would need to invalidate the cache and perform another O(N) probe to find the first element of the filtered range. O(N) copy and move operations make it difficult to reason about the cost of building adaptor pipelines.

Recompute the first position on each invocation of begin. This is obviously in conflict with the semantic requirements of the Range concept, which specifies that begin is amortized constant-time.

Compute the first position once in begin on demand and cache the result, with synchronization. Taking a lock in the begin member function in order to update an internal cache permits that operation to be const while satisfying [res.on.data.races], but obviously incurs overhead and violates the "don't pay for what you don't use" mantra.

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].

4 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.

C++20 Rangesライブラリ仕様のベースとなった、range-v3ライブラリのIssue#385より関連議論を一部引用（下線部は強調）。

There's a lot of wrong-thinking about views here: people need to stop thinking of views as being like references to containers and start thinking of views as being like iterators that denote zero or more elements instead of zero or one. Accepting a view by const& has the same semantics as accepting an iterator by const&: it has no effect on the mutability of the denoted elements, it only forbids modifying the iterator/view such that it denotes different elements. Algorithms that take views and/or iterators typically take them by value.
(snip)
https://github.com/ericniebler/range-v3/issues/385#issuecomment-290164218