C++テンプレート要素のプログラミングは選択順序付けを実現します。


前言
テンプレートはC++にずっと神秘的な存在です。STLとBoostはテンプレートを大量に使用していますが、一般のプログラマにとってはテンプレートは使用に限ります。一般的なプログラミングでは、自分でテンプレートを定義する必要がある場合が少ないです。しかし、理想的なプログラマとして、テンプレートは回り道のできないカンです。C++標準の継続的な改善により、テンプレートの能力はますます強くなり、使用範囲もますます広くなりました。
C+11において、テンプレートはconstexpr、可変テンプレートパラメータを増加し、リターンタイプの後付けの関数宣言はテンプレートの能力を拡張した。外部テンプレートを追加し、テンプレートのコンパイル速度を加速しました。テンプレートパラメータのデフォルト値、角括弧とテンプレートのエイリアスは、テンプレートの定義と使用をより簡潔にします。
C+14でconstexprの制限を緩和し、変数テンプレートを追加しました。
C++17では、テンプレートの構造関数を簡略化して、テンプレートをより使いやすくします。Foldingはテンプレートを定義に便利にします。
C+20は大きいバージョンの更新で、テンプレートにとっても大きな進歩があります。個人にとって、一番好きなのはconceptです。テンプレートが要求に合っているかどうかを判断できるようにします。また、テンプレートの特化に対して、もう一部のサポートを提供しました。また、ほとんどのSTLライブラリがconstexprをサポートしているので、多くの種類がコンパイル期間に直接使用できるようにしています(以後、テンプレート要素プログラミングは単なる関数言語ではないでしょう。C++のプログラミングは非常に奇妙になると思います)。
テンプレートが徐々に完璧になっていくにつれて、タイガー達はテンプレートの機能が図霊の完全さを実現したことを発見しました。
弟としては、もちろんテトリスに匹敵するプログラムを書く能力がないですが、簡単な順序を書いてもいいです。
ここで共有しているのは並べ替えアルゴリズムの選択です。なぜ並べ替えを選択しますか?それは順序付けの時、彼は元素の位置変化に対して比較的に少ないからです。個人の感覚の関数要素のプログラミングの一番複雑なのは元素の位置を修正することですよね。
コードの詳細
データの構造

template<int ...data>
struct mvector;

template<int first, int ...data>
struct mvector<first, data...> {
 static constexpr int size = sizeof...(data) + 1;
 static constexpr int value = first;
 typedef mvector<data...> next_type;
 constexpr static std::array<int, sizeof...(data) + 1> array = {first, data...};
};

template<int first>
struct mvector<first> {
 static constexpr int size = 1;
 static constexpr int value = first;
 typedef mvector<> next_type;
 constexpr static int array[] = {first};
};

template<>
struct mvector<> {
 static constexpr int size = 0;
 static constexpr int value = -1;
 typedef mvector<> next_type;
 constexpr static int array[] = {};
};

ここでmvcetorテンプレートを定義しました。彼の役割はデータを保存するためのものです。テンプレートの原型は

template<int ...data>
struct mvector;
彼は任意の数の整数を入力することができます。
後の特化によって、テンプレートは全部で4つの属性またはタイプがあります。(これらはテンプレートの出力と見なされます)、それぞれsize、value(最初の要素の値は、後の反復が便利です。)、next_type(頭の尻尾を除いて、反復に便利)、array(mvectorの配列表現形式)。
データの操作
ベクトルを分割

//     
template<int index, typename T, typename S>
struct SplitVector;

template<int index, int ...LeftData, int ...RightData>
struct SplitVector<index, mvector<LeftData...>, mvector<RightData...>> {
 typedef SplitVector<index - 1, mvector<LeftData..., mvector<RightData...>::value>, typename mvector<RightData...>::next_type> next_split;
 typedef typename next_split::LeftVector LeftVector;
 typedef typename next_split::RightVector RightVector;
};

template<int ...LeftData, int ...RightData>
struct SplitVector<0, mvector<LeftData...>, mvector<RightData...>> {
 typedef mvector<LeftData...> LeftVector;
 typedef typename mvector<RightData...>::next_type RightVector;
};

