yohhoyの日記

技術的メモをしていきたい日記

Rangeアダプタ std::view::reverse

C++20 Rangesライブラリの逆順ビューstd::ranges::reverse_viewおよびRangeアダプタstd::views::reverse*1についてメモ。

基本の使い方

範囲for構文とRangeアダプタreverseを組み合わせて、配列や文字列やコンテナなどRangeとして扱えるものを逆順に列挙できる。*2 *3

#include <iostream>
#include <map>
#include <string>
#include <string_view>
#include <ranges>
using namespace std::literals;  // ""sv

int a[] = {1, 2, 3, 4, 5};
for (int n: a | std::views::reverse) {
  std::cout << n;  // 54321
}

for (char c: "Hello"sv | std::views::reverse) {
  std::cout << c;  // olleH
}
// 文字列リテラル "Hello" に適用すると終端NUL文字を含む6文字が
// '\0', 'o', 'l', 'l', 'e', 'H' 順で列挙されることに注意。

std::map<int, std::string> m = {{1, "apple"}, {2, "banana"}, {3, "cinnamon"}};
for (const auto& [k, v]: m | std::views::reverse) {
  std::cout << k << ":" << v << '\n';
  // 3:cinnammon
  // 2:banana
  // 1:apple
}

対象を逆順走査するには、そのイテレータが双方向(bidirectional)走査可能である必要がある。例えば単方向リストstd::forward_listイテレータは双方向走査をサポートしないため、reverseと組み合わせるとコンパイルエラーとなる。膨大なエラーメッセージと共に_(:3 」∠)_*4

#include <forward_list>
#include <ranges>

std::forward_list lst = {1, 2, 3, 4, 5};
// std::forward_list は forward_range だが bidirectional_range ではない
static_assert( !std::ranges::bidirectional_range<decltype(lst)> );

for (int n: lst | std::views::reverse) {  // NG: ill-formed
  // ...
}

応用例

Range分割アダプタstd::views::splitの適用後は Forward Range となり、下記コードのように直接reverseと組み合わせてもコンパイルエラーになる。これはC++20 Rangesライブラリは遅延(lazy)評価戦略をとるため、分割処理が前方向(forward)にのみ行われることに起因する。

#include <iostream>
#include <string_view>
#include <ranges>

std::string_view str = "apple,banana,cinnamon";

// NG: カンマ(,)区切りで分割後にアイテム名を逆順表示
for (auto item: str | std::views::split(' ') | std::views::reverse) {  // ill-formed
  std::cout << item << '\n';
}

次期C++2b(C++23)向けの提案文書P2210R2は欠陥修正としてC++20へも遡及適用されるため、C++20標準ライブラリ+P2210R2適用済みであれば下記コードで所望の動作となる*5。さらにC++2b標準ライブラリであれば、式(分割後subrange) | std::views::reverseからstd::string_viewを直接構築できるようになる。(→id:yohhoy:20210624

// C++20 + P2210R2
// OK: カンマ(,)区切りで分割後にアイテム名を逆順表示
for (auto rev_item: str | std::views::reverse | std::views::split(',')) {
  // rev_itemは nomannic, ananab, elppa と列挙されるため
  // 個別にreverseを適用して元の文字並び順に復元する
  auto item = rev_item | std::views::reverse;
  // coutストリーム出力を行うには部分範囲itemの型
  // subrange<const char*, const char*, subrange_kind::sized>
  // から文字列型std::stringへの明示変換が必要となる
  std::cout << std::string{item.begin(), item.end()} << '\n';
}
// cinnamon
// banana
// apple
// C++2b(C++23)
// OK: カンマ(,)区切りで分割後にアイテム名を逆順表示
for (auto rev_item: str | std::views::reverse | std::views::split(',')) {
  std::cout << std::string_view{rev_item | std::views::reverse} << '\n';
}

// OK: カンマ分割結果を逆順にstring_view化するRangeアダプタ
auto split_reverse =
  std::views::reverse
  | std::views::split(',')
  | std::views::transform([](auto rv){
    return std::string_view{rv | std::views::reverse};
  });
for (auto item: str | split_reverse) {
  std::cout << item << '\n';
}

C++20 24.7.14.1/p1-2より引用。

1 reverse_view takes a bidirectional view and produces another view that iterates the same elements in reverse order.
2 The name views::reverse denotes a range adaptor object (24.7.1). Given a subexpression E, the expression views::reverse(E) is expression-equivalent to:

  • If the type of E is a (possibly cv-qualified) specialization of reverse_view, equivalent to E.base().
  • Otherwise, if the type of E is cv-qualified
    subrange<reverse_iterator<I>, reverse_iterator<I>, K>
    for some iterator type I and value K of type subrange_kind,
    • if K is subrange_kind::sized, equivalent to:
      subrange<I, I, K>(E.end().base(), E.begin().base(), E.size())
    • otherwise, equivalent to:
      subrange<I, I, K>(E.end().base(), E.begin().base())

  However, in either case E is evaluated only once.

  • Otherwise, equivalent to reverse_view{E}.

関連URL

*1:完全修飾名は std::ranges::views::reverse だが標準ヘッダ<ranges>内で namespace std { namespace views = ranges::views; } と宣言されており、std::views::reverse とも記述できる。

*2:厳密には View として扱えるものを対象とする。View は Range の一種であり、コピー/ムーブ操作や破棄操作を定数時間で行えるものが View と定義される(C++20 24.4.4)。両者には構文上の差異がないため、ユーザ定義型向けのカスタマイズポイントとして変数テンプレート std::range::enable_view<T> が提供される。

*3:例示コードではRangeアダプタ適用によるテンプレートクラス型推論過程で int[5] は std::ranges::ref_view<int [5]> へ、std::map<int, std::string> は std::ranges::ref_view<std::map<int, std::string>> へと View に自動変換されている。2例目の std::basic_string_view は字面通りそのまま View とみなされる。仮に std::string とした場合は std::ranges::ref_view<std::string> へ変換される。

*4:https://gist.github.com/yohhoy/4ff16f93d62e35be3788c5cdca5858d0

*5:R2210R2修正前の場合、split適用後の内部イテレータは Forward Iterator となりそのままでは逆順走査を行えない。一旦バッファリングしてから文字列反転させる必要がある。実装例:https://gist.github.com/yohhoy/5f104e6d3aee2b3e927419664abf63af