反復子でアルゴリズムをラップする

こんにちは親愛なる読者。 今日は金曜日です。機内では、できればC ++ 17を考慮して、新しいC ++製品を集中的にレビューおよび分析し続けます。このエキサイティングなレッスンで、Jacek Galowiczのブログに出会いました。 比較的新鮮な素材のうち、カットの下に投稿された記事が特に気に入った。



あるアルゴリズムから数値の範囲を生成する必要があることが時々起こります。 単純に昇順で並べられた数字の範囲、奇数のみ、または単純な数字などです。 フィボナッチ数と同様に、次の数を計算するための値を保存することにより、一部の操作を最適化できます。 この記事では、このような計算をイテレーターでラップして、強力で美しくカプセル化されたアルゴリズムを取得する方法を説明します。



フィボナッチ数



多くのフィボナッチ数が広く知られています。 これらの数値の生成は再帰の古典的な例ですが、少なくとも標準的な命令型言語では、反復バージョンの方がより強力です。

size_t fib(size_t n) { size_t a {0}; size_t b {1}; for (size_t i {0}; i < n; ++i) { const size_t old_b {b}; b += a; a = old_b; } return b; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、フィボナッチ数を生成するのは非常に簡単です。 しかし、特定の問題を解決するために、特定の制限までのすべてのフィボナッチ数を生成する必要がある場合、このソリューションはもはや便利とは言えません。 フィボナッチ数N



計算してからN+1



計算するとき、各フィボナッチ数は同じシリーズの2つの前の数の合計であるため、変数aおよびbの内容を再利用できます。



この場合、特定のフィボナッチ状態を制御するクラスを用意しておくと便利です。そうすれば、次の数値をすばやく正確に取得できます。



私たちの多くは、単にnext()



メソッド、 current()



メソッドでfibonacci_number



クラスを実装し、それを使用します。 もちろんこれは良いことですが、私はもう1つのステップを踏んで思い出してください。結局のところ、それがイテレータの仕組みです。 この機能をイテレータ言語で実装することにより、STLと組み合わせて使用​​でき、コードの可読性が大幅に向上します。



イテレータ



最も単純なイテレータを実装するために何をする必要がありますか？



これは、コンテナクラスを反復処理する場合のC ++コンパイラの機能です。

 for (const auto &item : vector) { /*   */ }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このようなループ宣言は、C ++ 11以降に存在します。 コンパイラーは、以下の同等のコードを作成します。

 { auto it (std::begin(vector)); auto end (std::end(vector)); for (; it != end; ++it) { const auto &item (*it); /*   */ } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

延長されたサイクルに注目し、何を実装する必要があるかを確認します。 まず、2種類のオブジェクトを区別する必要があります。 vector



は反復可能な範囲であり、 反復子です。



反復可能範囲は、 begin()



およびend()



関数を実装する必要があります。 これらの関数は反復子オブジェクトを返します。



注：サンプルコードでは、vector.begin（）およびvector.end（）ではなく、 std::begin(vector)



およびstd::end(vector)



が返されます。 これらのSTL関数はvector.begin（）およびend（）を呼び出しますが、より普遍的です。つまり、生の配列にも適用でき、開始および終了イテレーターを取得するために必要なことを自動的に実行します。



iterator



クラスに実装する必要があるものは次のとおりです。

• *ポインターを逆参照する演算子（ポインターも本格的なイテレーターです！）
• ++演算子（プレフィックス）、反復子を次の要素にインクリメントします
• the！=演算子は、サイクルを完了する必要があるかどうか、つまりend
  
  
  
  示された位置に到達it
  
  
  
  ていないかどうかを確認するために必要です。

アルゴリズムによって生成された範囲を実装するには、最初にイテレータを作成する必要があります。イテレータは、本質的に、 operator++



実装で変数とアルゴリズム自体を非表示にします。 次に、反復クラスは開始および終了反復子を提供するだけなので、C ++ 11スタイルのforループを提供します。

 class iterator { // ...   ... public: //  iterator& operator++() { /*  */ return *this; } T operator*() const { /*     */ } bool operator!= const (const iterator& o) { /*   */ } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

世界で最も単純なイテレーターは数えられます。 整数変数をラップし、演算子++でラップして、 operator*



整数を返します。 operator!=



次に、この番号を別のイテレータからの番号と比較します。

それでは、フィボナッチイテレータに移りましょう。



フィボナッチイテレータ

 class fibit { size_t i {0}; size_t a {0}; size_t b {1}; public: constexpr fibit() = default; constexpr fibit(size_t b_, size_t a_, size_t i_) : i{i_}, a{a_}, b{b_} {} size_t operator*() const { return b; } constexpr fibit& operator++() { const size_t old_b {b}; b += a; a = old_b; ++i; return *this; } bool operator!=(const fibit &o) const { return i != oi; } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このイテレータを使用すると、フィボナッチ数を繰り返し処理することがすでに可能です。

 fibit it; //       "i", //     ,   "i"   // 20,      const fibit end {0, 0, 20}; while (it != end) { std::cout << *it << std::endl; ++it; } //       STL: (  <iterator>) std::copy(it, end, std::ostream_iterator<size_t>{std::cout,"\n"});
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

C ++ 11のようにすべてを美しくするには、反復可能なクラスが必要です。

 class fib_range { fibit begin_it; size_t end_n; public: constexpr fib_range(size_t end_n_, size_t begin_n = 0) : begin_it{fibit_at(begin_n)}, end_n{end_n_} {} fibit begin() const { return begin_it; } fibit end() const { return {0, 0, end_n}; } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして今、あなたは書くことができます...

 for (const size_t num : fib_range(10)) { std::cout << num << std::endl; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

...最初の10個のフィボナッチ数を表示します



fibit_at



関数fibit_at



何をしfibit_at



か？ これはconstexpr



関数constexpr



、可能な場合は、コンパイル時にフィボナッチイテレータを昇格させ、ユーザーが必要とするフィボナッチ数に到達するようにします。

 constexpr fibit fibit_at(size_t n) { fibit it; for (size_t i {0}; i < n; ++i) { ++it; } return it; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

たとえば、この関数を使用すると、コンパイル時に目的の開始位置を準備できるため、実行時に最初の100個のフィボナッチ数を計算することなく、フィボナッチ数列の数を100から100の範囲で並べ替えることができます。



C ++ 17を使用する場合、 fibit_at



std::next(fibit{}, n)



に置き換えることができるため、C ++ 17 STLstd::next



はconstexpr



関数であるため、 constexpr



ない。



フィボナッチ数列の100番目の数値がすでに計算されていることを確認するには、コンパイラがディスクへのバイナリプログラムの書き込みを開始するときに、 constexpr



変数に範囲を追加するだけです。

 constexpr const fib_range hundred_to_hundredfive {105, 100}; for (size_t num : hundred_to_hundredfive) { //  - }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

フィボナッチ反復子とSTLアルゴリズムを組み合わせます



最初の1000フィボナッチ数を含むベクトルが必要だとします。 フィボナッチアルゴリズムは既に便利なイテレータクラスでラップされているため、 std:



STLアルゴリズムで使用できstd:

 std::vector<size_t> fib_nums; fib_nums.resize(1000); constexpr const fib_range first1000 {1000}; std::copy(std::begin(first1000), std::end(first1000), std::begin(fib_nums));
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

とても素敵で快適。 ただし、イテレータラベルを指定しなかったため、ここに示すコードはコンパイルされません。 これは単純に行われます： fibit



明示的にstd::iterator<std::forward_iterator_tag, size_t>



継承するようにしstd::iterator<std::forward_iterator_tag, size_t>



。



fibit



クラスのベースであるstd::iterator



は、いくつかの型定義を追加するだけで、STLアルゴリズムがどのようなイテレータであるかを把握するのに役立ちます。 特定の状況での特定のタイプのイテレーターには、パフォーマンスが最適化されたSTLアルゴリズムの他の実装があります（これはユーザーからきちんと隠されています！）。



ラベルstd::forward_iterator



は、ステップごとに単純に進めることができるイテレーターがあることを意味します-そして、それは前方にのみ移動し、後方には移動しません。



まとめ



数値範囲を生成する多くのアルゴリズムは、完全に自然な反復子として実装できます。 C ++にはイテレーター用のおいしい構文糖衣があり、抽象化のための有機的なインターフェースになります。



STLアルゴリズムおよびSTL準拠のデータ構造と組み合わせて、テストおよび保守が容易な読み取り可能な強力なコードを作成します。



この記事では、通常のデータポインターではなく、イテレーターについて説明します。 アルゴリズムの実装は、インクリメント段階で、次の要素への内部ポインタの新しい位置よりも複雑なものが計算されるという点で興味深いです。 興味深いことに、この方法では、範囲を定義する反復可能なオブジェクトをインスタンス化できます-これには、深刻な計算が必要です。 しかし、誰かが特に結果を要求するまで実行されません（そして、結果を要求するコードは、どのアルゴリズムが暗黙的に実行されるかさえも知りません。



このスタイルはレイジーコンピューティングに関連付けられています。純粋に機能的なプログラミング言語の強力で美しい原則です。