前回の投稿では、いわゆるプロキシ イテレータの問題について説明しました。実際の参照ではなくプロキシ参照を返すイテレータは、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
を持つビュー および参照型 714
、 729
の戻り型 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
からの参照型 936
へ 947
のオーバーロード と 959
その上で。 967
973
から継承します 、したがって、ほとんどのコードは賢明ではありません。完全に有効な設計。
とりあえずまとめ
私は口で長く走りましたが、対処すべき問題がまだあと 2 つあるので、別の投稿のために取っておきます。私たちは多くの分野をカバーしてきました。上記の設計では、アルゴリズムは 984
の助けを借りて、プロキシされたシーケンス内の要素を並べ替えることができます そして 994
、イテレータは 1004
と呼ばれるまったく新しい関連型を取得します .
このデザインを好むか他のデザインを好むかは、どちらが不快かによって異なります:
<オール>1015
1020
とは意味的に異なる場合があります 、または 1031
一部のプロキシ右辺値参照型を返すことができるカスタマイズ ポイントです。
次回の記事では、反復子の値の型とその参照型 (および現在の右辺値の参照型) との間の関係について何が言えるか、および 1042のような高次アルゴリズムをどのように制約できるかについて説明します。コード> および
1058
.
いつものように、ここで説明されているすべてのコードは、github の range-v3 リポジトリにあります。
"\e"