时间:2021-05-20
模板在C++一直是比较神秘的存在。 STL 和 Boost 中都有大量运用模板,但是对于普通的程序员来说,模板仅限于使用。在一般的编程中,很少会有需要自己定义模板的情况。但是作为一个有理想的程序员,模板是一个绕不过去的坎。由于C++标准的不断改进,模板的能力越来越强,使用范围也越来越广。
在C++11中,模板增加了 constexpr ,可变模板参数,回返类型后置的函数声明扩展了模板的能力;增加了外部模板加快了模板的编译速度;模板参数的缺省值,角括号和模板别名使模板的定义和使用变得更加的简洁。
C++14中,放宽了 constexpr 的限制,增加了变量模板。
C++17中,简化模板的构造函数,使模板更加易用;Folding使得模板在定义中更加方便。
C++20是一个大版本更新,对于模板来说,也有很大的进步。对于个人来说,最喜欢的应该就是 concept 了,它让模板可以判断模板参数是不是符合要求,同时也对模板的特化提供了更进一部的支持(以后再也不用看着模板成吨的报错流泪了。);同时它还要求大部分的STL库都支持 constexpr ,使得很多类可以在编译期直接使用(以后模板元编程就不是单纯的函数式语言了吧,感觉以后C++的编程会变得非常奇怪)。
而随着模板一步步的完善,大佬们发现模板的功能居然已经实现了图灵完备,于是各种骚操作层出不穷,比如俄罗斯方块Super Template Tetris 。
作为一个小老弟,当然是还没有能力写出一个可以媲美俄罗斯方块的程序,不过写一些简单的排序还是可以的。
这里我分享的是一个选择排序算法。为什么选择选择排序呢?因为它排序的时候,他对于元素的位置改变是比较少的。个人感觉函数元编程最复杂的就是对元素进行修改位置了吧。
这里我们定义了一个 mvcetor 模板,他的作用就是用来保存数据的。模板的原型是
template<int ...data>struct mvector;他可以输入任意数量的整数(模板参数可以看作是输入)。
根据后面的特化,模板一共有四个属性或类型(这些可以看作是模板的输出),分别是 size , value (第一个元素的值,方便后面的迭代), next_type (除去头的尾部,方便迭代), array ( mvector 的数组表现形式)。
分割向量
这个模板的主要目的是将向量从某一部分分离出来(取最大值)。
模板的输入有三个: index (要分离的元素的位置在 RightData 的位置), LeftData (分离的左边), RightData (分离的右边)。
输出有 LeftVector (出来的左边), RightVector (出来的右边)。
合并向量
将两个向量合并,主要是用在分割后的向量。
寻找最大值
寻找向量中的最大值。输入有 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,在这里给大家介绍一下吧。
到此这篇关于C++模板元编程实现选择排序的文章就介绍到这了,更多相关C++ 选择排序内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文针对C++函数模板与类模板进行了较为详尽的实例解析,有助于帮助读者加深对C++函数模板与类模板的理解。具体内容如下:泛型编程(GenericProgramm
C++编程优与Pascal的原因之一是C++中存在STL(标准模板库)。STL存在很多有用的方法。C++模板库中的许多方法都需要相关参数有序,例如Sort()。
分数排序的特殊问题在java中实现排序远比C/C++简单,我们只要让集合中元素对应的类实现Comparable接口,然后调用Collections.sort()
C++基数排序 大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是
c语言中sort,表示对给定区间所有元素进行排序。 C语言是一门面向过程的计算机编程语言,与C++、Java等面向对象编程语言有所不同。C语言的设计目标是提供