無限の間隔
無限の間隔の必要性を正当化するのはより困難です。 C ++プログラマーが無限に遭遇することはめったにありません。 他の言語では、これは常に起こります。 Haskellでは、単に[1 ..]と入力するだけで、無限の整数リストを作成できます。 オンデマンドで作成されるアイテムは単なる「遅延リスト」です。 すべての無限間隔は遅延しています。
なぜこれが必要なのでしょうか？ アルゴリズムで、別の要素のN個の最初の要素の新しいリストを作成するとします。 または、無限リストを有限リストで「接着」したい場合。 次に、要素のペアの最終リストを取得します。 これは完全に通常の慣行です。
一般的なライブラリで無限のリストをサポートするのは素晴らしいことです。
無限間隔/ STLで
無限区間は、制約条件が常にfalseを返す区切り区間として想像できます。 これを念頭に置いて、指定された数で始まり「never」で終わる整数の無限リストを実装します。
struct iota_range { private: int i_; public: using const_iterator = struct iterator : boost::iterator_facade< iterator, int const, std::forward_iterator_tag > { private: bool sentinel_; int i_; friend class boost::iterator_core_access; friend struct iota_range; iterator(int i) : sentinel_(false), i_(i) {} bool equal(iterator that) const { return sentinel_ == that.sentinel_ && i_ == that.i_; } void increment() { ++i_; } int const & dereference() const { return i_; } public: iterator() : sentinel_(true), i_(0) {} }; constexpr explicit iota_range(int i = 0) : i_(i) {} iterator begin() const { return iterator{i_}; } iterator end() const { return iterator{}; } constexpr explicit operator bool() const { return true; } };
このリストを使用すると、次のことができます。
// Spew all the ints. WARNING: THIS NEVER ENDS! for( int i : iota_range() ) std::cout << i << 'n';
iota_range-直接間隔; つまり、その反復子はForwardIteratorモデルに基づいて構築されます。 整数と、反復子がシグナルかどうかを示すブール値を格納します。 開始反復子はシグナルではありませんが、終了はシグナルです。 したがって、それらが等しくなることは決してなく、年齢の整数をカウントします。
無限への道のりで起こったこと
ただし、このような間隔で作業すると、何かが期待どおりに機能し、何かがハイパースペースに飛んで戻りません。 簡単な例：std :: distance。 次のことをしないように十分に賢くなければなりません：
iota_range iota; // Oops! auto dist = std::distance(iota.begin(), iota.end());
一般に、このような間隔をバイナリ検索アルゴリズム（binary_search、lower_bound、upper_bound、equal_range）に渡してはならないことはそれほど明白ではありません。 iota_rangeは前方に並べられた間隔であるという事実にもかかわらず。 バイナリアルゴリズムは間隔を分割し、出力で無限の間隔を分割すると、無限の間隔が得られます。 待つのに長い時間がかかります。
性能
最後の投稿の読者は、iota_range :: iterator :: equalの実装に悩まされている可能性があります。 iota_rangeはその繰り返しで停止しないため、終了条件は一定でなければなりません。 代わりに、次のことを行います。
bool equal(iterator that) const { return sentinel_ == that.sentinel_ && i_ == that.i_; }
ゼロになるはずの2つのチェック！ 前回、これが生成されたコードに望ましくない影響をもたらすことを示しました。
可能な無限の間隔
無限ループの問題に加えて、残念ながらSTLには別の問題があります。 私の大好きな鞭打ち少年std :: istream_iteratorを使ってください。 これは入力反復子であるため、difference_typeをそれに関連付ける必要があります。 「プログラミングの要素」という本で、アレクサンダーステパノフ（STLおよびジェネリックプログラミングの父）は次のように述べています。
DistanceTypeは、有効なアクセサーのアプリケーションシーケンスを測定するのに十分な大きさの整数型を返します。
istream_iteratorの場合、difference_typeはstd :: ptrdiff_tになります。 次のコードを検討してください。
std::istream& sin = ...; std::istream_iterator<char> it{sin}, end; std::ptrdiff_t dis = std::distance(it, end);
コードは有効で論理的です。 彼はistreamからシンボルを取り出し、それらをカウントし、それらを取り除きます。 sinがネットワークから文字を受け取り、このコードが数日間実行され、数十億の文字を受け取ると想像してください。 ptrdiff_tが結果に対して十分に大きくない場合はどうなりますか？ 回答：未定義の動作。 実際には、ごみですが、原則としてすべてです。
これは私には少し混乱しています。 イテレーターの場合、difference_typeは、2つのイテレーター間のギャップを含めるのに十分な大きさでなければなりません。 入力ストリームには原則として境界がないため、十分な大きさの符号付き整数はありません。 istream_iteratorインクリメント操作の有効性は、difference_typeのサイズによって制限されるか、difference_typeが正しく設定されないことを認める必要があります。
予備的結論
無限の間隔は便利ですが、STLでの定義方法に問題があります。 無限の間隔は禁止される可能性がありますが、問題はそれ以上です。 そして今日、いくつかの問題が存在します。 STLのdifference_typeオーバーフローの問題を修正することは困難ですが（注意を促すことは除きます）、インターバル用の新しいインターフェースが役立つかどうか疑問に思われるかもしれません。
以下は、STLの原則に基づいて、2、3のイテレーターで間隔を置いて出会ったすべての問題です。
- 区切られた間隔と無限の間隔は不良コードを生成し、
- 彼らは可能な限り弱い概念をモデル化しなければなりません。
- 彼らは使いにくいです
- 消化しないアルゴリズムに無限の間隔を渡すのは非常に簡単です。
- 間隔が無限または非常に大きくなると、difference_typeでオーバーフローが発生する可能性があります。
次の投稿では、これらすべての問題の根本にある、新しい間隔ライブラリの概念の基本について説明します。 切り替えないでください。
繰り返しになりますが、最後にたどり着いた人たちへの小さなプレゼントです。 Infinite Rangesプロモーションコードの30％割引でさらに5つのチケット
UPD：公正な発言により、 VoidExはzipに関するパッセージを修正しました。 よろしくお願いします！
その他のサイクル記事
C ++の間隔、パート1：区切り記号付きの間隔
C ++の間隔、パート3：インクリメントの導入（反復可能）
C ++の間隔、パート4：無限大まで