Zenn
⛓️

［C++］ <ranges>のviewを見る16 - reverse_view

2020/10/28に公開
C++
cpp20
ranges
tech

reverse_view

reverse_viewは元となるシーケンスを逆順にしたシーケンスを生成するViewです。

#include <ranges>

int main() {
  auto seq = std::views::iota(1, 10)
    | std::views::filter([](int n) { return n % 2 == 1; })
    | std::views::transform([](int n) { return n * 10; });
  
  std::ranges::reverse_view rv{seq};
  
  for (int n : rv) {
    std::cout << n; // 9070503010
  }
}

逆順にするという操作の都合上、入力となるrangeはbidirectional_range以上でなければなりません。reverse_viewそのものは入力rangeと同じカテゴリになります。

遅延評価

reverse_viewは遅延評価によって逆順範囲を生成します。とはいえ、実際の逆順範囲に関してはstd::reverse_iteratorに丸投げしているので、reverse_viewの行うことはbegin()によってイテレータを取得するタイミングでstd::reverse_iteratorを適切に構築することです。

そこではまず、元のシーケンスがcommon_rangeであればその終端イテレータ（end()で取得できるイテレータ）を使ってstd::reverse_iteratorを構築します。そうでない場合はstd::ranges::next()によって終端イテレータを求めて、それによってstd::reverse_iteratorを構築します。元のシーケンスがcommon_rangeではないbidirectional_rangeである場合、終端イテレータの取得はインクリメントによって行われるため、シーケンスの長さをNとしたO(N)の時間計算量となってしまいます（そのようなイテレータはなかなかない気がしますが）。

auto seq = std::views::iota(1, 10)
  | std::views::filter([](int n) { return n % 2 == 1; })
  | std::views::transform([](int n) { return n * 10; });

// 構築の時点では何もしない
std::ranges::reverse_view rv{seq};

// イテレータ取得時に元となるシーケンスの終端一つ手前のイテレータからreverse_iteratorを構築して返す
// 元となるシーケンスがcommon_rangeではなく単にbidirectional_rangeである場合、時間計算量はO(N)になる
auto it = std::ranges::begin(rv);

// イテレータの操作はreverse_iteratorと同じ
++it;
--it;
int n = *it;

// 元のシーケンスはcommon_rangeでなくてもok
bool fin = it == std::ranges::end(rv);

また、このreverse_viewのbegin()の処理結果はキャッシュされることが規定されています。これによってreverse_viewのbegin()の計算量は償却定数となります。

views::reverse

reverse_viewに対応するrange adaptor objectがstd::views::reverseです。

#include <ranges>

int main() {
  auto seq = std::views::iota(1, 10)
    | std::views::filter([](int n) { return n % 2 == 1; })
    | std::views::transform([](int n) { return n * 10; });
  
  for (int n : std::views::reverse(seq)) {
    std::cout << n; // 9070503010
  }
  
  std::cout << '\n';
  
  // パイプラインスタイル
  for (int n : seq | std::views::reverse) {
    std::cout << n; // 9070503010
  }
}

views::reverseはカスタマイゼーションポイントオブジェクトであり、rangeオブジェクトを1つ受け取りそれを転送してreverse_viewを構築して返します。ただし、すでに逆順になっているシーケンス（reverse_viewやreverse_iteratorのsubrange）に対してはその元になっているrangeを返す事によって、reverse_viewを何回も適用する事を回避します。

#include <ranges>

int main() {
  std::vector vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

  for (int n : vec | std::views::reverse  // vector<int> -> reverse_view
                   | std::views::reverse  // reverse_view -> ref_view<vector<int>>
                   | std::views::reverse  // ref_view<vector<int>> -> reverse_view
                   | std::views::reverse  // reverse_view -> ref_view<vector<int>>
      )
  {
    std::cout << n; // 123456789
  }
}

Discussion