Traits とタグ ディスパッチを使用したソフトウェア設計

タグのディスパッチにより、型の特性に基づいて関数を選択できます。この決定はコンパイル時に行われ、特性に基づいています。

タグのディスパッチは特性に基づいています。したがって、特性について少し書きたいと思います。

特性

特性は、ジェネリック型の特性を提供するクラス テンプレートです。クラス テンプレートの 1 つまたは複数の特性を抽出できます。

すでにお気づきかもしれませんが、型特性ライブラリのメタ関数は C++ の特性の典型的な例です。それらについては、すでにいくつかの記事を書いています。

<オール>
  • 型チェック
  • 型の比較
  • std::is_base_of
  • 正しさ
  • パフォーマンス
  • この投稿のタグ ディスパッチに直接ジャンプする前に、イテレータの特徴を紹介したいと思います。次のコード スニペットは、ポインターの部分的な特殊化を示しています:

    template<T> 
    struct iterator_traits<T*> { 
     using difference_type = std::ptrdiff_t; 
     using value_type = T; 
     using pointer = T*; 
     using reference = T&; 
     using iterator_category = std::random_access_iterator_tag; 
    };
    

    イテレータ カテゴリは、次の階層を構築します:

    struct input_iterator_tag{}; 
    struct output_iterator_tag{}; 
    struct forward_iterator_tag: public input_iterator_tag{}; 
    struct bidirectional_iterator_tag: public forward_iterator_tag{}; 
    struct random_access_iterator_tag: public bidirectional_iterator_tag{}; 
    

    さまざまなイテレータ カテゴリは、標準テンプレート ライブラリのコンテナに対応しています。

    次の関係は、イテレータ カテゴリとそのサポート操作に適用されます。ランダム アクセス反復子は双方向反復子であり、双方向反復子は前方反復子です。これは std::array, std::vector, を意味します と std::string ランダム アクセス イテレータをサポートしますが、std::list はサポートしません .

    タグのディスパッチ

    これで、タグ ディスパッチを適用して、細かく調整された advance_ を実装できます。 使用されるコンテナ用に最適化されたアルゴリズム。まず、std::advance はすでに標準テンプレート ライブラリの一部です:

    template< class InputIt, class Distance >
    void advance( InputIt& it, Distance n ); (until C++17)
    template< class InputIt, class Distance >
    constexpr void advance( InputIt& it, Distance n ); (since C++17)
    

    std::advance 指定されたイテレータ it をインクリメントします n 要素。 n が負の場合、反復子はデクリメントされます。したがって、この場合、イテレータを提供するコンテナは双方向でなければなりません。

    これが advance_ の私の実装です :

    // advance_.cpp
    
    #include <iterator>
    #include <forward_list>
    #include <list>
    #include <vector>
    #include <iostream>
    
    template <typename InputIterator, typename Distance> 
    void advance_impl(InputIterator& i, Distance n, std::input_iterator_tag) {
     std::cout << "InputIterator used" << '\n'; 
     if (n >= 0) { while (n--) ++it; }
    }
    
    template <typename BidirectionalIterator, typename Distance> 
    void advance_impl(BidirectionalIterator& i, Distance n, std::bidirectional_iterator_tag) {
     std::cout << "BidirectionalIterator used" << '\n';
     if (n >= 0) 
     while (n--) ++i;
     else 
     while (n++) --i;
    }
    
    template <typename RandomAccessIterator, typename Distance> 
    void advance_impl(RandomAccessIterator& i, Distance n, std::random_access_iterator_tag) {
     std::cout << "RandomAccessIterator used" << '\n';
     i += n; // (5)
    }
    
    template <typename InputIterator, typename Distance> // (4)
    void advance_(InputIterator& i, Distance n) {
     typename std::iterator_traits<InputIterator>::iterator_category category; 
     advance_impl(i, n, category); 
    }
     
    int main(){
     
     std::cout << '\n';
     
     std::vector<int> myVec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // (1)
     auto myVecIt = myVec.begin(); 
     std::cout << "*myVecIt: " << *myVecIt << '\n';
     advance_(myVecIt, 5);
     std::cout << "*myVecIt: " << *myVecIt << '\n';
     
     std::cout << '\n';
     
     std::list<int> myList{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // (2)
     auto myListIt = myList.begin(); 
     std::cout << "*myListIt: " << *myListIt << '\n';
     advance_(myListIt, 5);
     std::cout << "*myListIt: " << *myListIt << '\n';
     
     std::cout << '\n';
     
     std::forward_list<int> myForwardList{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // (3)
     auto myForwardListIt = myForwardList.begin(); 
     std::cout << "*myForwardListIt: " << *myForwardListIt << '\n';
     advance_(myForwardListIt, 5);
     std::cout << "*myForwardListIt: " << *myForwardListIt << '\n';
     
     std::cout << '\n';
     
    }
    

    この例では std::vector を使用しています (1 行目)、std::list (2 行目)、および std::forward_list (3 行目)。 std::vector std::list のランダム アクセス イテレータをサポート 双方向イテレータ、および std::forward_list 前方反復子。呼び出し std::iterator_traits<InputIterator>::iterator_category category;関数 advance_  で (4 行目) 指定されたイテレータに基づいて、サポートされているイテレータ カテゴリを決定します。最後の呼び出し advance_impl(i, n, category) 最後に、実装関数の最も特化したオーバーロードにディスパッチします advance_impl.

    ディスパッチを視覚化するために、実装関数 advance_imp に短いメッセージを追加しました l.

    このような微調整された事前実装の利点は何ですか?

    <オール>
  • タイプ セーフ :コンパイラが advance_impl のバージョンを決定します 使用されている。したがって、前方反復子を使用して双方向反復子を必要とする実装を呼び出すことはできません。前方反復子による後方反復は、未定義の動作です。
  • パフォーマンス :前方イテレータまたは双方向イテレータを n 位置に配置するには、さらに n インクリメント操作が必要です。したがって、その複雑さは線形です。この観察は、ランダム アクセス反復子には当てはまりません: i += n などのポインター演算 (5 行目) は一定の操作です。
  • 次は?

    次回の投稿では、動的ポリモーフィズム (オブジェクト指向) と静的ポリモーフィズム (テンプレート) を橋渡しして、かなり洗練された手法である型消去を紹介します。

    Modernes C++ の未来

    タイプ消去の投稿は、テンプレートに関する私の最後の投稿になります。以前のものを取得するには、TOC またはカテゴリ テンプレートを使用します。その後も C++20 について書き続け、C++23 の未来をのぞいていきます。興味深い投稿のアイデアがあれば、私に電子メールを書いてください:この電子メール アドレスは、スパムボットから保護されています。表示するには JavaScript を有効にする必要があります..