イテレータ++、パート1

前回の投稿では、いわゆるプロキシ イテレータの問題について説明しました。実際の参照ではなくプロキシ参照を返すイテレータは、STL のフレームワーク内に快適に収まらないという事実です。 03 のような真の、興味深い、有用な反復子は、この行に違反します。 のまたは 15 のイテレータのように 私が提示した見解。この投稿では、プロキシ イテレータを折り畳むために何ができるかを調べます。これは、イテレータの概念とアルゴリズムの両方にとって何を意味するかです。私は図書館好きなので、純粋な図書館の変更について話すことに制限しています。

まとめ

前回の投稿と同様に、28 を使用します 議論を活性化するためのビュー。次のような 2 つのシーケンスが与えられた場合:

vector<int> x{1,2,3,4};
vector<int> y{9,8,7,6};

…2 つを 1 つに「圧縮」することでビューを作成できます。ビューの各要素は、35 の対応する要素のペアです。 と 48 :

using namespace ranges;
auto rng = view::zip(x, y);

assert(*rng.begin() == make_pair(1,9));

式「55」の型 」 — 範囲の参照タイプ66 です 、範囲の値の型は 71 です .参照タイプは proxy の例です :別のオブジェクト、またはこの場合は他の 2 つのオブジェクトの代わりになるオブジェクト。

両方の 89 以降 そして 98 ランダム アクセス、結果の 107 ビューもランダムアクセスにする必要があります。しかし、ここでは STL の「実際の参照」要件に違反しています。入力イテレータ以外のイテレータの場合、式 111 しなければならない 実際の参照を返します。なんで?良い質問!この要件は、STL の標準化中に追加されました。委員会が、それ自体がメモリに永続的ではない要素を並べ替えたり逆にしたりすることの意味を知らなかったためだと推測できます。 (プロキシ) は永続オブジェクトの代役です。 (たぶん、当時の誰かが肯定または否定できるでしょう。)

実参照要件は非常に制限的です。 120 を意味するだけではありません view をランダム アクセス シーケンスにすることはできません。つまり、134 を介して要素を並べ替えたり、逆にしたりすることはできません。 見る。 149 の理由でもあります は実際のコンテナーではありません。

しかし、単に実参照要件を削除するだけでは十分ではありません。また、実際の参照を生成しないシーケンスをソートおよび逆順にするとはどういう意味かについても説明する必要があります。前回の投稿では、プロキシ参照が存在する場合のアルゴリズムの制約と実装に関連する 3 つの特定の問題について説明しました。

