Boost Range LibraryのOven拡張

このエントリは、Boost Advent Calendar 2011の参加記事です。


Boost Range Libraryは、Boost 1.43.0においてバージョン2にメジャーバージョンアップし、Rangeに対するアルゴリズムと、Rangeアダプタという大きく2つの機能が導入されました。


Rangeアルゴリズムは、既存のイテレータの組みを引数にとるSTLアルゴリズムを一段抽象化し、コンテナや配列のようなRange(範囲)をとるようにしたものです。

std::vector<T> v;
for_each(v, f);

これによって、「コンテナ全てにアルゴリズムを適用する」というような処理が簡潔に記述できるようになり、

for_each(a.begin(), b.end(), f);

のように、間違って異なる変数を範囲として渡してしまうようなバグを埋め込む可能性を減らしてくれます。


Rangeアダプタは、Rangeに対する複数の操作を合成し、Rangeを遅延評価的に操作する機能です。これによって、「Rangeの要素のうち、条件一致したもののみを処理する」といったよくある処理を簡潔に記述できるようになりました。

// 述語pを満たす要素のみ関数fを適用する
for_each(v | filtered(p), f);


ここまでできて大変便利になったBoost Range Libraryですが、圧倒的にRangeアダプタが不足しているのが現状です。
id:mb2sync さんから私が引き継いだOven Range Libraryでは、およそ考えうるあらゆるRangeアダプタが揃っていてBoost.Rangeより圧倒的に便利なのでなんとかしたいですね。


前置きが長くなりましたが、現在私の方で、Ovenの有用なRangeアダプタをBoost.Rangeに移植するプロジェクトを進めています。
このOven拡張を導入することにより、Boost.Rangeは多くの場面で活用できるようになります。たとえば、以下は素数列を作るプログラムです:

typedef
    boost::any_range<int, boost::single_pass_traversal_tag, int, std::ptrdiff_t>
range;

using boost::lambda::_1;
using namespace boost::adaptors;
using boost::range::access::value_front;

range sieve(range r)
{
    return r | dropped(1) |+ filtered(_1 % value_front(r) != 0);
}

range primes = boost::iteration(range(boost::iteration(2, boost::regular(_1 + 1))), sieve)
                     | transformed(value_front);

assert(boost::equal(
    primes | taken(5),
    boost::assign::list_of(2)(3)(5)(7)(11)
));

ここで使用しているOvenから移植された機能は、

  • 無限数列を作り出すiteration Range
  • Rangeから先頭N個の要素を取り除くdropped Rangeアダプタ
  • Rangeから先頭N個の要素を取り出すtaken Rangeアダプタ
  • Rangeの先頭要素を取り出すvalue_front Rangeアルゴリズム
  • ラムダ式をRangeアダプタに渡すことを可能にするregular関数

です。


その他に、regular関数の冗長性を取り除くための、regular演算子operator|+()も新たに導入しています。
regular関数は、ラムダ式をデフォルトコンストラクト可能かつコピー代入可能な形式に変換するための関数です。使用例を見てみましょう。以下は、Rangeの要素から、特定のメンバ変数のみを抽出する処理です。

struct X {
    int a;
    std::string s;
    X(int a_, const std::string& s_) : a(a_), s(s_) {}
};

struct disper {
    template <class T>
    void operator()(const T& x) const
    {
        std::cout << x << std::endl;
    }
};

int main()
{
    const std::vector<X> v = boost::assign::list_of
        (X(1, "a"))
        (X(2, "b"))
        (X(3, "c"))
        ;

    using boost::lambda::_1;
    boost::for_each(v | transformed(regular(&_1 ->* &X::s)), disper());
}
a
b
c

ここでは、Boost.Lambdaのメンバポインタ機能を使用してXクラスのメンバ変数sを抽出していますが、
関数オブジェクトを簡潔に記述するためのラムダ式が、regularによってだいぶ長くなってしまいました。


この冗長性を解決するのがregular演算子operator|+()です。

boost::for_each(v |  transformed(regular(&_1 ->* &X::s)), disper()); // regular関数
boost::for_each(v |+ transformed(&_1 ->* &X::s),          disper()); // regular演算子

regular演算子は、Rangeアダプタに渡された関数オブジェクトを演算子によってregular化するためのものです。Rangeアダプタを繋げるために使用するパイプ演算子operator|()に少し手を加え、間に処理を埋め込んでいます。


regular演算子は、operator|()と単項operator+()を組み合わせた複合演算子というかなり異色なものであるため、Boostに提案する際に大きな論点になりそうですが、今のところこれ以上の案はなさそうなので、このまま提案してみるつもりです。


Ovenの移植プロジェクトは、Boost本家のメーリングリストでも期待されているため、早々に提案まで持っていきたいと考えています。現在は、実装が終わり、日本語ドキュメントが書き終わり、残りはドキュメントを英訳すれば提出できる、という状況になっています。


移植は段階的に行う予定で、まずはOvenの汎用的な用途のRangeアダプタと、無限数列のためのiteration Range、regular演算子を導入するつもりで、その後RangeのRangeを扱うためのアダプタや、残りのRangeアダプタを導入していこうと考えています。


レビューやパッチの送付は随時受け付けています。
ソースコードやドキュメントは、以下の私のGitHubリポジトリから参照することができます。

OvenToBoost - GitHub


私のBoost Advent Calendar、1日目の記事はこれでおしまいです。
2日目のid:kikairoyaさんにバトンタッチします!