Zenn
⛓️

［C++］ <ranges>のviewを見る13 - lazy_split_view

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

lazy_split_view

lazy_split_viewは元のシーケンスから指定されたデリミタを区切りとして切り出した部分シーケンスのシーケンスを生成するViewです。

（lazy_split_viewは当初split_viewという名前だった時代があり、この記事はその時代に書かれたため、サンプルコードのWandboxリンク先ではlazy_split_viewではなくsplit_viewを使用しています。適宜読み替えてください・・・）

#include <ranges>

int main() {
  // ホワイトスペースをデリミタとして文字列を切り出す
  std::ranges::lazy_split_view sv{"split_view takes a view and a delimiter, and splits the view into subranges on the delimiter.", ' '};
  
  // lazy_split_viewは切り出した文字列のシーケンスとなる
  for (auto inner_range : sv) {
    // inner_rangeは分割された文字列1つを表すView
    for (char c : inner_range) {
      std::cout << c;
    }
    std::cout << '\n';
  }
}

基本的には文字列の分割に使用することになるでしょう。

lazy_split_viewは切り出した文字列それぞれを要素とするシーケンス（外側range）となります。そのため、その要素を参照すると分割後文字列を表す別のシーケンス（内側range）が得られます。そこから、内側rangeの要素を参照することで1文字づつ取り出すことができます。なお、このinner_range（内側range）はstd::string_viewあるいは類するものではなく、単にforward rangeである何かです。

lazy_split_viewの結果はとても複雑で一見非自明です。たとえば"abc,12,cdef,3"という文字列を,で分割するとき、lazy_split_viewの様子は次のようになっています。

の様子

実際の実装は元のシーケンスのイテレータを可能な限り使いまわすのでもう少し複雑になっていますが、概ねこの図のような関係性のrangeが生成されます。

遅延評価

lazy_split_viewもまた遅延評価によって分割処理とViewの生成を行います。

lazy_split_viewの主たる仕事は元のシーケンス上でデリミタと一致する部分を見つけだし、そこを区切りに内側rangeを生成する事にあります。それは外側rangeのイテレータのインクリメントと内側イテレータの終端チェックのタイミングで行われます。

外側rangeのイテレータ（外側イテレータ）は元のシーケンスのイテレータ（元イテレータ）を持っており、インクリメント時にはそのイテレータから出発して最初に出てくるデリミタ部分を探し出し、そのデリミタ部分の終端位置に元イテレータを更新します。インクリメントと共にこれを行う事で、デリミタ探索範囲を限定しています。

内側rangeにおける終端検出（すなわち文字列分割そのもの）は、内側rangeのイテレータ（内側イテレータ）の終端チェック（==）のタイミングで行われます。内側イテレータは自身を生成した外側イテレータとその親のlazy_split_viewを参照して、外側イテレータの保持する元イテレータの終端チェック→デリミタが空かのチェック→自信の現在位置とデリミタの比較、の順で終端チェックを行います。

// 構築時点では何もしない
std::ranges::lazy_split_view sv{"lazy_split_view takes a view and a delimiter, and splits the view into subranges on the delimiter.", ' '};

// 外側イテレータの取得、特に何もしない
auto outer_it = std::ranges::begin(sv);

// 外側イテレータのインクリメント時、元のシーケンスから次に出現するデリミタを探す
// 内部rangeは"lazy_split_view"->"takes"へ進む
++outer_it;

// 内側rangeの取得、特に何もしない
auto inner_range = *outer_it;

// 内側イテレータの取得、特に何もしない
auto inner_it = std::ranges::begin(inner_range);

// 内側イテレータのインクリメントは、元のシーケンスのイテレータのインクリメントとほぼ等価
++inner_it;

// 元のシーケンスのイテレータのデリファレンスと等価
char c = *inner_it; // a

// 内部rangeの終端チェック
// 元のシーケンスの終端と、デリミタが空かどうか、現在の位置でデリミタが出現しているかどうか、を調べる
bool f = inner_it == std::ranges::end(inner_range); // false

lazy_split_viewの結果が複雑となる一因は、この遅延評価を行うことによるところがあります。

views::lazy_split

lazy_split_viewに対応するrange adaptor objectがstd::views::lazy_splitです。

int main() {
  const auto str = std::string_view("lazy_split_view takes a view and a delimiter, and splits the view into subranges on the delimiter.");

  for (auto inner_range : std::views::lazy_split(str, ' ')) {
    for (char c : inner_range) {
      std::cout << c;
    }
    std::cout << '\n';
  }

  std::cout << "------------" << '\n';

  // パイプラインスタイル
  for (auto inner_range : str | std::views::lazy_split(' ')) {
    for (char c : inner_range) {
      std::cout << c;
    }
    std::cout << '\n';
  }
}

views::lazy_splitはカスタマイゼーションポイントオブジェクトであり、分割対象のrangeオブジェクトとデリミタを示すrangeオブジェクトを受け取りそれを転送してlazy_split_viewを構築して返します。

任意のシーケンスによる任意のシーケンスの分割

実のところ、lazy_split_viewはとてもジェネリックに定義されているため分割対象は文字列に限らず、デリミタもまた文字だけではなく任意のrangeを使用することができます。

