C ++の間隔、パート3：インクリメントの導入（反復可能）

以前の投稿で、間隔を処理するためのライブラリを作成するときに遭遇した問題について説明しました。 次に、ソリューションについて説明します。間隔の概念の改善。パフォーマンスを犠牲にすることなく、標準ライブラリの階層に完全に適合する区切り記号と無限の間隔を持つ間隔を作成できます。



前回の投稿の最後に、既存の間隔の欠点をまとめました。

• 区切られた間隔と無限の間隔は不良コードを生成します
• 彼らは彼らができるよりも弱い概念をモデル化する必要があります
• あなたはそれを消化しないアルゴリズムに簡単に無限の間隔を渡すことができます
• 使いにくい
• 無限または非常に大きい可能性のある間隔は、difference_typeでオーバーフローを引き起こす可能性があります

最初の問題は特に難しいので、始めましょう。

間隔の概念

はじめに、間隔の概念を厳密に定義しましょう。 C ++標準では、この単語はどこでも使用されますが、どこでも定義されていません。 間隔は、beginとendを抽出できるものであり、beginで開始することでendに到達できるように配置されたイテレータのペアであることを理解できます。 私の提案に関しては、この概念は次のように形式化できます。

using std::begin; using std::end; template<typename T> using Iterator_type = decltype(begin(std::declval<T>())); template<typename T> concept bool Range = requires(T range) { { begin(range) } -> Iterator_type<T>; { end(range) } -> Iterator_type<T>; requires Iterator<Iterator_type<T>>; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

InputRange、ForwardRangeなどと呼ばれる範囲スパンの概念も改善されています。 実際、彼らは単にイテレータからより多くを必要とします。 階層全体を以下に示します。







これらの概念は、Boost.Rangeライブラリ（http://www.boost.org/libs/range）の基礎です

問題1：不正なコード生成

覚えている場合、リミッターと無限の両方の区間を、イテレーターのペアの形で実装するには、終了イテレーターはシグナルでなければなりません。 そして、そのようなイテレータは、シーケンス内の要素の物理的な位置というよりも概念です。 位置が「last + 1」の要素として想像できます-唯一の違いは、到達するまで彼の位置がわからないことです。 シグナル反復子のタイプは通常のものと同じであるため、指定された反復子がシグナルかどうかを判断するには、プログラム実行段階でのチェックが必要です。 これにより、イテレータの比較が遅くなり、メソッドの実装が不便になります。

インクリメンターの概念（反復可能）

イテレーターとは何ですか？ それらを拡大し、逆参照して比較しますか？ そして、シグナルイテレータで何ができますか？ 特にありません。 彼の位置は変わらず、彼は逆参照できません。 彼の位置は常に「last + 1」です。 ただし、イテレータと比較できます。 シグナル反復子は弱い反復子であることがわかります。



間隔の問題は、シグナルイテレータを通常のイテレータに変えようとしていることです。 しかし、彼はそうではありません。 したがって、我々はそれをしません- それらを異なるタイプにします。



範囲の概念では、開始と終了が同じタイプであることが必要です。 それらを異なるものにできるなら、それはすでにより弱い概念-Iterableの概念になります。 インクリメントはイテレーターのようなもので、開始と終了のみが異なるタイプを持ちます。 コンセプト：

 template<typename T> using Sentinel_type = decltype(end(std::declval<T>())); template<typename T> concept bool Iterable = requires(T range) { { begin(range) } -> Iterator_type<T>; { end(range) } -> Sentinel_type<T>; requires Iterator<Iterator_type<T>>; requires EqualityComparable< Iterator_type<T>, Sentinel_type<T>>; }; template<typename T> concept bool Range = Iteratable<T> && Same<Iterator_type<T>, Sentinel_type<T>>;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

当然、RangeコンセプトはIterableコンセプトの一部です。 彼女は、開始タイプと終了タイプに等式制約を追加することにより、単純に改良します。







これは、間隔、インクリメンター、およびイテレーターを考慮すると階層がどのように見えるかですが、プログラムでこれらをこのように定義する必要はまったくありません。 「間隔」、つまり、開始タイプと終了タイプの類似性は、開始反復子の強度に直交することに注意してください。 RandomAccessRangeモデリングをコードに含める必要がある場合、RandomAccessIterable && Rangeが必要であり、コンセプト全体を変更するだけでよいと言えます。



たとえば、開始反復可能イテレーターによってモデル化された概念におけるBidirectionalIterableとForwardIterableの違い。

反復可能およびSTLアルゴリズム

しかし、ちょっと待ってください。結局、STLアルゴリズムはインクリメンターでは動作しません。なぜなら、開始と終了が同じタイプである必要があるからです。 そうです。 そこで、STL全体を調べて、何が書き換えられるかを確認しました。 たとえば、std :: find

 template<class InputIterator, class Value> InputIterator find(InputIterator first, InputIterator last, Value const & value) { for (; first != last; ++first) if (*first == value) break; return first; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

現在、std :: findは範囲を使用しています。 ただし、アルゴリズムは終了反復子の位置を変更しようとしないことに注意してください。 検索アルゴリズムは、範囲ではなくイテラブルで動作するように簡単に変更できます。

 template<class InputIterator, class Sentinel, class Value> InputIterator find(InputIterator first, Sentinel last, Value const & value) { for (; first != last; ++first) if (*first == value) break; return first; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それだけです-変更は非常に小さいため、気づくことさえ困難です。



それでは、どのC ++ 98アルゴリズムを範囲ではなくIterablesで動作するように適合させることができますか？ ほとんどすべてが判明しました。 拒否するものをリストする方が簡単です。 これは：

• copy_backward
• セットとピラミッドを操作するためのアルゴリズム（push_heap、pop_heap、make_heap、sort_heap）
• inplace_merge
• nth_element
• partial_sortおよびpartial_sort_copy
• next_permutationおよびprev_permutation
• random_shuffle
• reverseおよびreverse_copy
• sortおよびstable_sort
• stable_partition

残りの50個は、コードを純粋に機械的に変更する必要があります。 Rangeで定義されているIterableの概念を定義したので、Iterableで動作するアルゴリズムに、同じ方法でRangesで動作する機能を提供します。 これは便利で重要です-イテレータが何らかの互換性のない抽象化を行うために、イテレータに対して記述されたコードが多すぎます。

パフォーマンスの証明

そして、私たちは何を得ますか？ Cラインに戻りましょう。 c_string_rangeクラスについて説明しましたが、文字の列挙によって不正なコードが生成されることがわかりました。 Range_facadeのみを使用して、範囲ではなくIterableをビルドします。

 using namespace ranges; struct c_string_iterable : range_facade<c_string_iterable> { private: friend range_core_access; char const *sz_; char const & current() const { return *sz_; } void next() { ++sz_; } bool done() const { return *sz_ == 0; } bool equal(c_string_iterable const &that) const { return sz_ == that.sz_; } public: c_string_iterable(char const *sz) : sz_(sz) {} };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コードは古いものよりもはるかに単純です。 Range_facadeはすべての作業を行います。 イテレータとシグナルイテレータは、プリミティブとして実装されます。 それをテストするために、次の関数用に最適化されたマシンコードを生成しました。1つは古いc_string_rangeクラスを使用し、もう1つは新しいc_string_iterableを使用します。

 // Range-based int range_strlen( c_string_range::iterator begin, c_string_range::iterator end) { int i = 0; for(; begin != end; ++begin) ++i; return i; } // Iterable-based int iterable_strlen( range_iterator_t<c_string_iterable> begin, range_sentinel_t<c_string_iterable> end) { int i = 0; for(; begin != end; ++begin) ++i; return i; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

アセンブラーを知らなくても、違いを理解できます。

;Range-based strlen pushl %ebp movl %esp, %ebp pushl %esi leal 8(%ebp), %ecx movl 12(%ebp), %esi xorl %eax, %eax testl %esi, %esi movl 8(%ebp), %edx jne LBB2_4 jmp LBB2_1 .align 16, 0x90 LBB2_8: incl %eax incl %edx movl %edx, (%ecx) LBB2_4: testl %edx, %edx jne LBB2_5 cmpb $0, (%esi) jne LBB2_8 jmp LBB2_6 .align 16, 0x90 LBB2_5: cmpl %edx, %esi jne LBB2_8 jmp LBB2_6 .align 16, 0x90 LBB2_3: leal 1(%edx,%eax), %esi incl %eax movl %esi, (%ecx) LBB2_1: movl %edx, %esi addl %eax, %esi je LBB2_6 cmpb $0, (%esi) jne LBB2_3 LBB2_6: popl %esi popl %ebp ret

;Iterable-based strlen pushl %ebp movl %esp, %ebp movl 8(%ebp), %ecx xorl %eax, %eax cmpb $0, (%ecx) je LBB1_4 leal 8(%ebp), %edx .align 16, 0x90 LBB1_2: cmpb $0, 1(%ecx,%eax) leal 1(%eax), %eax jne LBB1_2 addl %eax, %ecx movl %ecx, (%edx) LBB1_4: popl %ebp ret

インクリメンタを使用したコードは、はるかにクールです。 そして、それは「裸の」Cのイテレータから得られたアセンブラとほとんど同じです。

反復子、信号反復子、およびパリティ

しかし、等価性について異なるタイプの2つのオブジェクトを比較することはどういう意味ですか？



未経験者向け： N3351は、どの場合に異なるタイプの比較を許可するかを決定します。 構文「x == y」が有効であり、ブール値を生成するだけでは不十分です。 xとyの型が異なる場合、これらの型自体はEqualityComparableである必要があり、変換できる共通の型である必要があり、EqualityComparableである必要もあります。 charとshortを比較するとします。 これは、EqualityComparableであり、EqualityComparableでもあるintに変換できるため可能です。



イテレータは比較でき、シグナルイテレータは簡単な方法で比較されます。 困難なのは、彼らに共通のタイプを見つけることです。 一般に、各反復子と信号には共通のタイプがあり、次のように作成できます。新しいタイプの反復子Iが存在すると仮定します。 それらを比較すると、両方とも最初にタイプIの2つのオブジェクトに変換されたかのように意味的に動作し、lhsおよびrhsと呼び、次のプレートで比較します。

lhsシグナルイテレータ？	rhsシグナルイテレータ？	lhs == rhs？
本当	本当	本当
本当	偽	完了（rhs.iter）
偽	本当	完了（lhs.iter）
偽	偽	lhs.iter == rhs.iter

このプレートは、比較演算子c_string_range :: iteratorの動作を分析するときに得られるプレートに似ています 。 これは偶然ではありません-これはこのより一般的なスキームの特別なケースでした。 これは、2つのクラスc_string_rangeとc_string_iterableを見ると、すでに気付いているという直感的な結論を裏付けています。 1つはイテレータのペア、もう1つはイテレータ/信号のペアですが、それらの操作スキームは似ています。 少しのパフォーマンスを犠牲にすると、イテラブルから同等の範囲を構築することが可能だと感じています。 そして今、私たちはこれの確認を見つけました。



イテレータとシグナルイテレータを直接比較する機能により、C ++型システムを使用して反復の大きなカテゴリを最適化し、パリティ比較演算子の分岐を削除できます。

異議

異なる種類の開始と終了を与えるという考えは新しいものではなく、それを発明したのは私ではありませんでした。 私は何年も前にそれについてデイブ・アブラハムズから学びました。 最近、同様のアイデアがRangesメーリングリストでDietmar Kuehl によって提示されました。彼の手紙に応えて、Sean Parentは反対しました。

私たちはイテレーターを使いすぎていると思います。 シグナルイテレータの検証またはカウントに基づくエンディングで機能するアルゴリズムは、異なるエンティティです。 copy_n（）およびcopy_sentinel（）を参照



stlab.adobe.com/copy_8hpp.html



間隔について-私はあなたがそれを構築できると確信しています：

1. イテレータのペア
2. イテレータと量
3. イテレータと信号

この場合、copy（r、out）で目的のアルゴリズムを作成できます。

私が彼を正しく理解していれば、彼は、IteratorRange、CountedRange、およびSentinelRangeの3つの並行した間隔の概念の存在について話しています。 そして、これらの階層は相互に関係付けようとする必要はありません。 コピーアルゴリズムには、概念ごとに1つずつ、3つの異なる実装を含める必要があります。 次に、約50のアルゴリズムを3倍にする必要があります。これは、コードの繰り返しが多すぎます。



さらに悪いことに、一部のアルゴリズムは洗練された概念に基づいています。 たとえば、 libc ++では 、rotateアルゴリズムは 、直接反復子、双方向反復子、またはランダムアクセス反復子を渡すかどうかに応じて、3つの実装のいずれかを選択します。 そして、Iterator、Counted、およびSentinelRangesの3つの異なる実装を含めるには、9つの回転アルゴリズムが必要です。 すべての敬意を払って、これはクレイジーです。

合計

投稿の冒頭で、ペアのイテレーターとの間隔に関連する問題のリストを示しました。 パフォーマンスの問題を扱う新しい概念Iterableを示し、間隔の実装の複雑さの問題を提起しました。 これまでのところ、この概念が無限の間隔でどのように機能するかについては説明していません。これについては、4番目の最終投稿で説明します。



すべてのコードはgithubリポジトリにあります。

謝辞

Andrew SuttonにConcpets Liteの構文を支援し、さまざまなタイプのEqualityComparableコンセプトの要件を説明し、多くのアイデアの一般的な改善と形式化に感謝します。 彼の多大な貢献のおかげで、記事はずっと良くなりました。

その他のサイクル記事

C ++の間隔、パート1：区切り記号付きの間隔

C ++の間隔、パート2：無限の間隔

C ++の間隔、パート4：無限大まで