大人のための内部boolinq

この記事は、前回の投稿からboolinqライブラリーの実装に興味のある人向けです。 この記事では、ソースを掘り下げ、ライブラリを「遅延」させて拡張可能にする興味深いトリックをいくつか示します。

イテレータの何が問題になっていますか？

ライブラリコードを調べる前に、STLに注目してください。 これは標準のテンプレートライブラリで、コンテナ、アルゴリズムなどが含まれています。 ライブラリの最も興味深い要素の1つは、エンティティ- イテレータです。 イテレーターは、コンテナーとアルゴリズムの間のレイヤーとして発明されました。 そのため、どのコンテナにも任意のアルゴリズムを適用できます（ほとんどすべて）。



一見、すべてが正常です。 アルゴリズムとコンテナは、中間エンティティ（イテレータ）を介して接続されます。 ただし、コードをよく見ると、これは一見しただけです。

int sum = 0; for (std::vector<int>::iterator it = candles.begin(); it != candles.end(); it++) sum += it->ClosePrice;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一見すると目立たないSTLイテレーターには1つの欠点がありますが、Javaイテレーターにはこのマイナスがありません。

 int sum = 0; Iterator it = al.iterator(); while (it.hasNext()) { it = it.next(); sum += it.ClosePrice; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はい、これらの.begin()



と.end()



は同じエンティティの2つの部分です。 これらの2つの部分を取り、それらを1つのエンティティに結合する場合...言われた-完了（アイデアはAlexandrescuから「Iterators Must Go」のプレゼンテーションから借用された）：

 template<typename TIter> class IterRange { public: typedef typename std::iterator_traits<TIter>::value_type value_type; IterRange(TIter b, TIter e) : b(b), e(e) { } bool empty() { return (b == e); } value_type popFront() { assert(!empty()); return *(b++); } value_type popBack() { assert(!empty()); return *(--e); } value_type front() { assert(!empty()); return *b; } value_type back() { assert(!empty()); TIter tmp = e; return *(--tmp); } private: TIter b; TIter e; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、1つのエンティティがあり、シーケンスにさらに要素があるかどうかを尋ね、要素を要求し、次の要素に移動するように要求できます。 実際、 back()



およびpopBack()



メソッドもpopBack()



ません。



それでは、すべてのライブラリクラスがどのように見えるかを推測することは難しくありません。これらはそのようなRangeのラッパーです。 たとえば、WhereRangeは次のようになります。

 template<typename R, typename F> class WhereRange { public: typedef typename R::value_type value_type; WhereRange(R r, F f) : r(r), f(f) , frontReady(false) , backReady(false) { } bool empty() { if (!frontReady) seekFront(); return r.empty(); } value_type popFront() { if (!frontReady) seekFront(); auto tmp = *this; r.popFront(); frontReady = false; return tmp.front(); } value_type popBack() { //  } value_type front() { if (!frontReady) seekFront(); return r.front(); } value_type back() { //  } private: void seekFront() { while(!r.empty() && !f(r.front())) r.popFront(); frontReady = true; } void seekBack() { //  } private: R r; F f; bool frontReady; bool backReady; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

簡単に言うと、クラスは別のRangeをコンストラクターに取り込み、そこから要素を取得し、各要素が結果の選択に属するかどうかを決定する述語を取得します。 Rangeの「先頭から」および「末尾から」値が見つかるかどうかを決定する2つの変数があります。 seekFront（）およびseekBack（）関数は、次の前面と次の背面を直接検索します。



実際、他のすべてのRangeは似ています。 次の問題は、ドット表記の使用を減らすことでした...

ポイント表記が欲しい

一方では、.NET LINQで使用されているのと同じメソッドを使用したかったのですが、C ++にはC＃のような拡張メソッドがありません。

 int max = arr.Where(...).OrderBy(...).Select(...).Max();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一方、ライブラリを拡張可能にしたいと考えました...そしてここでアイデアを得ました ））Linqクラスはすべての範囲の上にラップされます。シーケンスを変換するメソッドを呼び出すと、Linqで囲まれたクラスがラップされ、Linqクラスがすべての上に残ります



各クラスについて、RangeはMixinラッピングクラスで次のことを行いました。

 template<template<typename> class TLinq, typename R> class WhereRange_mixin { public: template<typename F> TLinq<WhereRange<R,F> > where(F f) const { return boolinq::where(((TLinq<R>*)this)->r,f); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、必要なすべてのMixinからLinqクラスを継承しました。

 template<typename R> class Linq : public SkipRange_mixin<Linq,R> , public TakeRange_mixin<Linq,R> , public WhereRange_mixin<Linq,R> , public SelectRange_mixin<Linq,R> , public ReverseRange_mixin<Linq,R> , public OrderByRange_mixin<Linq,R> // ...   ... { public: typedef typename R::value_type value_type; Linq(const R & r) : r(r) { } bool empty() { return r.empty(); } value_type popFront() { return r.popFront(); } value_type popBack() { return r.popBack(); } value_type front() { return r.front(); } value_type back() { return r.back(); } public: R r; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

要素の順序を逆にする

この機能については別途説明したかったのです。 ダブルリバースシーケンスを本当に打ちたかったという点で注目に値します。 そして、コンパイルエラーではなく、良い方法で打ちます。 クラスコードは非常に単純です。

 template<typename R> class ReverseRange { public: typedef typename R::value_type value_type; ReverseRange(R r) : r(r) { } bool empty() { return r.empty(); } value_type popFront() { return r.popBack(); } value_type popBack() { return r.popFront(); } value_type front() { return r.back(); } value_type back() { return r.front(); } template<typename R2> friend R2 reverse(ReverseRange<R2> r); // smart needed private: R r; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードのすべてはあなたが期待したとおりです。前と後ろで動作するメソッドは逆になりますが、それらの間で友好的な機能は失われました。 そして、彼女はプライベートフィールドまでクロールしやすい-ラップされた範囲、この関数の実際のコードは次のとおりです。

 template<typename R> ReverseRange<R> reverse(R r) { return r; } // Unwrap for double-reverse case template<typename R> R reverse(ReverseRange<R> r) { return rr; // smart }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はい！ 関数は1つではありません-それらは2つあります。 最初のものは、本来どおりに動作します-ReaverseRangeでRangeをラップします（暗黙的なコンストラクター呼び出しがあります）。 反対に、2番目はReverseRangeをデプロイします。 これは、実行時ではなく、コンパイルレベルで発生することが重要です。 しかし、これは最も難しいことではありません。Mixinでこれを描写しようとしたときに、地獄が始まりました。

 template<template<typename> class TLinq, typename R> class ReverseRange_mixin { public: TLinq<ReverseRange<R> > reverse() const { return boolinq::reverse(((TLinq<R>*)this)->r); } }; // Unwrap for double-reverse case template<template<typename> class TLinq, typename T> class ReverseRange_mixin<TLinq,ReverseRange<T> > { public: TLinq<T> reverse() const { return boolinq::reverse(((TLinq<ReverseRange<T> >*)this)->r); } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

繰り返しますが、最初のMixinは異常な処理を行いませんが、2番目のコンパイル段階では、 Linq<ReverseRange<XxxRange<...>>>



型を検出し、 Linq<XxxRange<...>>



ます。 コンパイルされたコードを達成している間に脳が壊れた。

ユーザーはどのようにしてライブラリを拡張できますか

アイデアは次のとおりであり、彼に彼自身の魔法の範囲クラスを作成させてから、他のMixinのイメージと似顔絵にMixinクラスを作成させました。 その後、彼は独自のCustomLinqクラスを作成し、初期シーケンスの作成時にそれを使用します（Linqからの継承は機能しません。MixinsはCustomLinqではなくLinqですべてをラップするためです）。

 boolinq::from<CustomLinq>(arr)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

代わりに：

 boolinq::from(arr)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まあ、ユーザーはこれをすべて行わずにドット表記をまったく使用しなくてもかまいません。 結局、次のようなコードを書くことができます。

 using namespace boolinq; int sum = sum(select(where(from(arr), [](...){...}), [](...){...}));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

性能試験

興味のある人向けにテストを実施します。ランダム変数の分散を考慮します。 最初に、ベクトルのすべての奇数要素の平均値を見つけ、次に平均から奇数要素の標準偏差を計算します。



1. 1億個の擬似ランダム要素を生成します。

 srand(0xDEADBEEF); std::vector<int> vec(100000000, 0); for (unsigned i = 0; i < vec.size(); i++) vec[i] = rand();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2. C ++でアルゴリズムを作成します

 //      double sum = 0; int count = 0; for (unsigned i = 0; i < vec.size(); i++) { if (vec[i] % 2 == 1) { sum += vec[i]; count++; } } double avgValue = sum / count; //       avgValue double disperSum = 0; for (unsigned i = 0; i < vec.size(); i++) if (vec[i] % 2 == 1) disperSum += (vec[i] - avgValue)*(vec[i] - avgValue); double disper = disperSum / count;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

3. boolinqでアルゴリズムを作成します

 //      double avgValue = from(vec).where( [](int a){return a%2 == 1;}) .cast<double>() .avg(); //       avgValue double disper = from(vec).where( [](int a){return a%2 == 1;}) .select([=](int a){return (a-avgValue)*(a-avgValue);}) .cast<double>() .avg();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

C ++コードがイテレータを使用していないと思わないでください。 イテレータを使用してコードを記述しましたが、レイアウトしないでください。まったく同じです。 MS Visual C ++ 2010のリリースでコンパイルし、私のマシンで実行します...

C ++コード	1207ミリ秒
イテレータを使用したC ++コード	1224ミリ秒
Boolinqコード	1564ミリ秒

もちろん、Boolinqは少し（3分の1）を失いますが、これもタスクに依存します。 理論的には、すべてのメソッドを個別にテストする必要があります。 ちなみに、.NET LINQは、サイクルではるかに強力に、相手に負けます。



近い将来、STLとの後方互換性のために、Linqクラスに.begin()



および.end()



メソッドを追加する予定です。