⛓️

[C++] <ranges>のviewを見る12 - join_view

2020/10/23に公開

join_view

join_viewViewrangeとなっているシーケンスを平坦化したシーケンスを生成する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_viewrangeは通常、元となるシーケンスの外側と内側のrangeが両方ともbidirectional_range以上であればbidirectional rangeとなり、forward_range以上であればforward rangeとなります。
それ以外の場合、及び外側のrangeのイテレータの*prvalueを返すような場合には常にinput rangeになります。

この例ではstd::vectorstd::vectorを利用していますが、別に外側と内側のrangeが同じものである必要はありません。std::liststd::vectorとか、std::dequeの生配列など、rangerangeになっていれば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 objectstd::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はカスタマイゼーションポイントオブジェクトであり、rangerangeとなっているrangeオブジェクト1つを受け取りそれを転送してjoin_viewを構築して返します。

Discussion