<オール>
  • イテレータの値の型とその参照型の関係について何か言えることはありますか?
  • 153 のような高次アルゴリズムをどのように制約するか と 165 シーケンスの要素を操作する関数を取りますか?
  • 174 のように、要素を入れ替えたり移動したりしなければならないアルゴリズムをどのように実装しますか? ?
  • 最初に最後のものを取りましょう。

    要素の交換と移動

    就職の面接で 186 を実装するように頼まれた場合 、次のように書くかもしれません:

    template< class BidiIter >
    void reverse( BidiIter begin, BidiIter end )
    {
        using std::swap;
        for(; begin != end && begin != --end; ++begin)
            swap(*begin, *end);
    }
    

    おめでとうございます、あなたは採用されました。さて、インタビュアーがこのアルゴリズムが 197 で機能するかどうか尋ねたとしたら、 先ほど説明したビューについて、あなたはどう思いますか?ご想像のとおり、答えはノーです。 209 のオーバーロードはありません 214 を受け入れる 右辺値。あったとしても、私たちは 224 で薄氷の上にいます ビューのプロキシ参照タイプ。デフォルトの 236 実装は次のようになります:

    template< class T >
    void swap( T & t, T & u )
    {
        T tmp = move(u);
        u = move(t);
        t = move(tmp);
    }
    

    248 のときに何が起こるか想像してみてください 257 です .最初の行は値を移動しません。 262 275 によって参照される値をエイリアスするだけです .次の行は 289 の値を踏みます 、これは 293 を変異させます 別名だから。次に、踏み込んだ値を 306 にコピーします。 .値を交換するのではなく、両方の値を 315 に等しくします .おっと。

    この時点で、323 と独り言を言っている場合は、 独自の 339 を持っています (ほとんど)正しいことをする過負荷、あなたはとても賢いです。うるさい。しかし、上記が標準準拠の 341 ではないという場合は、 他のすべてのアルゴリズムとは異なり、 351 361 を使用する必要があります 、それからとても良いです!それが、この混乱全体を解明する手がかりです。

    iter_swap

    372 389 の薄いラッパーです 値の代わりに反復子を取り、それらが参照する要素を交換します。 398 以来、これは非常に役に立たない機能です。 409 を呼び出すだけで十分です。 .しかし、それをもう少し賢くするとどうなるでしょうか? 415 の場合 要素を交換する方法をプロキシ シーケンスがアルゴリズムに伝えることを可能にする本格的なカスタマイズ ポイントでしたか?

    427 を想像してみてください ビューのイテレータは 437 を提供しました 基礎となるシーケンスの要素を真に交換する方法を知っていました。次のようになります:

    template< class It1, class It2 >
    struct zip_iterator
    {
        It1 it1;
        It2 it2;
    
        /* ... iterator interface here... */
    
        friend void iter_swap(zip_iterator a, zip_iterator b)
        {
            using std::iter_swap;
            iter_swap(a.it1, b.it1);
            iter_swap(a.it2, b.it2);
        }
    };
    

    440 を実装します。 このように:

    template< class BidiIter >
    void reverse( BidiIter begin, BidiIter end )
    {
        using std::iter_swap;
        for(; begin != end && begin != --end; ++begin)
            iter_swap(begin, end);
    }
    

    ほら! 現在 451 462 で動作します ビュー。それは簡単でした。必要なのは、(a) 470 を宣伝することだけです カスタマイズポイントとして (b) 485 を使用 498 だけでなく、標準ライブラリ全体で一貫して .

    iter_move

    問題はまだ解決していません。一部のアルゴリズムは要素を交換するだけではありません。彼らはそれらを動かします。例えば ​​506 一時バッファを割り当て、動作中に要素をそこに移動する場合があります。 513 は使用できません 要素を raw ストレージに移動します。しかし、520 からのプレイを使用できます。 この問題を解決するためのプレイブック。 530 を作ってみましょう シーケンスから値を移動する方法を反復子に伝達する方法を提供するカスタマイズ ポイント。

    544 のデフォルトの実装はほぼ 些細なこと:

    template< class I,
        class R = typename iterator_traits< I >::reference >
    conditional_t<
        is_reference< R >::value,
        remove_reference_t< R > &&,
        R >
    iter_move( I it )
    {
        return move(*it);
    }
    

    唯一のトリッキーなビットは、戻り値の型の宣言です。 550 の場合 一時的なものを返します。値で返したいだけです。それ以外の場合は、右辺値参照で返します。 561 を渡す場合 573 へ 、あなたは 585 を返します ご想像のとおりです。

    599 はどのように機能しますか ビューの実装 602 ?まったく難しいことではありません:

    template< class It1, class It2 >
    struct zip_iterator
    {
        It1 it1;
        It2 it2;
    
        /* ... iterator interface here... */
    
        friend auto iter_move(zip_iterator a)
        {
            using std::iter_move;
            using RRef1 = decltype(iter_move(a.it1));
            using RRef2 = decltype(iter_move(a.it2));
            return pair<RRef1, RRef2>{
                iter_move(a.it1),
                iter_move(a.it2)
            };
        }
    };
    

    アルゴリズムは 619 を使用できます 次のように:

    // Move an element out of the sequence and into a temporary
    using V = typename iterator_traits< I >::value_type;
    V tmp = iter_move( it );
    // Move the value back into the sequence
    *it = move( tmp );
    

    余談ですが、これは 627 のより一般的なデフォルト実装を示唆しています :

    template< class I >
    void iter_swap( I a, I b )
    {
        using V = typename iterator_traits< I >::value_type;
        V tmp = iter_move( a );
        *a = iter_move( b );
        *b = move( tmp );
    }
    

    632 のようなプロキシ シーケンスになりました 646 を定義するだけです 意味的に正しい 656 を取得します 無料で。デフォルトの 661 に似ています 678 で定義されています . (この方法では、681 のユーザー定義のオーバーロードは検出されません。 .良くないね。回避策はありますが、この投稿の範囲外です。)

    698 の場合 値の型 709 を持つビュー および参照型 714729 の戻り型 731 です .完全に理にかなっています。 740 のデフォルトの実装をもう一度見てみましょう 基礎となるシーケンスに移動のみの値型がある場合でも、圧縮された要素が正しくスワップされることを確認してください。

    754 に関する最後の注意事項 :これは、プロキシされたシーケンスをサポートするために、反復子に追加の 関連型 が必要であることを意味します :763 の戻り型 . 778 と呼ぶことができます 782 に入れます 797 と並んで および 805 .

    別のデザイン

    上記のデザインはすっきりしていて直感的です。しかし、興味深い質問があります:814 でよろしいですか? と 827 意味が違うかも?個人的にはそれでいいと思いますが、そうではないことを少し想像してみましょう。他に何ができますか?

    明らかな代替設計は、830 をオーバーロードすることです プロキシ リファレンスが参照するオブジェクトを交換します。次のオーバーロードを名前空間 843 に追加するとします。 :

    template< class T, class U >
    void swap( pair< T&, U& > && a, pair< T&, U& > && b )
    {
        swap(a.first, b.first);
        swap(a.second, b.second);
    }
    

    十分な SFINAE マジックがあれば、これをさらに一般化して、プロキシ参照のペアの交換をサポートできますが、これに固執しましょう。私はそれと一緒に暮らすことができました。

    しかし、これだけでは十分ではありません。 857 もオーバーロードする必要があります 864 を取る 876 を返します . 881 という理由で、ここから不快になり始めます。 どこでも使用されており、現在のところカスタマイズ ポイントではありません。 890 の型を想定するコードがどれだけ出回っているか 式は です && ?それが真実でなくなったら何が壊れますか?

    純粋にライブラリの進化の問題として、905 をオーバーロードします 参照のペアのその方法は、既存のコードの意味を変更するため、非スターターです。 916 を変更することで問題を回避できます 922 からの参照型 936947 のオーバーロード と 959 その上で。 967 973 から継承します 、したがって、ほとんどのコードは賢明ではありません。完全に有効な設計。

    とりあえずまとめ

    私は口で長く走りましたが、対処すべき問題がまだあと 2 つあるので、別の投稿のために取っておきます。私たちは多くの分野をカバーしてきました。上記の設計では、アルゴリズムは 984 の助けを借りて、プロキシされたシーケンス内の要素を並べ替えることができます そして 994 、イテレータは 1004 と呼ばれるまったく新しい関連型を取得します .

    このデザインを好むか他のデザインを好むかは、どちらが不快かによって異なります:

    <オール>
  • 1015 1020 とは意味的に異なる場合があります 、または
  • 1031 一部のプロキシ右辺値参照型を返すことができるカスタマイズ ポイントです。
  • 次回の記事では、反復子の値の型とその参照型 (および現在の右辺値の参照型) との間の関係について何が言えるか、および 1042 および 1058 .

    いつものように、ここで説明されているすべてのコードは、github の range-v3 リポジトリにあります。

    "\e"