这篇文章给大家介绍利用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;
他可以输入任意数量的整数(模板参数可以看作是输入)。
根据后面的特化,模板一共有四个属性或类型(这些可以看作是模板的输出),分别是 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; };
这个模板的主要目的是将向量从某一部分分离出来(取最大值)。
模板的输入有三个: 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 (已经比较的部分), 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上, select_sort.cpp 。
总的来说,代码还是非常的简单的,只要合理的进行分解,大部分的算法应该都是可以实现的。
在编程的过程中,我也有一些自己的领悟,对于模板元编程的几点小Tips,在这里给大家介绍一下吧。
如果熟悉函数式编程的话,再来学习模板元编程,对于其中的理解会更加的深刻,所以最好在开始准备学习之前,先学习一下函数式编程会比较好(虽然这个过程会非常的痛苦)。
类模板可以看作是一个函数,有输入输出。输入是模板的参数,输出是模板里面的类型或者变量,这些输出也可以作为函数计算的中间变量,方便编码。
模板元编程,一定要有耐心,特别是debug,会特别的难受
关于利用C++模板元编程怎么实现一个选择排序功能就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。