このテンプレートの主な目的はベクトルをある部分から分離することです。
テンプレートの入力は3つあります。index(分離する要素の位置はRightDataの位置)、LeftData(分離された左)、RightData(分離された右側)。
出力はLeftVector、Right Vectorがあります。
ベクトルを統合

//     
template<typename T, typename S>
struct MergeVector;

template<int ...dataa, int ...datab>
struct MergeVector<mvector<dataa...>, mvector<datab...>> {
 typedef mvector<dataa..., datab...> result_type;
};

二つのベクトルを統合して、主に分割後のベクトルに使います。
最大値を探す

template<int now_index, typename U, typename V>
struct FindMax;

template<int now_index, int ...Looped, int ...unLooped>
struct FindMax<now_index, mvector<Looped...>, mvector<unLooped...>> {
 typedef FindMax<now_index + 1, mvector<Looped..., mvector<unLooped...>::value>, typename mvector<unLooped...>::next_type> next_max;
 constexpr static int max = mvector<unLooped...>::value > next_max::max ? mvector<unLooped...>::value : next_max::max;
 constexpr static int max_index = mvector<unLooped...>::value > next_max::max ? now_index : next_max::max_index;
};

template<int now_index, int ...Looped>
struct FindMax<now_index, mvector<Looped...>, mvector<>> {
 typedef FindMax<now_index, mvector<Looped...>, mvector<>> next_max;
 constexpr static int max = -1;
 constexpr static int max_index = now_index;
};

ベクトルの最大値を探します。入力はnow_がありますindex,Looped(既に比較されている部分),unlooped(比較されていない部分)。その中のnow_indexは余分です。sizeof...(Looped)を使って代替できます。
出力はmax(最大値)、max_index(最大値の位置は、後の分割に便利です。)
並べ替え
データ操作が完了しました。このプログラムは大半を完成しました。並べ替えもとても簡単です。並べ替えられていないリストの中で、一番大きな値を選んで、並べ替えられたリストの前に置いてください。

//   
template<typename T, typename S>
struct SelectSortWork;

template<int ...unSorted, int ...Sorted>
struct SelectSortWork<mvector<unSorted...>, mvector<Sorted...>> {
 typedef FindMax<0, mvector<>, mvector<unSorted...>> max_find_type;
 constexpr static int max = max_find_type::max;
 constexpr static int max_index = max_find_type::max_index;
 typedef SplitVector<max_index, mvector<>, mvector<unSorted...>> split_type;
 typedef SelectSortWork<typename MergeVector<typename split_type::LeftVector, typename split_type::RightVector>::result_type, mvector<max, Sorted...>> next_select_sort_work_type;
 typedef typename next_select_sort_work_type::sorted_type sorted_type;
};

template<int ...Sorted>
struct SelectSortWork<mvector<>, mvector<Sorted...>> {
 typedef mvector<Sorted...> sorted_type;
};
締め括りをつける
コードはgithubのgistに置いてあります。Super Template Tetris
全体としては、コードは非常に単純であり、合理的に分解すれば、ほとんどのアルゴリズムは実現できるはずである。
プログラミングの過程で、私もいくつかの自分の悟りがあります。テンプレートのメタプログラミングのいくつかのTipsについて、ここで紹介しましょう。
  • 関数式プログラミングに慣れたら、テンプレートの要素プログラミングを勉強します。その中の理解はもっと深いので、勉強を始める前に、まず関数式プログラミングを勉強したほうがいいです。
  • クラスのテンプレートは、関数として見なされ、入出力があります。入力はテンプレートのパラメータであり、出力はテンプレート内のタイプや変数であり、これらの出力は関数として計算された中間変数でもあり、符号化に便利です。
  • テンプレートの元はプログラミングして、きっと根気良いことがあって、特にdebug、とても苦しいことができます。
  • ここでC++テンプレートのメタプログラミングについての選択順位を達成するための文章を紹介します。より多くの関連C++選択順位の内容を紹介します。以前の文章を検索したり、下記の関連記事を見たりしてください。これからもよろしくお願いします。