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

免責事項: これは詳細についての長くて退屈な投稿です。深刻なライブラリ マニアのみ。

これは、プロキシ イテレータに関するシリーズの 3 番目です。 、既存の STL イテレータ概念階層の制限、およびそれに対して何ができるか。最初の投稿で、プロキシ イテレータとは何かを説明しました (vector<bool> のようなイテレータ)。 逆参照されると、実際の参照ではなくプロキシ オブジェクトを返す) と、それらが今日の STL で引き起こす 3 つの具体的な問題:

<オール>
  • イテレータの値の型とその参照型の関係について、一般的に言えることは何ですか?
  • for_each のような高次アルゴリズムをどのように制約するか そして find_if シーケンスの要素を操作する関数を取りますか?
  • sort のように、要素を入れ替えたり移動したりしなければならないアルゴリズムをどのように実装しますか? と reverse ?
  • 2 番目の投稿では、問題 (3) にズームインし、既存の std::iter_swap がどのように機能するかを示しました。 API は、私が提案する新しい API とともに、サービスに投入される可能性があります:std::iter_move .これらの API を組み合わせることで、反復子は、その要素をどのように交換および移動する必要があるかをアルゴリズムに伝えるためのチャネルを提供します。 iter_move の追加で API、イテレータは新しい関連型を取得します :rvalue_referencestd::iterator_traits に住むことができます 既存の value_type と並んで と reference 関連する型。

    この投稿では、最初の問題を掘り下げます:イテレータとは何かをコードで定義する方法 .

    値と参照

    最初の 2 つの記事と同様に、zip を使用します。 理解するのは簡単ですが、STLアルゴリズムには完全に悩まされているためです。 zip を思い出してください pair の 1 つのシーケンスのように見せることで、2 つのシーケンスを遅延適応させます 以下に示すように、

    std::vector<int> x{1,2,3,4};
    std::vector<int> y{9,8,7,6};
    
    using namespace ranges;
    auto zipped = view::zip(x, y);
    
    assert(*zipped.begin() == std::make_pair(1,9));
    assert(&(*zipped.begin()).first == &x[0]);
    

    上記の 2 つのアサーションが示すように、zip を逆参照します。 イテレータは pair を返します 、そしてペアが実際には 参照 のペアであること 、基になるシーケンスを指しています。 zip 上記の範囲には、次のタイプが関連付けられています:

    関連型… zip の場合 ビュー
    value_type pair<int, int>
    reference pair<int &, int &>
    rvalue_reference pair<int &&, int &&>

    概念が C++ に導入されると、イテレータとはとは何かをコードで記述する必要があります。 . パロ アルト TR 、2012 年に公開され、それを突き刺します:InputIterator Readable です と Incrementable 、ここで Readable は次のように定義されます:

    template< typename I >
    concept bool Readable =
        Semiregular<I> &&
        requires(I i) {
            typename ValueType<I>;
            { *i } -> const ValueType<I> &;
        };
    

    これは、Readable タイプには関連する ValueType があります . *i とも言います 有効な表現です 、および *i の結果 const ValueType<I> & に変換可能でなければなりません . *i の場合はこれで問題ありません 実際の参照のような単純なものを返します。しかし、zip のようなプロキシ参照を返す場合 表示すると、問題が発生します。

    zip の代用 requires へのイテレータ 上記の句は次のようになります:

    const pair<int,int>& x = *i;
    

    これは x の初期化を試みます pair<int&, int&> で .これは実際にはある意味で機能します。一時的な pair<int &, int &> オブジェクトは暗黙的に一時的な pair<int, int> に変換されます 基礎となる整数をコピーすることによって、その新しいペアは const & にバインドされます 一時変数は const 参照にバインドできるためです。

    しかし、値をコピーすることは、私たちが望んでいることでも期待していることでもありません。 int の代わりに s、unique_ptr のような移動のみのタイプのペアがありました 、これはまったく機能しませんでした。

    だから Readable プロキシ参照を処理するには、概念を微調整する必要があります。何ができるでしょうか?

    zip を作成する簡単な方法の 1 つ イテレータモデル Readable コンセプトは、*i という要件を単純に削除することです。 const ValueType<I>& に変換可能 .これは不満です。きっと何かがある イテレータの参照型とその値型の関係について言えます。あると思います。パロアルト TR が EqualityComparable を定義する方法にヒントがあります。

    一般的な型の制約

    このようなコードについてどう思いますか?

    vector<string> strs{"three", "blind", "mice"};
    auto it = find(strs.begin(), strs.end(), "mice");
    

    合理的ですね。これは string の範囲を検索します char const* の .リンゴの入ったバケツの中のオレンジを探しているとしても、これはうまくいくはずです。オレンジは十分にリンゴに似ています。リンゴとオレンジを比較する方法を知っているからです。つまり、operator== があります。 string を比較する s with char const* .しかし、「十分にリンゴに似ている」とはどういう意味ですか? find を制約する場合 アルゴリズムと概念を組み合わせて使用​​する場合、任意の にとって「リンゴのような」とはどういう意味かをコードで記述できる必要があります。 リンゴとすべて オレンジ。

    パロアルト TR は、operator== が存在するだけでは考えていません。 で十分です。代わりに、クロスタイプ EqualityComparable を定義します コンセプト 次のように:

    template< typename T1, typename T2 >
    concept bool EqualityComparable =
        EqualityComparable<T1> &&
        EqualityComparable<T2> &&
        Common<T1, T2> &&
        EqualityComparable< std::common_type_t<T1, T2> > &&
        requires(T1 a, T2 b) {
            { a == b } -> bool;
            { b == a } -> bool;
            { a != b } -> bool;
            { b != a } -> bool;
            /* axioms:
                using C = std::common_type_t<T1, T2>;
                a == b <=> C{a} == C{b};
                a != b <=> C{a} != C{b};
                b == a <=> C{b} == C{a};
                b != a <=> C{b} != C{a};
            */
        };
    

    つまり、これは 2 つの 異なる ためのものです。 型が EqualityComparable であるためには、それぞれ個別に EqualityComparable (つまり、それ自体) である必要があり、互いに比較可能である必要があります。および (重要な部分) 共通の型を共有する必要があります これは、同じセマンティクスを持つ EqualityComparable でもあります。

    質問は次のようになります:do std::string および char const * 共通の型を共有しており、それらは両方とも変換でき、どちらが同じセマンティクスと比較されますか?この場合、答えは簡単です:std::string は一般的なタイプです。

    余談:なぜパロアルト TR は find への引数にこの追加の CommonType 要件を設定するのですか? 機能し、今日「正しい」コードを壊すのはいつになるのでしょうか?興味深い質問です。正当化は数学的で、やや哲学的です。物事が等しいかどうかを比較するとき、それらが同じ値を持っているかどうかを尋ねているのです。誰かが operator== を提供したからといって たとえば、Employee を比較する SocialSecurityNumber で 従業員を社会保障番号にしたり、その逆にしたりしません。コードについて数学的に推論できるようにしたい場合 (実際にそうしています)、like を like に置き換えることができなければなりません。等式の推論をプログラムに適用できることは恩恵ですが、そのルールに従ってプレイする必要があります。

    読みやすく共通

    これが Readable とどう関係しているのか疑問に思うかもしれません 概念。パロアルト TR が定義する概念をもう一度見てみましょう:

    template< typename I >
    concept bool Readable =
        Semiregular<I> &&
        requires(I i) {
            typename ValueType<I>;
            { *i } -> const ValueType<I> &;
        };
    

    私の考えでは、これが言おうとしているのは、イテレータの参照型とその値の型の間には代用可能性、数学的な同等性があるということです。 EqualityComparable Common を使用 その代替可能性を強制します。 Readable を修正しようとするとどうなりますか

    template< typename I >
    concept bool Readable =
        Semiregular<I> &&
        requires(I i) {
            typename ValueType<I>;
            requires Common< ValueType<I>, decltype(*i) >;
        };
    

    ここでは、Readable について言っています。 型の場合、参照型と値型は共通の型を共有する必要があります。一般的な型は std::common_type_t のようなものを使用して計算されます 、基本的に三項条件演算子を使用します (?: )。 (私は std::common_type_t 以来「何か」と言います 実際にはその仕事をしていません。 lwg2408 と lwg2465 を参照してください。)

    残念ながら、これで問題が完全に解決するわけではありません。 common_type_t<unique_ptr<int>, unique_ptr<int>&> をしようとすると 理由がわかります。答えは明白に思えるにもかかわらず、うまくいきません。問題は common_type です 条件演算子で共通の型をテストする前に、常に最上位の const および参照修飾子を取り除きます。移動のみのタイプの場合、条件演算子が barf します。

    common_type というのはいつも少し奇妙だと思っていました。 それらをテストする前にその引数を減衰させます。それが必要な場合もありますが、(ここのように) そうでない場合もあります。代わりに、共通の型をテストする別の型特性が必要ですが、参照と cv の修飾は保持されます。 common_reference と呼んでいます .ただし、常に参照型を返すとは限らないため、少し間違った呼び名です。

    2 つの型の共通の参照は、両方の型のオブジェクトをバインドできる最小修飾型です。 common_reference 可能な場合は参照型を返そうとしますが、必要な場合は値型にフォールバックします。例をいくつか挙げてみましょう:

    共通参照… …結果
    common_reference_t<int &, int const &> int const &
    common_reference_t<int &&, int &&> int &&
    common_reference_t<int &&, int &> int const &
    common_reference_t<int &, int> int

    common_reference で 型特性、 CommonReference を定義できます コンセプトと Readable を指定 つまり、次のようになります:

    template< typename I >
    concept bool Readable =
        Semiregular<I> &&
        requires(I i) {
            typename ValueType<I>;
            requires CommonReference<
                ValueType<I> &,
                decltype(*i) && >;
        };
    

    上記の概念では、両方の *i に対応する共通の参照型が必要です。 イテレータの値型の変更可能なオブジェクトはバインドできます。

    これは、現在有効なすべての反復子と、プロキシ参照を返す反復子を型チェックするのに十分一般的だと思います (ただし、それを確認するには多少の作業が必要です)。 iter_move に対応するために、これをさらに一般化できます。 以前の投稿で説明した API:

    template< typename I >
    concept bool Readable =
        Semiregular<I> &&
        requires(I i) {
            typename ValueType<I>;
            requires CommonReference<
                ValueType<I> &,
                decltype(*i) && >;          // (1)
            requires CommonReference<
                decltype(iter_move(i)) &&,
                decltype(*i) && >;          // (2)
            requires CommonReference<
                ValueType<I> const &,
                decltype(iter_move(i)) &&>; // (3)
        };
    

    では、これが実際にどのように機能するか見てみましょう。

    反復子と CommonReference

    まず、int& のような実際の参照を返すイテレータの簡単なケースを考えてみましょう。 .要件は、その値型、参照型、右辺値参照型の 3 つの CommonReference を満たすことです。 上記の制約。 (1) int& 間の共通参照が必要 と int& . (2) int&& の間 そして int& 、および (3) int const& の間 そして int&& .これらはすべて明らかに正しいので、この反復子は Readable です .

    しかし、zip はどうでしょうか。 イテレータ?ここでのことはもっとトリッキーです。

    zip の 3 つの一般的な参照制約 これまでの反復子:

    共通参照… …結果
    common_reference_t<
    pair<int,int> &,
    pair<int&,int&> &&>
    ???
    common_reference_t<
    pair<int&&,int&&> &&,
    pair<int&,int&> &&>
    ???
    common_reference_t<
    pair<int,int> const &,
    pair<int&&,int&&> &&>
    ???

    うわぁ。 common_reference はどうですか これを評価するはずの特性?三項条件演算子は、その役割を果たせません.

    OK、まず、答えをどうしたいか想像してみましょう。最初に最後のコードを取り上げて、次のコードを検討してください:

    void foo( pair< X, Y > p );
    
    pair<int,int> const & a = /*...*/;
    pair<int &&,int &&> b {/*...*/};
    
    foo( a );
    foo( move(b) );
    

    X で選択できるタイプがある場合 と Y これをコンパイルすると、pair<X,Y> を作成できます pair<int&&,int&&>&& の「共通参照」 と pair<int,int> const & .確かにある:XY 両方とも int const & である必要があります .

    実際、 CommonReference のそれぞれについて 制約がある場合、答えを pair<int const&,int const&> にすることができます 安心してください。原則として、私たちの zip イテレータ できる Readable をモデル化 概念。

    しかし、これをもう一度見てください:

    common_reference_t<pair<int,int> &, pair<int&,int&> &&>
    

    これで咳が出たら pair<int const&,int const&> ペアの要素を変異させる能力です。理想的な世界では、答えは pair<int&,int&> です 両方の pair<int,int>& からの変換のため と pair<int&,int&>&& 安全であり、common_reference の「最小限の資格」の精神を満たしています。 特性。しかし、このコードはコンパイルされません:

    void foo( pair< int&,int& > p );
    
    pair<int,int> a;
    pair<int&,int&> b {/*...*/};
    
    foo( a );       // ERROR here
    foo( move(b) );
    

    残念ながら、pair 理論上は安全ですが、この変換は提供されません。それは欠陥ですか?多分。しかし、それは私たちが取り組む必要があるものです。

    簡単に言うと、range-v3 で行った解決策は、独自の pair を定義することです 必要な変換を伴う型に似ています。 common_pair と呼んでいます std::pair から継承しています 期待どおりに動作するようにします。 common_paircommon_reference のいくつかの狡猾な特殊化 、Readable zip の制約が満たされている 次のような反復子:

    共通参照… …結果
    common_reference_t<
    pair<int,int> &,
    common_pair<int&,int&> &&>
    common_pair<int&,int&>
    common_reference_t<
    common_pair<int&&,int&&> &&,
    common_pair<int&,int&> &&>
    common_pair<int const&,int const&>
    common_reference_t<
    pair<int,int> const &,
    common_pair<int&&,int&&> &&>
    common_pair<int const&,int const&>

    これらの型を計算することは、最初に見えるほどトリッキーではありません。 pair<int,int>& のようなタイプの場合 と common_pair<int&,int&>&& 、次のようになります:

    <オール>
  • 最上位の ref および cv 修飾子をペアのメンバーに配布します。 pair<int,int>& pair<int&,int&> になります 、および common_pair<int&,int&>&& common_pair<int&,int&> になります .
  • 要素ごとの共通参照を計算し、結果を新しい common_pair にバンドルします 、結果は common_pair<int&,int&> になります .
  • 一般化

    私たちの zip イテレータは、十分に醜いハッカーで、再指定された Readable をモデル化できます 概念。それは良いことですが、vector<bool> などの他のプロキシ参照タイプはどうでしょうか。 の? vector<bool> の場合 の参照タイプは bool_ref です の場合、common_reference を特殊化する必要があります。 Readable 制約が満たされます。これには必ず、bool_ref のいずれかで初期化できるように型を定義する必要があります。 または bool& .それは明らかに奇妙なタイプですが、不可能ではありません。 (variant<bool&,bool_ref> を想像してみてください 視覚化するのに問題がある場合)。

    vector<bool> を取得しています のイテレータを型にはめることは、ハッカーでは厄介な作業であり、実際に 使用 その共通の参照 (バリアント型) は、読み取りと書き込みのたびにパフォーマンス ヒットを引き起こします。しかし、STL は実際にそれを使用する必要はありません。存在する必要があるだけです。

    おそらく実際には決して使用されることのない非効率的な型を実装するために、これらのフープを飛び越えるポイントは何ですか? ?これは多くの人にとって満足のいくものではありませんが、答えは数学的な厳密さのためです。イテレータの参照型とその強制可能な値型の間には、なんらかの代入関係がなければなりません。彼らが共通の参照を共有することを要求することは、私がこれまでに思いついた最高のものです.結局のところ、この「役に立たない」タイプには、次の記事で説明するように、実際にはいくつかの用途があります。

    まとめ

    ここにいます。 ある Readable を定義する方法 コンセプト — したがって InputIterator 概念 — プロキシ イテレータを許可するのに十分一般的であると同時に、イテレータの関連付けられた型について意味のある有用な何かを言う方法で。この概念をモデル化するようにプロキシ イテレータを実際に定義するのは簡単なことではなく、膨大な量のハック作業が必要です。でも可能です。

    ゲッター関数とセッター関数を取り、反復子の概念を満たすためにすべてのフープ ジャンプを行う Universal Proxy Reference 型を定義することを想像することもできます。これは、読者の演習として残します。

    ここまで来たら、おめでとうございます。少しがっかりしても許されるかもしれません。このソリューションは理想とはほど遠いものです。おそらく、状況を改善するために言語を変更する方法についての実際の議論に拍車をかけるのに十分なほどひどいものです.

    次の記事では、パズルの最後のピースについて説明します。プロキシ イテレータを許可するようにアルゴリズムの制約をどのように記述すればよいでしょうか?お楽しみに。

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

    "\e"