前回の投稿で、可能性のある std::advance を提示しました タグディスパッチに基づく実装。私の読者の 1 人は、 constexpr if に基づいて std::advance を実装することもできると述べました。 、または概念。彼の権利。では、やってみましょう。
短いリマインダー: std::advance(it, n) 指定された iterator it をインクリメントします n 作 要素。 If n が負の場合、反復子はデクリメントされます。コンテナーとコンテナーによって提供される反復子に応じて、微調整されたバージョン std::advance 使用されている。この綿密な戦略の理由は、型の安全性とパフォーマンスの 2 つです。前回の投稿「特性とタグのディスパッチを使用したソフトウェア設計」では、バージョン std::advance を実装しました。 タグディスパッチに基づいています。 std::advance の可能性に飛び込む前に constexpr if (C++17) または概念 (C++20) に基づく実装、タグ ディスパッチ (C++98) の実装をもう一度示したいと思います。
タグのディスパッチ (C++98)
関数 advance_ を呼び出します std::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--) ++i; }
}
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';
}
難しい話は抜きにして。これがプログラムの出力です。
詳細を知りたい場合は、以前の記事「特性とタグのディスパッチを使用したソフトウェア設計」をお読みください。
constexpr if (C++17)
constexpr if ソース コードを条件付きでコンパイルできるようにします。
template <typename T>
auto getValue(T t) {
if constexpr (std::is_pointer_v<T>) // (1)
return *t; // deduces return type to int for T = int*
else // (2)
return t; // deduces return type to int for T = int
}
constexpr if の式は、コンパイル時の述語でなければなりません。コンパイル時の述語は、ブール値を返し、コンパイル時に実行される関数です。この場合、型特性関数 std::is_pointer. を使用します 両方の分岐は (1 行目と 2 行目) が有効である必要があります。
std::advance の次の実装 cppreference.com からのコピーです。関数の名前を advance_ に変更しただけです 以前のプログラムの関数名と一致させる advance_.cpp, いくつかのラインマーカーを追加しました。したがって、以前の C++98 ベースの実装を次のものに置き換えることができます:
// implementation via constexpr if, available in C++17
template<class It, class Distance>
constexpr void advance_(It& it, Distance n)
{
using category = typename std::iterator_traits<It>::iterator_category; // (1)
static_assert(std::is_base_of_v<std::input_iterator_tag, category>); // (2)
auto dist = typename std::iterator_traits<It>::difference_type(n); // (3)
if constexpr (std::is_base_of_v<std::random_access_iterator_tag, category>) // (4)
it += dist;
else {
while (dist > 0) { // (6)
--dist;
++it;
}
if constexpr (std::is_base_of_v<std::bidirectional_iterator_tag, category>) { // (5)
while (dist < 0) {
++dist;
--it;
}
}
}
}
この実装は、使用されたイテレータに基づいてイテレータ カテゴリを決定し (1 行目)、イテレータ カテゴリが std::input_iterator_tag から派生したものであることをアサートします。 （2行目）。 3 行目は、イテレータをインクリメントするための値を決定します。今、 constexpr if 登場します。反復子の型に応じて、(4) 行、(5) 行、または (6) 行が使用されます。行 (4) には std::random_access_iterator, が必要です 行 (5) std::bidirectional_iterator 、そして行 (6) は残りの反復子を取ります。
次の図は、どのコンテナーがどの constexpr if のコンパイルをトリガーするかを示しています。 ブランチ:
正直、タグディスパッチをベースにしたC++98版の方が分かりやすいです。もう 3 年先の未来に飛び込んで、advance を実装させてください。 概念を使用します。
概念 (C++20)
C++20 は、反復子の次の概念をサポートしています:
std::input_or_output_iterator std::input_iterator std::output_iterator std::forward_iterator std::bidirectional_iterator std::random_access_iterator std::contiguous_iterator
std::input_output_iterator オペレーション ++It, It++ をサポート 、および *It. std::input_iterator と std::output_iterator すでに std::input_or_output_iterator. です 次の関係が成り立ちます。連続反復子はランダム アクセス反復子、ランダム アクセス反復子は双方向反復子、双方向反復子は前方反復子です。連続イテレータでは、コンテナ要素が連続してメモリに格納されている必要があります。
コンセプトのおかげで、advance_ の実装は非常に簡単です。私は概念でadvance_をオーバーロードし、概念を制限された型パラメータとして使用します.
// conceptsAdvance.cpp
#include <concepts>
#include <iostream>
#include <forward_list>
#include <list>
#include <vector>
template<std::input_iterator I> // (1)
void advance_(I& i, int n){
std::cout << "InputIterator used" << '\n';
if (n >= 0) { while (n--) ++i; }
}
template<std::bidirectional_iterator I> // (2)
void advance_(I& i, int n){
std::cout << "BidirectionalIterator used" << '\n';
if (n >= 0)
while (n--) ++i;
else
while (n++) --i;
}
template<std::random_access_iterator I> // (3)
void advance_(I& i, int n){
std::cout << "RandomAccessIterator used" << '\n';
i += n;
}
int main() {
std::cout << '\n';
std::forward_list forwList{1, 2, 3};
std::forward_list<int>::iterator itFor = forwList.begin();
advance_(itFor, 2); // (4)
std::list li{1, 2, 3};
std::list<int>::iterator itBi = li.begin();
advance_(itBi, 2); // (5)
std::vector vec{1, 2, 3};
std::vector<int>::iterator itRa = vec.begin();
advance_(itRa, 2); // (6)
std::cout << '\n';
}
関数の 3 つのバリエーション advance_ 概念にオーバーロードされています std::input_iterator (1 行目)、 std::bidirectional_iterator (2 行目)、および std::random_access_iterator (3 行目)。コンパイラは、最適なオーバーロードを選択します。これは、 std::forward_list に対して (4行目) 概念 std::forward_iteratorに基づくオーバーロード 、 std::list の場合 (5行目) 概念 std::bidirectional_iteratorに基づくオーバーロード 、および std::vector の場合 (6 行目) std::random_access_iterator の概念に基づくオーバーロード
完全を期すために、コンパイラ エクスプローラで実行したプログラムを次に示します。
あなたが好むadvance_のバージョンがわかりません。タグ ディスパッチ ベースの C++98 実装、constexpr if ベースの C++17 実装、または概念ベースの C++20 実装。読みやすさと保守性の観点から、コンセプトベースのバージョンが私のお気に入りです。欠点は、C++20 コンパイラが必要なことです。 cppreference.com は、C++ コンパイラの C++ コンパイラ サポートに関する洞察を提供します。
次は?
この高度なアルゴリズムとの短い相互作用の後、次の投稿で動的ポリモーフィズム (オブジェクト指向) と静的ポリモーフィズム (テンプレート) を橋渡しして、かなり洗練された手法である型消去を紹介します。
新しい C++ 開発者の仕事の機会をお探しですか?ジューブルを試してみてください。