はじめに
長い休憩の後、C ++プログラミングに戻らなければなりませんでした。 C＃の後、varキーワードとlinqクエリを構築する機能が非常に不足していました。 しかし、判明したように、進歩はまだ止まっておらず、私の不在中にC ++ 11の新しいバージョンがリリースされました。 私はクロスプラットフォームプロジェクトに関与し、Linux向けのGCCコンパイラ、Windows向けのVisual Studioおよびmingwに興味がありました。 linqのようなライブラリを見つけようとしてもうまくいきませんでした。私が見つけたのは、膝の上にある生きていないクラフトだけでした。 辞任し、検索を終了しましたが、2012年4月に、私に合ったライブラリを説明するC ++の励ましのLINQ to Objects記事がリリースされました。 実際に試して、そのデバイスを整理したので、私は非効率に失望しましたが、いくつかのアイデアを思いつきました。 あと1つしかありませんでした。同じことを、ブラックジャックのみで記述し、 github.com/drbasic/CppLinqで行い、同時に自動型推論（auto）とラムダ式を整理しました。
このライブラリは、流fluentな構文とラムダ式を使用して、変換グラフを作成できるように設計されています。 これらのグラフは、コピー、完成、結合、つまり C＃の世界のLinq to Objectsプロトタイプにできるだけ近い動作を実装します。 ライブラリ機能は、考え直さずに、C＃から借用し、明示的な左結合と完全結合を追加しました。 ライブラリの重要な制限は、コピーではなく、元のシーケンスの要素へのポインターの変換グラフに沿って移動することです。 これにより、コピーのオーバーヘッドがないため、コレクションの複雑な要素を効果的に処理できますが、これによる元のシーケンスは「仮想」ではないはずです。 つまり 作業の開始までに、元のシーケンスの各要素には一意のアドレスが必要であり、linq変換の操作中に要素をメモリ内で移動しないでください。 一般に、配列、Qtコンテナー、std :: bitsetを除くすべての標準コンテナーがこれに適しています。 困難が生じたのは定数シーケンスでのみであり、実際にはそれらを必要としなかったため、完了しませんでした。 ライブラリが検証され、Visual Studio 2010および2012、gcc 4.8、mingw 4.8が正常にコンパイルされました。 これは、Microsoftコンパイラを制御する最も簡単な方法であることが判明し、gccを幸せにすることははるかに困難であり、内部エラーにより、時にはわかりやすい叫び声がなくてもすべてのコンパイラが落ちました。
戦いに
したがって、CppLinqの使用例では、10個の要素のシーケンスを取得し、フィールドiVal> 5の要素を選択して、フィールドsValでソートし、結果をstd :: vectorに入れます。
TestClass1 data[10]; auto t1 = Linq::from(data) .where([](const TestClass1 &a){return a.iVal >= 5; }) .orderBy([](const TestClass1 &a){return a.sVal; }) .toVector();
この場合、最初にソースデータからのアダプターが作成され、次にフィルター演算子（ソート演算子orderBy）からグラフが作成されます。 この時点では、データアクションはまだ実行されていませんが、toVectorは最終的に処理パイプラインを開始します。これは、次のアルゴリズムに従って動作します。 toVectorは、処理チェーンの最後のフィルターから順番にすべての要素を要求し始め、それらからstd :: vectorを形成します。 チェーンの最後のフィルターはorderByですが、正しく順序付けるためにすべての要素を一度に必要とするため、シーケンスの要素へのすべてのポインターがバッファーに配置され、それらを並べるフィルターを要求します。 whereフィルターには必要な要素を「オンザフライ」で選択する機能があるため、下からシーケンスの新しい要素を要求するたびに、条件を満たすフィルターが見つかるまで、上位のフィルターから要素を要求します。 下からの各リクエストのfromシーケンスアダプタは、次の要素のアドレスを返し、要素が終了すると拒否します。
グラフは、たとえば、実行時に必要なフィルターをチェーンに追加することにより、動的に構築できます。
auto src = Linq::from(data) .where([](const TestClass1 &a){return a.iVal >= 5; }); if (order == ascending) src = src.orderBy([](const TestClass1 &a){return a.sVal; }); else src = src.orderByDesc([](const TestClass1 &a){return a.sVal; }); auto result = src.toVector();
グラフが形成されると、複数の連続したソートを1つのソート操作に結合する最適化が行われます。これにより、要素を比較するすべての機能が結合されます。 たとえば、次の場合、2つのシーケンスソートフィルターを設定しても、1つのソートのみが実行されます。
auto t4 = Linq::from(src1) .orderByDesc([](const TestClass1 &a){return a.sVal; }) .thenBy([](const TestClass1 &a){return a.iVal; }) .toVector();
純粋に学術的な目的で、2つの連続した逆シーケンスが消滅し、チェーン内でフィルターを形成しない場合に最適化が実装されます。 可能であれば、すべてのフィルターは貪欲ではなく、つまり 上位シーケンスから余分な要素を要求しないことが可能な場合、作業は「車輪から」実行されます。 しかし、データが受信され、おそらく再び必要になる場合、上位フィルターから要素を取得するコストは不明であるため、上位フィルターへのアクセスを最小限に抑えるために、ポインターは必ず独自のキャッシュに格納されます。 バランスは、次の要素の後にフィルターチェーンに沿ってパスを追加するのではなく、過剰なメモリの使用にシフトします。 さらに、ポインタは要素自体ではなくバッファに格納されるため、適切なシーケンスサイズで大量のメモリを消費することはありません。
結合を実装するとき、演算子==を介して等号、または演算子<を介して等価のシーケンス要素の比較を実装する方法にジレンマがありました。 どちらのオプションにも長所と短所があります。 less操作を適用する場合、最初のシーケンスの各要素を2番目のシーケンスの各要素と比較する必要がないため、両方の入力シーケンスをソートしてより効率的にマージすることができます。 ただし、Linq to Objectsでは、演算子==を使用して特に同等性の比較を実装するのが一般的です。これが、アルゴリズムの複雑さO（n * m）を取得して同じことをした理由です。
どのように機能しますか？
すべての変換メソッドを記述するLinqインターフェイスクラスがあります。 メソッドは、グラフのさらなる構築につながる2つのグループに分けることができ、Linq <？>を返します。例：
template <typename U> Linq<T> where(U f);
そして、グラフの実行を開始する「ターミナル」のもの、例えば：
size_t count(); std::vector<T> toVector();
変換グラフは常に値で指定されますが、これは問題ではありません。ほとんどの場合、ディスプレイスメントセマンティクスを使用した完全なコピーを使用せずに実行できるからです。 たとえば、最初の例では、ディープコピーは発生しません。
興味深いことに、thenByおよびthenByDescの追加の順序付けの操作が行われました。 前の演算子がorderByまたはorderByDescである場合にのみ使用できるため、Linqの子孫が作成され、これらの操作が実行されるLinqOrdクラス、orderByまたはorderByDescメソッドがLinqOrdを返すと宣言されます。
LinqOrd<T> orderBy(); LinqOrd<T> orderByDesc();
したがって、orderBy操作の後、LinqOrd型のオブジェクトが返されます。このオブジェクトには、追加の順序付け操作が既にあります。
Linqクラスの内部には、単一のデータメンバー、Rangeインターフェイスクラスへのポインターがあります。 これは、すべての作業を行う変換グラフのギアです。
template<typename T> class Range { public: Range(){} virtual ~Range(){} virtual bool empty() = 0; virtual T& popFront() = 0; virtual T& front() = 0; virtual void rewind() = 0; virtual Range* clone() = 0; };
インターフェースは非常にシンプルで、概して一方向のイテレーターです。 empty（）メソッドは、さらに要素があるかどうかを返します。 popFront（）メソッドはシーケンスの次の要素を取得し、front（）は現在の要素を返します。 rewind（）メソッドは、ポインターをシーケンスの先頭に移動します。 clone（）メソッドは、新しいオブジェクトを作成し、内部フィルターチェーン全体のディープコピーを作成します。
変換操作はRangeインターフェースを実装します。 たとえば、WhereRange <T、F>の操作の変換コードを指定します。 Tは要素のタイプ、Fはフィルタリングに使用されるオブジェクトのクラスです。 この場合、Fには、TまたはTへの参照を受け入れ、要素がフィルタリング条件に一致する場合にtrueを返すメソッドが定義されている必要があります。
template<typename T, typename F> class WhereRange : public Range<T> { public: WhereRange(Range<T> *src, F f) : src_(src) , f_(f) , frontReady(false) { } ~WhereRange() { delete src_; }; bool empty() override { if (!frontReady) seekFront(); return src_->empty(); } T& popFront() override { if (!frontReady) seekFront(); auto &result = src_->front(); frontReady = false; src_->popFront(); seekFront(); return result; } T& front() override { return src_->front(); } void rewind() override { frontReady = false; src_->rewind(); } Range<T>* clone() override { auto result = new WhereRange(CloneRange(src_), f_); return result; } private: Range<T> *src_; F f_; bool frontReady; void seekFront() { while(!src_->empty() && !f_(src_->front())) src_->popFront(); frontReady = true; } };
さらに多くの作業をコンパイラに任せるために、ラムダ式では、decltypeキーワードを使用して要素タイプを自動的に表示できます。 最初の例を次のように書き換えることができます。
TestClass1 data[10]; auto src = Linq::from(data); auto result = src .where([](decltype(src.const_reference()) a){return a.iVal >= 5; }) .orderBy([](decltype(src.const_reference()) a){return a.sVal; }) .toVector();
ご覧のとおり、要素タイプTestClass1はどこにも明示的に表示されません。 便利な場合もあれば、どの種類のタイプを扱っているかを把握するのが難しい場合もあります。
以下のシーケンス結合の例では、中間型もコンパイラによって出力されます。
auto data1 = testData1(); auto data2 = testData2(); auto src1 = Linq::from(data1); auto src2 = Linq::from(data2); auto result = src1 .join( src2, [](decltype(src1.const_reference()) a){ return a.iVal; }, [](decltype(src2.const_reference()) b){ return b.iVal2; }, [] (decltype(src1.const_reference()) a, decltype(src2.const_reference()) b) { return std::make_pair(b.dVal, a.sVal); } ) .toVector(); }
ここで、1番目と2番目のラムダはシーケンスを結合するキーを返し、3番目のラムダは両方のシーケンスの一致する要素から形成された結果を返します。 次に、受信したすべての要素がstd :: vectorに保存されます。
PS gcc 4.7はoverrideキーワードをダイジェストしないため、＃define overrideを指定できます