C ++の間隔、パート4：無限大まで

最後の部分では、インクリメンター（Iterable）の概念について説明し、標準間隔に固有の多くの問題を解決する方法を示しました。 次に、このコンセプトを拡張して、無限のインターバルプログラミングをより安全で効率的なビジネスにします。



免責事項 ：この記事のアイデアは、以前のアイデアよりも投機的です。 議論ができて嬉しいです。



以前の投稿で話した解決済みの問題に加えて、さらに2つあります。 これは：

1. 一部のSTLアルゴリズムは無限の間隔で機能しません
2. 無限またはおそらく無限の間隔は、difference_typeオーバーフローにつながります

無限イテレーター

iota_range-ある値から始まり、永久に続く無限の整数の範囲。 これは、ソートされた前方スペースです。 以下は、ソートされたまっすぐな間隔で機能するバイナリ検索アルゴリズムであり、機能しません。 分割によって無限を征服することはできません（良いフレーズが判明しました）。



無限の間隔を受信したときに壊れないようにSTLアルゴリズムを修正することは可能ですか？ 現在の形式では、いいえ-イテレータの一部が無限の間隔を示すというコンパイル段階で情報を伝えることは不可能です。 これについて考えてみてください。次のコードは確実に機能します。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、これは永遠に機能します：

 //   «» :'-( iota_range<bigint> rng; auto i = std::lower_bound(rng.begin(), rng.end(), 5);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

rng.begin（）がrng.end（）と同じタイプの場合、2つの呼び出しは同じlower_boundインスタンスを返します。 関数は、永久に機能するかどうかを判断できません。 ただし、シグナルイテレータを別のタイプにすることができる場合は、コンパイル段階でこのチェックを実行できます。

DenotesInfiniteSequenceと呼ばれる型関数（メタ関数）があり、それが型のペア（BeginType、EndType）を取り、シーケンスが無限かどうかを判断するとします。 BeginTypeとEndTypeが同じ場合、DenotesInfiniteSequenceはfalseを返す必要があることを既に決定しています。これは、これをどのような方法でも検証できないためです。 しかし、それらが異なる場合-EndTypeのタイプがunreachable_sentinelまたはそのようなものになるとすると、コンパイル段階でシーケンスが無限であることがわかります。

無限の間隔

一部の間隔は、定義上、同じタイプの開始反復子と終了反復子を持つこともあり、無限になります。

 //    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()  end()   range_facade //  begin_impl  end_impl.      impl begin_impl() const { return {false}; } impl end_impl() const { return {true}; } }; //    Range CONCEPT_ASSERT(Range<zeros>()); int main() { //  for_each(zeros(), [](int i) {/*...*/}); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このようなエラーをすぐにキャッチしたいのですが、明らかに、バイナリ関数DenotesInfiniteSequenceはこれに対処できません。 ゼロの場合、BeginTypeタイプとEndTypeタイプは同じになるため、DenotesInfiniteSequenceはfalseを返します。



したがって、区間型を受け入れるIsInfinite型の単項関数を作成する必要があります。

 //   ,   Iterable  template<typename Iterable> struct is_infinite : std::integral_constant<bool, true-or-false> {};
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FiniteIterableの概念を定義するために使用できます。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

各FiniteIterableは反復可能です。 改良の並列階層が観察されます。







また、これらの概念はすべて、Rangeとの類推により、コードで定義する必要はありません。 有限性はIterable階層に直交しており、個別に問い合わせることができます。



しかし、なぜInfiniteIterableではなくFiniteIterableなのでしょうか？ アルゴリズムとその要件がすべてです。 間隔引数を無限にする必要があるアルゴリズムはありません。 したがって、InfiniteIterableを記述できても意味がありません。 しかし、lower_boundのようなアルゴリズムは、間隔が有限であることを望みます。 これとFiniteIterableから。



これは、すべての反復子がデフォルトでFiniteIterableをモデル化し、その型が何らかの形で無限であることを学習する必要があることを意味します。 どうやって？ is_infiniteを特殊化することができます。 幸いなことに、インクリメンターとインターバルを作成するツールはオプションのIsInfiniteパラメーターを受け入れるため、これは簡単です。 zeroesクラスは次のようになります。

 //   class zeros : public range_facade<zeros, true> { // ... IsInfinite ...................^^^^ // ...  ,   ... }; // zeros –  Range,    Finite CONCEPT_ASSERT(Range<zeros>()); CONCEPT_ASSERT(!FiniteIterable<zeros>());
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FiniteIterableコンセプトを追加することにより、有限性を必要とするアルゴリズムに、コンパイル段階でこれを検証する機会を与えます。

