Zenn
⛓️

［C++］ <ranges>のviewを見る12 - join_view

2020/10/23に公開
C++
#
cpp20
#
ranges
tech

join_view

join_viewはViewのrangeとなっているシーケンスを平坦化したシーケンスを生成するViewです。

#include <ranges>

int main() {
  std::vector<std::vector<int>> vecvec = { {1, 2, 3}, {}, {}, {4}, {5, 6, 7, 8, 9}, {10, 11}, {} };

  std::ranges::join_view jv{vecvec};
  
  for (int n : jv) {
    std::cout << n; // 1234567891011
  }
}

すなわち、配列の配列を1つの配列に直列化するような事を行うものです。

join_viewのrangeは通常、元となるシーケンスの外側と内側のrangeが両方ともbidirectional_range以上であればbidirectional rangeとなり、forward_range以上であればforward rangeとなります。
それ以外の場合、及び外側のrangeのイテレータの*がprvalueを返すような場合には常にinput rangeになります。

この例ではstd::vectorのstd::vectorを利用していますが、別に外側と内側のrangeが同じものである必要はありません。std::listのstd::vectorとか、std::dequeの生配列など、rangeのrangeになっていればjoin_viewは平坦化してくれます。。

#include <ranges>

int main() {
  std::vector<std::list<int>> veclist = { {1, 2, 3}, {}, {}, {4}, {5, 6, 7, 8, 9}, {10, 11}, {} };

  std::ranges::join_view jv1{veclist};
  
  for (int n : jv1) {
    std::cout << n; // 1234567891011
  }
  
  std::cout << '\n';
  
  std::deque<int> arrdeq[] = { {1, 2, 3}, {}, {}, {4}, {5, 6, 7, 8, 9}, {10, 11}, {} };

  std::ranges::join_view jv2{arrdeq};
  
  for (int n : jv2) {
    std::cout << n; // 1234567891011
  }
}

遅延評価

join_viewによるシーケンスもまた遅延評価によって生成されます。join_viewの仕事の殆どは元となるシーケンスの内側のrangeを接続することにあり、イテレータのインクリメントのタイミングでそれを行います。

join_viewは元となるシーケンスの内側のシーケンスのイテレータを利用する事で1つの内側rangeのイテレートを行います。そのイテレータが終端に達した時（1つの内側rangeの終端に達した時）、外側rangeのイテレータを一つ進めてそこから次の内側rangeのイテレータを取得します。
そのままだと内側rangeが空の場合に死ぬので、すぐに内側rangeの終端チェックを行い空でない内側rangeが見つかるまで外側rangeをイテレートします。

std::vector<std::vector<int>> vecvec = { {1, 2, 3}, {}, {}, {4}, {5, 6, 7, 8, 9}, {10, 11}, {} };

// 構築とイテレータ取得時には何もしない
std::ranges::join_view jv{vecvec};
auto it = std::ranges::begin(jv);

// インクリメント時に内側イテレータの接続を行う
// 内側イテレータが終端に到達していれば、外側イテレータを進めてそこから内側イテレータを再取得する
// 同時に内側イテレータの終端チェックを行い、空の内側*range*をスキップする
++it;

// デクリメント時はその逆を行う
--it;

// 間接参照は元のシーケンスのイテレータそのまま
int n = *it;

1つの内側rangeをイテレートしている間は内側イテレータの終端チェックのみが行われますが、終端に到達した時（2つの内側rangeを接続する時）は少し処理が重くなります。

次の図は、配列の配列になっているシーケンスとjoin_viewの様子をそれっぽく書いたものです。

の様子

views::join

join_viewに対応するrange adaptor objectがstd::views::joinです。

int main() {
  std::vector<std::vector<int>> vecvec = { {1, 2, 3}, {}, {}, {4}, {5, 6, 7, 8, 9}, {10, 11}, {} };

  for (int n : std::views::join(vecvec)) {
    std::cout << n;
  }

  std::cout << '\n';

  // パイプラインスタイル
  for (int n : vecvec | std::views::join) {
    std::cout << n;
  }
}

views::joinはカスタマイゼーションポイントオブジェクトであり、rangeのrangeとなっているrangeオブジェクト1つを受け取りそれを転送してjoin_viewを構築して返します。

Discussion