コンテナ アルゴリズム

アーバナ シャンペーンで開催された C++ 標準化委員会の最近の会議は、範囲に関する私の作業の転機となりました。最終的に、私のプレゼンテーションは好評でした (Herb Sutter は部屋の雰囲気を表現するために「明白な興奮」というフレーズを使用しました) が、物事がそのように進むかどうかはまったく確信が持てず、実際には 11 時間の追加がプッシュされました。上の提案:コンテナー アルゴリズム。

範囲、N4128 時点

C++ 標準ライブラリの既存のアルゴリズムは積極的に動作します。 std::transform の後 たとえば、すべての変換が完了していることを確認できます。一部のアルゴリズムも変化しています。 std::sort を呼び出したとき 、データがソートされました — その場で。

範囲ビューではそうではありません N4128が提案する。これらは、遅延評価され、変化しないのようなものです 他の場所に保存されているデータのカスタム ビューを表示するアルゴリズム。たとえば、次のように言うと:

std::vector<int> ints{1,2,3,4};
auto squared = ints
    | view::transform([](int i){return i*i;});

… 変換のイオタは 1 つも発生していません。 ビューを作成しました これは、反復されると、基になるシーケンスを変更することなく、オンザフライで変換を行います。

アルゴリズムとビューは別の重要な点で異なります。ビューは簡単に構成できます — 変換されたスライスをフィルタリングしますか?問題ない! —しかし、アルゴリズムはそうではありません。アルゴリズムでそのようなことを行うには、反復子と名前付き一時変数をいじる必要があり、おしゃべりなコードを数行必要とします。

失われたピース

要約すると、N4128 の世界では次のようになります。