おそらく無限の間隔

次に、間隔をカテゴリに分割する必要があります。 理論的には、無限または有限のどちらかです。そうではありませんか？ いや istreamを利用してください。 それは有限かもしれないし、そうでないかもしれない。 通常、フローは停止しますが、時には...



状況は複雑です。 istreamのアルゴリズムへの転送を禁止する必要があるのは、それが無限である可能性があるためだけですか？

カウント不可

無限の間隔では、このような困難があります。すべてのイテレータとすべてのインクリメンタには、それらに関連付けられたdifference_typeがあります。 アレクサンダー・ステパノフはこれについて書いています：

DistanceTypeは、その型に有効な後続アプリケーションのシーケンスを測定するのに十分な大きさの整数型を返します。

あらゆるサイズの無限サイズが必要であることがわかりました。 この問題の解決策はありますか？

1. C ++では、bigintが必要です-精度が無限の型全体です。 他の言語ではそうです。 C ++はライブラリを作成するのに最適な言語であり、ライブラリはそれを求めているだけです。 そのようなタイプがあった場合、それはdifference_typeとして取られます。
2. 無限間隔では、safe_intをdifference_typeとして使用できます。 safe_intはintのように動作しますが、無限を表すことができます。 混んでいません。 difference_typeのオーバーフローに関する2つの最も難しい問題は、未定義の動作と、何が間違っていたかを事実を伝えることができないことです。 safe_intを使用すると、不確実性を回避し、後で何が起きるかを回避できます。
3. オーバーフロー時に例外をスローする代替のsafe_int実装が提案される場合があります。
4. また、ライブラリがdifference_typeを使用する場所を確認し、別のタイプがそこで使用されるようにユーザーに指定させることもできます。 たとえば、距離計算アルゴリズムAPIは、間隔とオプションの初期値を取る場合があります。 デフォルトでは、difference_type {0}で動作しますが、bigintを渡した場合は、異なる、より遅いが、より安全な方法で動作します。
5. 問題を無視できます。 そして、オーバーフローを気にする人は、カウントダウン間隔アダプター（https://github.com/ericniebler/range-v3/blob/master/include/range/v3/view/counted.hpp）を使用して確認できます。その繰り返しは、difference_typeがオーバーフローする前に停止します。
6. 私には起こらなかった何か。

もちろん、アルゴリズムの動作を遅くするものすべてが好きではないので、std :: ptrdiff_tはデフォルトでdifference_typeのままにしておくことができます。 さらに、ユーザーがオーバーフローを心配する場合に別のdifference_typeを設定できるように、インターバルインターフェイスを設計する必要があります。 したがって、オプション4と5が好きです。特定の制限を持つbigintやsafe_intのような他のライブラリタイプは、使用できるといいでしょう。

結果と次に何をすべきか

おそらく、前の投稿を読んでいる間、あなたは過度に楽観的でした：すべてがうまくいき始めているようで、今あなたは混乱しています。 しかし、私が始めた場所と比較して、私たちは順調に進歩しているように思えます。 イテレータのペアを使用して、間隔に関する5つの問題を説明しました。 インクリメンターの新しい概念はそれらのうち3つを解決し、4番目の問題（無限間隔）はこの概念を改善することで理論的に解決できます。 また、5番目（オーバーフロー）を処理するためのオプションがいくつかあります。 少なくとも開始されました。



私のアイデアをC ++標準化委員会に伝えたいと思う人もいます。 もちろん。 言語の概念のサポートが得られると、異なる名前空間で動作する可能性のある概念化されたバージョンのSTLが必要になります。



それまでの間、SG9（Ranges）メーリングリスト（http://www.open-std.org/mailman/listinfo/ranges）でこの問題を議論します。 この議論のある問題は、新しいアイデアを生み出す可能性があります。 興味のある方は、ディスカッションに参加することをお勧めします。



著者は彼のアイデアを委員会に持ち込み、現在それらの実装に取り​​組んでいます。

その他のサイクル記事

C ++の間隔、パート1：区切り記号付きの間隔

C ++の間隔、パート2：無限の間隔

C ++の間隔、パート3：インクリメントの導入（反復可能）