たとえば、文字列を文字列で分割することができます。

#include <ranges>

int main() {
  const auto str = std::string_view("1, 12434, 5, 0000, 3942");

  // カンマとホワイトスペースで区切りたい
  // そのままだとナル文字\0が入るのでうまくいかない
  for (auto inner_range : str | std::views::lazy_split(", ")) {
    for (char c : inner_range) {
      std::cout << c;
    }
    std::cout << '\n';
  }

  std::cout << "------------" << '\n';

  // デリミタ文字列を2文字分のシーケンスにする
  for (auto inner_range : str | std::views::lazy_split(std::string_view(", ", 2))) {
    for (char c : inner_range) {
      std::cout << c;
    }
    std::cout << '\n';
  }
}

デリミタに任意のシーケンスを使用できるので、std::vectorをstd::listで分割することもできます。

#include <ranges>

int main() {
  // 3つ1が並んでいるところで分割する
  std::vector<int> vec = {1, 2, 4, 4, 1, 1, 1, 10, 23, 67, 9, 1, 1, 1, 1111, 1, 1, 1, 1, 1, 1, 9, 0};
  std::list<int> delimiter = {1, 1, 1};
  
  for (auto inner_range : vec | std::views::lazy_split(delimiter)) {
    for (int n : inner_range) {
      std::cout << n;
    }
    std::cout << '\n';
  }
}

実際このようなジェネリックな分割が必要になる事があるのかはわかりません・・・

ジェネリックなlazy_split_viewのrangeは外側も内側も同じカテゴリとなり、元となるシーケンス（分割対象のシーケンス）がforward_range以上であるときにのみforward rangeとなり、それ以外の場合はinput rangeとなります。

文字列への変換

lazy_split_viewはほぼほぼ文字列に対してしか使わないと思われますが、分割結果を文字列で受け取ることができません。

#include <ranges>

int main() {
  using namespace std::string_view_literals;
  const auto str = "split_view takes a view and a delimiter, and splits the view into subranges on the delimiter."sv;

  for (auto split_str : str | std::views::lazy_split(' ')
                            | std::views::transform([](auto view) {
                              return std::string{view}; // できない
                              return std::string{view.begin(), view.end()}; // ダメ 
                            })
  ) {
    std::cout << split_str << '\n';
  }
}

lazy_split_viewの内側rangeは単純なViewであって、std::stringへの暗黙変換を備えていません。そして、内側rangeはbegin()/end()のイテレータ型が同じ型を示すcommon_rangeではありませんので、C++17以前の設計のイテレータ範囲から構築するコンストラクタからは構築できません。かといって1文字づつ読んでstd::stringに入れる処理を書くのは忍びない・・・

<ranges>にはこのような時のためにcommon_rangeではないrangeをcommon_rangeに変換するViewが用意されています（次次回紹介予定）。それを用いれば次のように書くことができます。

#include <ranges>

int main() {
  using namespace std::string_view_literals;
  const auto str = "split_view takes a view and a delimiter, and splits the view into subranges on the delimiter."sv;

  for (auto split_str : str | std::views::lazy_split(' ')
                            | std::views::transform([](auto view) {
                              // common_viewを通してイテレータ範囲からコピーして構築
                              auto common = std::views::common(view);
                              return std::string{common.begin(), common.end()};
                            })
  ) {
    std::cout << split_str << '\n';
  }
}

lazy_split_viewはViewであるので元のシーケンスをコピーして処理したりしておらず、その内部イテレータの参照する要素は元のシーケンスの要素そのものです。したがって、文字列の場合はstd::string_viewを用いることができるはずです。

#include <ranges>

int main() {
  using namespace std::string_view_literals;
  const auto str = "split_view takes a view and a delimiter, and splits the view into subranges on the delimiter."sv;

  for (auto split_str : str | std::views::lazy_split(' ')
                            | std::views::transform([](auto view) {
                                auto common = std::views::common(view);
                                return std::string_view(&*common.begin(), std::ranges::distance(common));
                              })
  ) {
    std::cout << split_str << '\n';
  }
}

ただ、ここでviews::transformの引数に来ているviewは内部rangeであり、文字列の場合それはforward_rangeです。そのため、その長さを定数時間で求めることができません。std::stringで動的確保してコピーしてよりかは低コストだとは思いますが・・・

これらの絶妙な使いづらさはlazy_split_viewが遅延評価を行うことに加えてとてもとてもジェネリックに設計されていることから来ています。このことは標準化委員会の人たちにも認識されていて、lazy_split_viewの主たる用途は文字列の分割なのだから、汎用性を捨てて破壊的変更をしてでも文字列で扱いやすくしよう！という提案（P2210R0）が提出されています（まだ議論中です）。

C++20に向けてP2210R2が採択され（これはC++20への欠陥報告として遡ってC++20に適用され、歴史修正されました）、lazy_split_view（元split_view）は文字列分割に特化した新split_viewと上記の振る舞いを維持するlazy_split_viewへと分割定義されることになりました。従って、文字列分割にはsplit_viewを使用すると良いでしょう。

Discussion