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>
int a[] = {1, 2, 3, 4, 5};
const auto view1 = a | std::views::take(3);
for (auto& e: view1) {
e *= 2;
}
auto view2 = std::as_const(a) | std::views::take(3);
for (auto& e: view2) {
e *= 2;
}
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>
template <std::ranges::view View>
void f0(const View& view)
{
for (const auto& e : view)
std::cout << e;
}
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);
f0(a | is_odd);
f1(a | take3);
f1(a | is_odd);
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
関連URL