範囲の概念、パート 2/4:無限の範囲

前回の投稿で、区切られた範囲を STL に適合させようとしたところ、満足のいく結果が得られませんでした。今回は、無限の範囲で同じことを試みますが、残念ながら同じ結論に達します。しかし、演習は、区切られた範囲、無限の範囲、および STL 風のペアとイテレータの範囲を包含する超範囲の概念への道を示します。

無限の範囲

区切られた範囲の動機付けはかなり単純です。 null で終わる文字列のアイデアはよく知られています。無限の範囲の場合は、作るのが少し難しくなります。 C++ プログラマーとして、私たちは定期的に無限にぶつかることはありません。他の言語では、無限は一日の仕事のすべてです。 Haskell プログラマーは、[1..] と入力するだけで、整数の無限リストを作成できます。 .それはあなたの脳を壊しますか?すべきではありません。 怠け者 list — 要素はオンデマンドで生成されます。すべての無限範囲は必然的に遅延します。

それの用途は何ですか? take を検討してください 最初の N から新しいリストを構築するアルゴリズム 別のリストの要素。無限のリストを慎重に処理します。または、zip したときにどうなるかを考えてみましょう 有限リストを持つ無限リスト。要素ペアの有限リストになります。それは完全に賢明なことです。

一般的な範囲ライブラリで無限範囲をサポートすることはメリットになるため、それが概念に与える影響を調べる価値があります。

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 の概念をモデル化します 1 .整数 の両方を格納します。 イテレータがセンチネルかどうかを示すブール値。範囲の開始イテレータはセンチネルではなく、終了イテレータです。したがって、それらが等しく比較されることは決してなく、整数を数えます…永遠に!

無限への道で起こったおかしな出来事

コードでこの範囲を使用すると、期待どおりに機能するものもあれば、ハイパースペースにスピンオフして元に戻らないものもあることがわかります。非常に単純な例を見てみましょう:std::distance .おそらく、あなたはこれを行うほど愚かではないでしょう:

iota_range iota;
// Oops!
auto dist = std::distance(iota.begin(), iota.end());

あまり明確でないのは、binary_search を含む二分探索を行うアルゴリズムに、この範囲を直接的または間接的に、いかなる状況下でも絶対に渡してはならないということです。 、 lower_boundupper_bound 、および equal_rangeiota_range という事実にもかかわらず 実際、ソートされた前方範囲です。考えてみてください。二分探索は分割統治アルゴリズムです。無限の範囲を分割すると、驚きです! — 無限の範囲。 iota_range を渡す場合 これらのアルゴリズムのいずれかに興味がある場合は、コーヒーを飲みに行ってください。しばらくお待ちください。

パフォーマンスの問題

区切り範囲に関する前回のブログ投稿を読んだ場合、iota_range::iterator::equal の実装を見て少しひるんだかもしれません。 . iota_range の反復子は決して反復を終了しないため、終了条件は定数式にする必要があります。代わりに、これがあります:

bool equal(iterator that) const
{
    return sentinel_ == that.sentinel_
        && i_ == that.i_;
}

ゼロになるはずなのに、これは 2 つの実行時チェックです!前回示したように、これは生成されたコードの品質に壊滅的な影響を与える可能性があります。 <悲しい顔>

たぶん 無限の範囲

無限ループは無限範囲の問題の 1 つですが、別のより微妙な問題があり、残念ながら標準ライブラリには既に存在します。私たちの旧友 (そして私のお気に入りのサンドバッグ) std::istream_iterator を連れて行きましょう .これは入力イテレータなので、関連する difference_type が必要です . 「Elements of Programming」で、アレクサンダー ステパノフ (STL とジェネリック プログラミングの父) はイテレータの差分型について次のように述べています。

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 つの反復子の間の距離を保持するのに十分な大きさにする必要があります。入力ストリームは原則として無制限であるため、no はありません 十分な大きさのスカラー符号付き整数型。は。 istream_iterator の妥当性を結論付けざるを得ません。 のインクリメント操作は、その difference_type のサイズによって制限されます 、またはその istream_iteratordifference_type 間違っている。繰り返します:ふむ。

まとめ、とりあえず…

無限の範囲は便利ですが、STL の現在の定義を考えると実際の問題があります。無限の範囲を許可しないことで問題を回避できると思うかもしれませんが、それはそれよりも根本的なことです。実際、今日いくつかの問題が存在します。 difference_type を修正するのは難しい 今日の STL でのオーバーフローの問題は (人々に注意するように伝えることは別として)、新しい範囲ベースのインターフェイスが役立つかどうかを検討する価値があります。 (期待を高めないように、これは厄介な問題であり、私はまだ優れた解決策を持っていないと言います.)

要約すると、これまでに STL っぽいペアのイテレータ スタイルの範囲で特定した問題は次のとおりです。

  • 区切られた範囲と無限の範囲が不適切なコードを生成する
  • そうでない場合よりも弱い概念をモデル化することを余儀なくされている
  • また、実装するのが面倒です
  • 処理できないアルゴリズムに無限の範囲を渡すのは簡単すぎる
  • おそらく無限の範囲が difference_type をオーバーフローする可能性があります

次回の記事では、これらの問題の根源に迫る新しい範囲ライブラリの概念的基礎について説明します。お楽しみに。

1.実は、これはちょっとした嘘です。前方反復子は、内部のオブジェクトへの参照を返すことは想定されていません。議論のためにこれを無視してください.↩

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

x
x