<オール>
  • 変異はできるが構成はしない熱心なアルゴリズム
  • できない遅延アルゴリズム 変異するがする 作成します。
  • ??!!!!
  • おっと!何かが欠けています。大量の int を読み取り、並べ替えて一意にしたい場合、N4128 では次のようになります。

    extern std::vector<int> read_ints();
    std::vector<int> ints = read_ints();
    std::sort(ints);
    auto i = std::unique(ints);
    ints.erase(i, ints.end());
    

    ブリーチ!私の提案のこの欠点に気づいた人は数人いました。会議の 1 週間前、私はこの問題がすべての取り組みを狂わせるのではないかと真剣に心配していました。迅速な解決策が必要でした。

    コンテナ アルゴリズム

    私がアーバナで提示したソリューションは、コンテナ アルゴリズムです。 .これらは、コンテナのようなものに対して熱心に動作し、それらをその場で変更し、さらに処理するために転送する構成可能なアルゴリズムです。たとえば、read+sort+unique の例は、コンテナー アルゴリズムでは次のようになります。

    std::vector<int> ints =
        read_ints() | cont::sort | cont::unique;
    

    かなり より良い。コンテナ アルゴリズムは積極的に実行されるため、ベクトル and を使用できます。 ベクトルを返します。範囲ビューではそれができません。

    動く例

    移動セマンティクスにより、これらすべてがスムーズに機能します。一時的なコンテナーは、変化するコンテナー アルゴリズムのチェーンに移動されます。そこで、コンテナーは変更されて移動され、次のコンテナー アルゴリズムによって丸呑みされる準備が整います。 (当然のことながら、大きな std::array のように、効率的に移動できないコンテナーでコンテナー アルゴリズムを使用すると、パフォーマンスが低下します。 .そうしないでください。)

    コンテナ アルゴリズムは、値でコンテナを受け入れて返すため 、人々がこれを行って結果に驚かれるのではないかと心配しました:

    std::vector<int> v{/*...*/};
    // Oops, this doesn't sort v:
    v | cont::sort;
    

    このコードの作成者は、これが v をソートすることを期待するかもしれません .代わりに、v コピーされ、コピーはソートされ、結果は無視されます。

    また、コンテナ アルゴリズムに左辺値を渡すことを許可すると、以下のようなコードでパフォーマンス バグが発生する可能性があります:

    // Oops, this isn't very efficient:
    std::vector<BigObject> bigvec{/*...*/};
    bigvec = bigvec | cont::sort | cont::unique;
    

    bigvec cont::sort に渡されたときにコピーされます 値によって。良くないね!別の方法は、コンテナー アルゴリズムに完全な転送を行わせることです。この場合、返されるのは bigvec への参照です。 .それは bigvec に割り当てられます !コンテナをそれ自体に割り当てるのは…奇妙です。動作することは保証されていますが、効率的であることは保証されていません。この間違いを犯しやすいインターフェイスは、悪いインターフェイスです。

    代わりに、私の現在の考えでは、上記のコードはコンパイルに失敗するはずです。コンテナ アルゴリズムには rvalue が必要です コンテナ;コンテナをチェーンに移動またはコピーする必要があります。 range-v3 では、次のようになります:

    using namespace ranges;
    bigvec = std::move(bigvec) | cont::sort | cont::unique;
    

    これにより、パフォーマンスの問題が修正され、move(v) | cont::sort の戻り値の型を無視することが明らかになります。

    また、変更操作のチェーンをコンテナーに適用するためのこの短い形式も提供します。

    bigvec |= cont::sort | cont::unique;
    

    パイプ構文のファンでない場合は、これも機能します:

    cont::unique(cont::sort(bigvec));
    

    これらの構文は両方とも、一時的なコンテナーでの操作を拒否します。

    コンテナとは?

    上記の一連の変更操作をコンテナに適用する次のコード行を考えてみましょう:

    bigvec |= cont::sort | cont::unique;
    

    これはどのように実装されていますか?簡単な答えの 1 つは、以下の同義語にすることです:

    bigvec = std::move(bigvec) | cont::sort | cont::unique;
    

    しかし、すべてのコンテナーが効率的に移動できるわけではないため、これは不必要に非効率的です。代わりに、参照でラップされたコンテナが渡されます。基本的には、次のように実装されます:

    std::ref(bigvec) | cont::sort | cont::unique;
    

    しかし cont::sortcont::unique コンテナです アルゴリズム。では、参照ラップ コンテナもコンテナなのでしょうか。ありえない!

    コンテナは要素を所有し、コンテナがコピーされるときにそれらをコピーします。参照ラップ コンテナーには、これらのセマンティクスがありません。それは範囲です:別の場所に格納された要素を参照する Iterable オブジェクトです。しかし ref(v) | cont::sort 確かにそう

    つまり、コンテナ アルゴリズムの名前が間違っています。範囲が適切な操作を提供する限り、範囲が渡されたときに問題なく動作します。 cont::sort 並べ替えることができる要素を持つ Iterable が必要です。それだけです。誰が要素を所有しているかはまったく気にしません。

    cont::unique 一意でない要素を削除する方法がある限り、要素の所有権にも無関心です。 erase に頼るのではなく 消去を行うメンバー関数、erase を定義できます 任意の Iterable 型をオーバーロードできるカスタマイズ ポイント (無料の関数) として。 erase の適切なオーバーロード 参照ラップ コンテナーの場合、std::ref(v) | cont::unique

    これの興味深い (少なくとも私にとっての) 結果は、コンテナは面白くないということです .代わりに、EraseableIterable のような特定の動作を追加する Iterable の概念を改良することで、さらに先へ進みます。コンテナー アルゴリズムは、適切な動作セットを提供する Iterable を受け入れます。誰がエレメントを所有していようと気にしません。

    まとめ

    この 1 か月間、並べ替え、要素の削除、スライス、挿入などのために、コンテナ アルゴリズムの完全なスイートを range-v3 ライブラリに追加してきました。これらは構成する熱心なアルゴリズムです。私はそれらを「コンテナ アルゴリズム」と呼んでいます。これは、「意欲的で構成可能なアルゴリズム」が口から出てこないためです。これらは完全に満足のいく動作範囲です。所有していないスライス ビューを cont::sort に送信する場合 、ノックアウトしてください。

    コンテナー アルゴリズムは、N4128 の大きな穴を埋めます。彼らは、現在の標準アルゴリズムの使いやすさの問題を解決するために範囲を心から望んでいる多くの委員会メンバーをなだめるために、長い道のりを歩んできました。プレゼンテーションでコンテナ アルゴリズムを除外していたら、アーバナでの反応は数度冷たかったとしか思えません。

    謝辞

    ここで紹介するコンテナ アルゴリズムの設計は、Sean Parent からのフィードバックによって多大な恩恵を受けました。

    更新:

    聞きました! 「コンテナ アルゴリズム」は紛らわしい名前です。それらはコンテナーに限定されていません。とにかく、それは興味深いことではありません。興味深い点は、熱心であることです。 、突然変異構成可能 アルゴリズム。そのすべてを伝える簡潔な言葉はありませんが(AFAICT)、これまでのところ「行動」が最も近いものになっています.これで view::transform ができました (怠け者、非変更) および action::transform (熱心、変異)。完璧ではありませんが、より良いものであることは間違いありません。

    "\e"