C++模板元編程—-快速排序
目錄
簡介
上一篇使用C++模板模板實現了一個選擇排序。這一次，更進一步的，實現了一個快速排序演算法。關於快速排序的可以看這一篇文章快速排序
實現
和上一次一樣，我把快速排序演算法分為幾個小的步驟，分別實現，然後聯合在一起，實現演算法。
數據結構定義
和之前類似，不過多定義了一個head_type，同時對一些類型進行了改名。
// 數據結構定義
template<int ...>
struct mvector;
template<int ...data, int _head>
struct mvector<_head, data...> {
constexpr static int head = _head;
typedef mvector<_head> head_type;
typedef mvector<data...> tail_type;
constexpr static std::array<int, 1 + sizeof...(data)> value = {_head, data...};
};
template<int _head>
struct mvector<_head> {
constexpr static int head = _head;
typedef mvector<_head> head_type;
typedef mvector<> tail_type;
constexpr static std::array<int, 1> value = {_head};
};
template<>
struct mvector<> {
constexpr static int head = -1;
typedef mvector<> head_type;
typedef mvector<> tail_type;
constexpr static std::array<int, 0> value = {};
};
在數組前添加一個元素
// 在數組前增加一個元素
template<int data, typename list>
struct add_to_list;
template<int data, int ...data_list>
struct add_to_list<data, mvector<data_list...>> {
typedef mvector<data, data_list...> result_type;
};
判斷
// 判斷，輸出一個類型
template<bool, typename T, typename S>
struct m_type_if;
template<typename T, typename S>
struct m_type_if<true, T, S> {
typedef T result_type;
typedef S not_result_type;
};
template<typename T, typename S>
struct m_type_if<false, T, S> {
typedef S result_type;
typedef T not_result_type;
};
分堆
根據第一個元素，將不同的元素分在不同的數組中
// 分堆
template<typename , typename>
struct m_diff;
template<typename _mid, int ...data, int data_head>
struct m_diff<_mid, mvector<data_head, data...>> {
typedef _mid mid;
typedef m_diff<_mid, mvector<data...>> next_type;
typedef typename m_type_if<data_head < mid::head, typename add_to_list<data_head, typename next_type::right_type>::result_type, typename next_type::right_type>::result_type right_type;
typedef typename m_type_if<data_head >= mid::head, typename add_to_list<data_head, typename next_type::left_type>::result_type, typename next_type::left_type>::result_type left_type;
};
template<typename _mid>
struct m_diff<_mid, mvector<>> {
typedef _mid mid;
typedef m_diff<_mid, mvector<>> next_type;
typedef mvector<> right_type;
typedef mvector<> left_type;
};
合併
// 合併
template<typename, typename, typename>
struct combine_result;
template<int ...data_S, int mid, int ...data_T>
struct combine_result<mvector<data_S...>, mvector<mid>, mvector<data_T...>> {
typedef mvector<data_S..., mid, data_T...> result_type;
};
快速排序的實現
// 快排
template<typename data>
struct QuickSortWork;
template<int ...data>
struct QuickSortWork<mvector<data...>> {
typedef m_diff<typename mvector<data...>::head_type, typename mvector<data...>::tail_type> diffed_type;
typedef typename QuickSortWork<typename diffed_type::right_type>::result_type right_type;
typedef typename QuickSortWork<typename diffed_type::left_type>::result_type left_type;
typedef typename combine_result<right_type, typename mvector<data...>::head_type, left_type>::result_type result_type;
};
template<>
struct QuickSortWork<mvector<>> {
typedef mvector<> result_type;
};
template<int ...data>
struct QuickSort {
typedef QuickSortWork<mvector<data...>> work_type;
constexpr static std::array<int, sizeof...(data)> result = work_type::result_type::value;
};
總結
源程式碼：//gist.github.com/ink19/2dd0c466db4a11611a9b75e78dd25b4e
和之前的感覺類似，不過使用更加順手了。
部落格原文：部落格原文：//www.cnblogs.com/ink19/p/cpp_template_quick_sort.html
