C++でStreamライブラリを書いた話

  • 4
    いいね
  • 1
    コメント

はじめに

どうも、いなむのみたまです。

この記事はC++ Advent Calendar 2016の25日目の記事です。

あ…ありのまま起こった事を話すぜ! 俺は文字列のSplitを書いていたと思ったら、いつのまにかStreamを書いていた。 な…何を言っているのかわからねーと思うが、俺も何を考えていたのかわからなかった…

閑話休題。

Cranberries Stream Libraryを作ったので、その話をします。

Streamとは?

今回作ったのはJava8のStreamを真似たものです。
コレクションの集約操作を行うもので、中間操作ではストリームパイプラインが構築され、終端操作が呼び出されるまで計算が遅延されるというものです。

ちなみに、無限ストリームというものがあるのですが、そちらの実装で迷走しました。
結局、C#のLINQの実装を参考にして書きました。

既存のライブラリについて

それっぽいものとしては

なんかがある気がする。

Boost.Range, LINQ for C++は結構いいと思いました。
ただ、Streamsは処理の終了に例外を使っている部分があるので、「おっそーいー!」という感想でした。

Cranberries Stream Libraryの概要

機能は大きく分けて、「ストリームの構築」、「中間処理」、「終端処理」の3種類があります。
ストリームを構築して中間処理をメソッドチェイン、最後に終端処理が呼ばれたらパイプラインが実行される、というものです。

ストリーム構築
  >> 中間処理1() // 遅延評価
  >> 中間処理2() // 遅延評価
  >> 中間処理3() // 遅延評価
  >> 終端処理()  // すべての処理が実行される
  ;

また、有限ストリームと無限ストリームがありまして、有限ストリームはレンジで、無限ストリームはイテレータみたいな扱いです。
有限ストリームはレンジを内包してるだけです。
無限ストリームは無限イテレータなので、ひとつづつ値を取り出してやる必要があるため、適用できる中間操作が逐次操作に限られます。
また、無限ストリームに対して終端処理を実行すると、無限ループにならず、コンパイルエラーになります。
takeやtake_whileで無限ストリームを有限ストリームにすることができます。

実装の話

実際、バグの嵐だった。

Visual Studio 2015 Community で開発していたのですが...
ちょっとメタプロしただけでコンパイラ内部エラーになるぜ。
いや、問題は変数テンプレートだった。
部分適用されてない変数テンプレートを定義するとエラーになる。

こういうやつ

template < template<class, class> class Target >
constexpr convert_to = detail::ConvertTo<Target>{};

幸い、Visual Studio 2017RCで直っていたんで、解決です、神。

一番困ったのが、GCCのコンパイルエラーです。
これなんですが。
もう意味わからなくて、さよならGCCしました。

ストリームの型にオペレーションを埋め込む

オペレーションをストリーム自体にぶち込んでしまおうという発想でやってます。

template <
  typename T,
  typename Operation // ココに処理埋め込んじゃうよ
>
stream{
 // ...
priavte:
  Operation op; // 状態を保存
};

例えば次のようにストリームにフィルターを適用すると、

make_stream::of({1,2,3,4,5})
  >> filtered([](int const& a){ return a%2; })
  ;

ストリームの型がstream<int,Filter>みたいになります。

そして、ドン!

template <
    typename Op1, // evaluate first
    typename Op2  // evaluate next
  >
  struct OperationTree
  {
    template <
      typename Stream
    >
    decltype(auto)
    operator()
    (
      Stream&& stream
    )
      noexcept(false)
    {
      return op2(op1(std::forward<Stream>(stream)));
    }

    // members
    Op1 op1;
    Op2 op2;
  };

オペレーションのペア的な型をつくります。
これで完璧です。
OperationTreeOperatioinTreeをぶち込めばいいのです。

C++1zの機能を使いたくて、自分で書いてしまった

void_t,conjunction,disjunction,negation,invoke,apply,is_callable,bool_constantなどは書いた。

放っておいても、誰かが作ってくれるのにつくってしもうた。
まあ、便利だから仕方ないね。

この辺に書きなぐった記憶が。

メタ関数いっぱい

高階メタ関数みたいなのからちょっとしたものまでいろいろなメタ関数を書きました。
SFINAEでオーバーロードに制限を設けていろいろとやってるうちに量産されていったんですねぇ。

例えば、ストリームのオペレータクラスを判定するメタ関数。

class StreamOperatorBase{}; // 空の基底クラス

template < typename T >
constexpr bool is_stream_operator_v = std::is_base_of<StreamOperatorBase, T>::value;

空の基底クラスを作っておいて、オペレータクラスはすべてこれを継承させる。
するとEBO(Empty Base Optimization)が働き、基底クラスのサイズが0になる。

そうしておいて、is_base_ofを使ってやるとなんか楽です。

メンバ関数を生やす

ストリームのオペレータはoperator>>でメソッドチェインするように作ったのですが、メンバ関数もあったほうがいいかなぁと思いまして、CRTPして生やしました。

以下のようなCRTP用クラスを作ってストリームに継承させます。

template <
  typename Derived
>
struct enable_men_fn
{
  template < typename ...Args >
  decltype(auto) filter(Args&& ...args)
  noexcept( noexcept( filtered(std::forward<Args>(args)...) ) )
  {
    return std::move(*static_cast<Derived*>(this))
      >> cranberries::streams::filtered( std::forward<Args>(args)... );
  }
};

teplate < typename T >
stream : public enable_men_fn<stream<T>>
{
 // ...
};

オペレーションはいっぱいあるし、面倒だから、魔黒して羅列...

#define men_fn_def(men_fn, adaptor_fn)\
template < typename ...Args >\
decltype(auto) men_fn(Args&& ...args)\
noexcept( noexcept( adaptor_fn(std::forward<Args>(args)...) ) )\
{\
  return std::move(*static_cast<Derived*>(this))\
    >> cranberries::streams::adaptor_fn( std::forward<Args>(args)... );\
}

結局こうなった

Radix Sort作った

なんで作ったのかわからんが作った。
整数(負の数OK)、実数、bitsetをソートすることができる。
ソートキーを取得する関数オブジェクトを指定すればなんでもソートできる。

radix_sort.hpp