快捷導(dǎo)航

C++模板元編程實(shí)現(xiàn)選擇排序

更新時間：2020年12月13日 08:42:04 作者：ink19

這篇文章主要介紹了C++模板元編程實(shí)現(xiàn)選擇排序,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

前言

模板在C++一直是比較神秘的存在。 STL 和 Boost 中都有大量運(yùn)用模板，但是對于普通的程序員來說，模板僅限于使用。在一般的編程中，很少會有需要自己定義模板的情況。但是作為一個有理想的程序員，模板是一個繞不過去的坎。由于C++標(biāo)準(zhǔn)的不斷改進(jìn)，模板的能力越來越強(qiáng)，使用范圍也越來越廣。

在C++11中，模板增加了 constexpr ，可變模板參數(shù)，回返類型后置的函數(shù)聲明擴(kuò)展了模板的能力；增加了外部模板加快了模板的編譯速度；模板參數(shù)的缺省值，角括號和模板別名使模板的定義和使用變得更加的簡潔。

C++14中，放寬了 constexpr 的限制，增加了變量模板。

C++17中，簡化模板的構(gòu)造函數(shù)，使模板更加易用；Folding使得模板在定義中更加方便。

C++20是一個大版本更新，對于模板來說，也有很大的進(jìn)步。對于個人來說，最喜歡的應(yīng)該就是 concept 了，它讓模板可以判斷模板參數(shù)是不是符合要求，同時也對模板的特化提供了更進(jìn)一部的支持（以后再也不用看著模板成噸的報錯流淚了。）；同時它還要求大部分的STL庫都支持 constexpr ，使得很多類可以在編譯期直接使用（以后模板元編程就不是單純的函數(shù)式語言了吧，感覺以后C++的編程會變得非常奇怪）。

而隨著模板一步步的完善，大佬們發(fā)現(xiàn)模板的功能居然已經(jīng)實(shí)現(xiàn)了圖靈完備，于是各種騷操作層出不窮，比如俄羅斯方塊Super Template Tetris 。

作為一個小老弟，當(dāng)然是還沒有能力寫出一個可以媲美俄羅斯方塊的程序，不過寫一些簡單的排序還是可以的。

這里我分享的是一個選擇排序算法。為什么選擇選擇排序呢？因?yàn)樗判虻臅r候，他對于元素的位置改變是比較少的。個人感覺函數(shù)元編程最復(fù)雜的就是對元素進(jìn)行修改位置了吧。

代碼詳解

數(shù)據(jù)的結(jié)構(gòu)

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 模板，他的作用就是用來保存數(shù)據(jù)的。模板的原型是

template<int ...data>
struct mvector;

他可以輸入任意數(shù)量的整數(shù)（模板參數(shù)可以看作是輸入）。

根據(jù)后面的特化，模板一共有四個屬性或類型（這些可以看作是模板的輸出），分別是 size ， value （第一個元素的值，方便后面的迭代）， next_type （除去頭的尾部，方便迭代）， array （ mvector 的數(shù)組表現(xiàn)形式）。

數(shù)據(jù)的操作

分割向量

// 分割向量
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;
};

這個模板的主要目的是將向量從某一部分分離出來（取最大值）。

模板的輸入有三個： index （要分離的元素的位置在 RightData 的位置）， LeftData （分離的左邊）， RightData （分離的右邊）。

輸出有 LeftVector （出來的左邊）， RightVector （出來的右邊）。

合并向量

// 合并向量
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 （已經(jīng)比較的部分）， unLooped （未比較的部分）。其中 now_index 是多余的，可以使用 sizeof...(Looped) 來代替。

輸出是 max （最大值）， max_index （最大值的位置，方便后面的分割）

排序

對數(shù)據(jù)操作完成了，這個程序也就完成了一大半了，排序也是非常的簡單，從未排序的列表中，選擇最大的值，放到已經(jīng)排序好的列表的前面就好了。

// 排序
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;
};

總結(jié)

代碼我放在了github的gist上， select_sort.cpp 。

總的來說，代碼還是非常的簡單的，只要合理的進(jìn)行分解，大部分的算法應(yīng)該都是可以實(shí)現(xiàn)的。

在編程的過程中，我也有一些自己的領(lǐng)悟，對于模板元編程的幾點(diǎn)小Tips，在這里給大家介紹一下吧。

如果熟悉函數(shù)式編程的話，再來學(xué)習(xí)模板元編程，對于其中的理解會更加的深刻，所以最好在開始準(zhǔn)備學(xué)習(xí)之前，先學(xué)習(xí)一下函數(shù)式編程會比較好（雖然這個過程會非常的痛苦）。
類模板可以看作是一個函數(shù)，有輸入輸出。輸入是模板的參數(shù)，輸出是模板里面的類型或者變量，這些輸出也可以作為函數(shù)計算的中間變量，方便編碼。
模板元編程，一定要有耐心，特別是debug，會特別的難受

到此這篇關(guān)于C++模板元編程實(shí)現(xiàn)選擇排序的文章就介紹到這了,更多相關(guān)C++ 選擇排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: