範囲の概念、パート 4/4:無限とその先へ

前回は、Iterable という新しい概念を導入し、反復子スタイルの範囲のペアに関する多くの問題を解決する方法を示しました。今回は、Iterable を小さな方法で拡張して、無限範囲でのプログラミングをより安全かつ効率的にします。免責事項:この投稿のアイデアは、前の 3 つよりも推測に基づいています。議論を楽しみにしています。

おさらい

前に、反復子のペアで無限範囲と区切られた範囲を表すときに発生する問題について説明しました。最初の 3 つは次のとおりです。

<オール>
  • 反復が遅い
  • 範囲は、他の方法よりも弱い概念をモデル化することを余儀なくされています
  • 実装がぎこちない
  • この問題に対する私の解決策は Iterable の概念です。つまり、範囲の終わりが範囲の始まりとは異なる型を持つことを許可します。許可したら:

    <オール>
  • センチネル性が C++ 型システムでエンコードされているため、実行時にチェックする必要がないため、パフォーマンスが向上します。
  • 範囲がモデル化できる概念は、センチネルによってモデル化できる概念によって制限されなくなりました。センチネルは、まさにその定義により、デクリメントまたは逆参照できません。
  • センチネル性はコンパイル時のプロパティになり、明示的にチェックする必要がないため、イテレータ比較のロジックがより単純になります。
  • 特に無限範囲で発生する問題がさらに 2 つあります。それらは:

    <オール>
  • 一部の STL アルゴリズムは、無限の範囲では機能しません
  • 無限またはおそらく無限の範囲は difference_type をオーバーフローします
  • これらは、この投稿で焦点を当てる問題です。

    無限のイテラブル

    iota_range 整数の無限の範囲であり、ある値から始まり、無限にカウントアップします。 (iota_range とします。 無限精度の整数型を使用するため、実際には終了しません。) ソートされた前方範囲です。二分探索アルゴリズムはソートされた順方向範囲で機能するため、iota_range でも機能するはずです 、 右?違う!無限を分割して征服することはできません。 (あなたはそれについて私を引用することができます。)

    標準のアルゴリズムをより安全にして、無限の範囲で機能しないアルゴリズムを渡すとコンパイルに失敗するようにすることはできますか? STL の現在の定式化では、答えはノーです。同じ型の 2 つの反復子がある場合、それらが無限の範囲を示しているかどうかをコンパイル時に判断する方法はありません。少し考えてみてください:以下は完全に問題なく、終了することが保証されています:

    // OK, this finishes quickly
    iota_range<bigint> rng;
    auto i = std::lower_bound(rng.begin(),
                              std::next(rng.begin(), 10),
                              5);
    

    ただし、以下は永久に実行されます:

    // Oops! this runs forever. :'-(
    iota_range<bigint> rng;
    auto i = std::lower_bound(rng.begin(),
                              rng.end(),
                              5);
    

    rng.begin() の場合 rng.end() と同じ型です 、これらの 2 つの呼び出しは lower_bound の同じインスタンス化に解決されます . lower_bound はありえない 永久に実行されるかどうかを判断します。しかし、sentinel の型が異なることを許可すると、コンパイル時のチェックが強化されます。どのように?型のペア (BeginType、EndType) を取り、シーケンスが無限かどうかを示す DenotesInfiniteSequence と呼ばれる型関数 (別名メタ関数) があるとします。 BeginType と EndType が同じ場合、DenotesInfiniteSequence は認識できないため、常に false を返さなければならないことを既に確立しています。しかし、それらが異なる場合 — たとえば、EndType が unreachable_sentinel という特殊な型である場合 または何か — すると、シーケンスが無限であることをコンパイル時に知ることができます。

    したがって、Iterable の概念は、無限の範囲をテストする方法を自然に提供してくれますよね?さて…

    無限の範囲

    一部の範囲は、開始イテレータと終了イテレータが同じ型であっても、真に無限である可能性があります .私たちもそれらを捕まえたいです。考慮事項:

    // An infinite range of zeros
    class zeros : public range_facade<zeros>
    {
        friend range_core_access;
        struct impl
        {
            bool sentinel;
            int current() const { return 0; }
            void next() {}
            bool equal(impl that) const
            { return sentinel == that.sentinel; }
        };
        // begin() and end() are implemented by range_facade
        // in terms of begin_impl and end_impl. They will 
        // have the same type.
        impl begin_impl() const { return {false}; }
        impl end_impl() const { return {true}; }
    };
    // zeros models the Range concept
    CONCEPT_ASSERT(Range<zeros>());
    
    int main()
    {
        // Oops! This will run forever.
        for_each(zeros(), [](int i) {/*...*/});
    }
    

    可能であれば、このような間違いを検出できるようにしたいと考えていますが、明らかに、上で仮定したバイナリ DenotesInfiniteSequence 型の関数では対応できません。 zeros の場合 の場合、型 BeginType と EndType は同じであるため、DenotesInfiniteSequence は false を返します。それでも zeros は無限です。

    したがって、(BeginType,EndType) ペアを取る DenotesInfiniteSequence 型関数の代わりに、範囲型を取る単項 IsInfinite 型関数を用意しましょう。もっと簡単なことは何ですか?コードでは、それは型の特徴になります:

    // Report whether an Iterable is infinite or not
    template<typename Iterable>
    struct is_infinite
      : std::integral_constant<bool, true-or-false>
    {};
    

    この型特性は、次のように概念 FiniteIterable を定義するために使用できます:

    // Current proposed Concept Lite syntax
    template<typename T>
    concept bool FiniteIterable =
        Iterable<T> && !is_infinite<T>::value;
    

    (なぜ InfiniteIterable ではなく FiniteIterable なのか? 理由はすぐに説明します。) すべての FiniteIterable は Iterable です。実際、Ranges の場合と同様に、ここには並列の絞り込み階層があります。

    有限反復可能な概念階層

    Range と同様に、これらすべての概念をコードで実際に定義する必要はありません。 「有限性」は Iterable の概念階層と直交しており、個別に照会できます。

    では、なぜ InfiniteIterable ではなく FiniteIterable なのか?それは、アルゴリズムとその要件に帰着します。 必要なアルゴリズムはありません それらの範囲引数は無限であること。だから requires InfiniteIterable<T> と言えます 役に立たない。しかし、lower_bound のようなアルゴリズム それが動作している範囲に明確な終わりがあることを要求したいと思います。したがって、FiniteIterable.

    現在、反復可能なものはすべてデフォルトで FiniteIterable をモデル化しており、型は無限であることを選択する必要があります。どのように? 1 つの方法は、is_infinite を特殊化することです。 .便宜上、イテラブルと範囲を構築するためのユーティリティは、オプションの IsInfinite テンプレート パラメータなので、オプトインは簡単です。 zeros の方法は次のとおりです。 現在の外観:

    // An infinite range of zeros
    class zeros : public range_facade<zeros, true>
    {   // ... IsInfinite ...................^^^^
        // ... as before ...
    };
    // zeros is a Range but it's not Finite
    CONCEPT_ASSERT(Range<zeros>());
    CONCEPT_ASSERT(!FiniteIterable<zeros>());
    

    FiniteIterable の概念が追加されたことで、有限性を必要とするアルゴリズムはコンパイル時に簡単にチェックできるようになりました。これはのみ 範囲ベースのインターフェースで可能であるため、範囲がイテレータよりも優れている長いリストにこれを追加できます。

    おそらく無限の範囲

    有限範囲を無限範囲から分離する方法が得られたら、範囲を分類する必要があります。これは単純なはずです。範囲が有限であるか、そうでないかのどちらかですよね?実際にはそれよりもトリッキーです。たとえば、istream の範囲を考えてみましょう。 かもしれない 無限になるか、そうでないかもしれません。あなたは知りません。ほとんどの場合、ストリームは最終的に枯渇し、反復は停止します。実際、ほぼ常に。でも時々…

    これは厄介な状況です。 可能性があるという理由だけで、istream の範囲をアルゴリズムに渡すことを禁止する必要がありますか? 永遠に続く?答えはイエスだと思いますが、まだ決心していないことを告白します。もっと現実世界での使用が必要だと思います.

    数えられないものを数える

    範囲が無限にあると、固有の問題に直面します。すべてのイテレータ — ひいてはすべてのイテラブル — には difference_type が関連付けられています。 . Alex Stepanov は、イテレータの difference_type について次のように述べています。 :

    無限シーケンスに対するイテレータでは、サクセサを無限に適用できるため、十分な大きさの整数型が必要です…まあ、無限に大きいです。この問題に解決策はありますか?屋根の上のバイオリン弾きのテヴィエの言葉のように、「教えてあげる…。わかりません。」

    洞察のひらめきはありません。代わりに、この問題に関する私の脳のコア ダンプを次に示します。

    <オール>
  • C++ には bigint が必要です 、無限精度の整数型。他の言語にはそれがあります。 C++ はライブラリを構築するための優れた言語であり、これはライブラリ ソリューションを切望しています。そのようなタイプが存在する場合、無限範囲はそれを difference_type として選択する可能性があります .これには、少なからぬパフォーマンス ヒットが伴います。
  • 無限の範囲は safe_int を使用できます difference_type として . safe_int int のように動作します 、しかしそれは無限を表すことができます。オーバーフローして undefined-behavior-land に入る代わりに、safe_int 無限にクリップし、そこにとどまります。イテレータの difference_type を許可することに関する 2 つの最大の問題 オーバーフローは未定義の動作であり、何か問題が発生した場合に事後に判断できないことです。 safe_int で を使用すると、UB を回避して、実行時に何か問題が発生したかどうかを確認できます。状況によってはそれで十分かもしれません。これがあなたにとって大きなハックのように感じるなら、それはその通りだからです。
  • safe_int の代替デザイン 無限にクリップするのではなく、オーバーフロー時に例外をスローする可能性があります。状況によっては、これが適切な場合もあります。
  • もう 1 つの方法は、ライブラリが difference_type を使用している場所を調べることです。 また、別の型を使用するように指定する方法をユーザーに提供します。たとえば、範囲ベースの distance の API アルゴリズムは、範囲とオプションで開始カウントを取る場合があります。デフォルトは difference_type{0} です 、しかし、たとえば bigint を渡した場合 より安全で低速なコードを選択することになります。
  • その問題は無視して構いません。オーバーフローを心配するユーザーは counted range adaptor を使用できます difference_type の前に繰り返しが停止することを確認する オーバーフロー。
  • 思いもよらなかったこと
  • これが私の意見です:不必要なランタイム オーバーヘッドを導入するものは好きではないので、std::ptrdiff_t difference_type の許容可能なデフォルトです .さらに、ユーザーが別の difference_type を指定できるように、範囲ベースのインターフェイスを設計する必要があります。 オーバーフローが懸念される場合。したがって、基本的には、オプション (4) と (5) を使用します。その他のライブラリ タイプ — bigint おそらくポリシーベースの safe_int — ユーザーにとって意味のある安全性と速度のトレードオフを得るために、ユーザーがこれらのアルゴリズムに渡すことができると便利です.

    それは私が持っている最高のものです。

    まとめと次のステップ

    範囲の概念に関する最初の 3 回の投稿の後、すべてが適切な位置に収まったように感じていたのに、今は混乱しているかもしれません。しかし、私たちは良い場所にいると思います。以前よりもはるかに優れています。イテレータ範囲のペアに関する 5 つの問題について説明しました。新しい概念である Iterable は、そのうちの 3 つに非常にうまく対処しています (遅い反復、必要以上に弱い概念のモデル化、ぎこちない実装)。 4 番目の問題 (無限範囲) は、Iterable をさらに改良することで対処できます。そして、5 番目 (オーバーフロー) を処理するためのオプションがいくつかあります。これは、無限の範囲と有限の範囲を区別できることによって助けられます。そこでも新しい概念が役立ちます。これは有望なスタートだと思います。

    これらのアイデアを C++ 標準化委員会に持ち込む予定があるかどうかを尋ねる人もいます。確かに、私はそうです。 いつ 概念の言語サポートが得られた場合 (場合、いつではありません)、STL の新しい概念化されたバージョンが、おそらく別の名前空間でプッシュされる可能性が非常に高くなります。この大規模な書き直しは、絶好の機会です Iterable のようなものを初日から STL に焼き付けたおかげです。

    私の次のステップは、SG9 (Ranges) メーリング リストで議論を開始することです。論争になる可能性が高く、これらのアイデアが進化することを期待しています.メーリングリストへの登録とディスカッションへの参加を検討してください。

    補遺

    Sean Parent が私のブログにコメントし、カウント アルゴリズムの重要性について興味深い指摘をしてくれました (例:copy_n )。彼は、私が提案したソリューションよりも効率的にカウント範囲をサポートする方法を見つけるよう私に挑戦しました。私はこの問題についていくつかの最初の考えを書き上げてここに公開します。いずれにせよ、私以外の頭脳がこの問題に取り組む時が来ていることは明らかです. C++17 はあなたが思っているよりも近くにあり、時間は無駄です!

    x

    1.ステパノフ、A。 McJones、P. プログラミングの要素 .アディソン・ウェズリー。 2009.↩