C++模板元編程—-堆排序

目錄

前言

經過前兩次經驗的積累,終於來到了麻煩的堆排序。在一開始接觸模板元編程的時候,我就期望有一天能夠寫出元編程堆排序的代碼。原因是看了知乎大佬的一篇文章《在簡歷上寫了「精通 C++」後……》。由於學識淺薄,感覺只能接觸到模板元編程這一部分,所以便開始了對模板元編程的研究。經過多次的學習研究,最終在今天完成了這一成就。但是時間花了三個小時左右,所以時間肯定是不能達標了,但是也算是一個比較奇特的經歷吧。

相比較於前兩種排序方式,堆排序需要交換操作,更多的判斷操作,隨機讀取等。這一些都不是模板元編程擅長的地方,但是幸運的是都是有辦法實現。

實現的一些小細節

Debug

前兩次實現的時候,運氣很好,結束的時候都沒有出現什麼bug,但是這一次的比較麻煩,出現了比較嚴重的bug。但是由於限制,沒辦法進行很好的調試。於是通過編譯器的報錯機制,我寫了一個元編程的斷言。當輸入的flag為false時,便會報錯。

template<bool>
struct m_assert;

template<>
struct m_assert<true> {
    typedef int result_type;
};

template<>
struct m_assert<false> {};

使用的時候在需要查看的類裏面,放入一個類似的語句,然後將flag改成相應的條件,就可以得到調用棧了。

typename m_assert<m_or<begin != 0, T::size != 3>::result>::result_type non_data;

實現的方法也很簡單,就是區分truefalse,當輸入為true時,結構體便有result_type類型,而false則沒有。此時如果使用其的result_type,便會產生報錯,以便觀察程序的調用。編譯輸出為:

斷言輸出

但是這一種方法沒辦法打印當前調用的輸出,因此我又增加了一層:

template<bool flag, typename ...T>
struct m_assert_print{
    typedef typename m_assert<flag>::result_type result_type;
};

使用方法也類似,如果需要打印當前調用的輸出,便將要打印的內容作為T輸入即可,譬如:

typename m_assert_print<m_or<begin != 0, T::size != 3>::result, result_type>::result_type non_data;

此時的編譯輸出為:

斷言打印輸出

可以看到相比較之前的輸出,這一次的輸出多了一層,而在這一層里,包含了需要打印的內容。

惰性求值

我一開始一直以為C++是沒有實現惰性求值的,但是經過一系列的實驗,和查找資料,好像C++是存在一定的惰性求值的。譬如

template<>
struct m_assert<false> {};

template<bool flag, typename ...T>
struct m_assert_print{
    typedef typename m_assert<flag>::result_type result_type;
};

template<bool flag>
struct ErrorType {
    typedef typename m_assert<flag>::result_type result_type;
};

struct Test {
    typedef typename m_if<true, ErrorType<true>, ErrorType<false>>::result_type::result_type result_type;
};

如果是沒有惰性求值的存在,這一段代碼是應該報錯的。因為在ErrorType<false>中引用了m_assert<fasle>::result_type。而在上一部分就提到過,應該是會必報錯的。

而對於另一個寫法

struct Test {
    typedef typename m_if<true, ErrorType<true>::result_type, ErrorType<false>::result_type>::result_type result_type;
};

編譯期卻提示錯誤,甚至將ErrorType模板修改成

template<bool flag>
struct ErrorType {
    typedef typename m_assert<flag>::result_type result1_type;
    typedef int result_type;
};

編譯器也還是會報錯。

通過查閱資料總結的話,編譯期對於出現的模板並不會全部的具現化。但是如果使用了其中的類型,便會對其進行具現化[1]。因此,通過這個特性,是有辦法設計出一些惰性加載的類,但是由於當時並不知道,所以實現的時候採取了偏特化的方法,防止編譯時走向一些奇怪的方向。

簡單的來說,就是通過增加一個valid輸入,來判斷需不需要對這個支線進行下去。如果為fasle,則返回默認值,如果為true,則返回操作後的值,配合m_if,便可以得到想要的結果。

總結

總的來說,模板元編程是C++裏面一個比較有趣的部分。由於其晦澀難懂,也成為了許多大佬秀操作的地方。但是隨着C++標準的完善,它的難度也在不斷的降低。在C++17的時候,大部分的函數都可以使用constexpr來修飾了,這讓模板元編程在值運算的時候失去了一部分函數式編程的特點。而C++20中的constraintsconcepts,讓模板偏特化有了更大的活力。

源代碼://gist.github.com/ink19/9fdcca26e89655e8c1b80da56ee04c65

Ref

[1] //www.jianshu.com/p/f2477d2c19ea

博客原文://www.cnblogs.com/ink19/p/cpp_template_heap_sort.html

Tags: