C++ Meta Templates Programming

C++ 果然是一个语言联邦...

Hello World

template <int n>
struct add {
    static constexpr int value = add<n - 1>::value + n;
};

template <>
struct add<1> {
    static constexpr int value = 1;
};

上面就是模板元编程一个类似Hello world 的示例. 调用的话就是

std::cout << add<5>::value;

实现了一个编译期的叠加的代码. 下面则是与之相同功能的Haskell代码

addFunc :: (Integral a) => a -> a
addFunc 0 = 1
addFunc x = x + addFunc (x - 1)

(其实, 这两个函数都有点儿问题, 输入是负数就gg. 为了展示起见, 不管它)
c++ 代码中第一个struct 中的是函数的实现, 第二个则是边界(其实两个都是实现). 然后通过递归一层一层的求解. 可以跟Haskell 代码进行类比.

Functional Programming

函数式编程比较重要的一点就是函数没有副作用也不会改变装填, 即多次调用同一个函数, 只要输入相同它的输出不会改变.
使用函数式编程解决问题时,常常先取一个合适的集合, 然后对这个集合进行变形, 让数据通过过滤条件, 最后得到正确的数据.

模板元编程便和函数式编程部分类似, 因为模板会在编译时期进行推倒.我们就可以使用推到展开和递归的手法来达到部分和函数式编程类似功能的函数. 上面的代码就是一个不错的例子.

当然了, 如果直接与纯的函数式编程语言如Haskell, 相比较还是有一些东西没有的. 比如不全调用啥的, 可能也没有高阶函数吧, 还没了解过...这使得c++ 代码写起来不是那么容易理解. 不过是很好玩的一个东西.

编译期插入排序

integral_constant 和 integer_sequence 分别已经在c++11 和 c++14 标准中出现定义, 那就不用自己写了.2333
integral_constant -> <type_traits>
integer_sequence -> <utility>

Haskell

下面是函数式编程的代码实现, 大概能够体现编程的思想

insert :: (Ord a) => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
    | x < y = x:y:ys
    | otherwise = y:insert x ys

insertSort :: (Ord a) => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x $ insertSort xs

C++ 版

把一些实现放到test.hpp中, 因为标准库中有integer_sequence

#ifndef TEST_HPP_
#define TEST_HPP_

#include <utility>
#include <type_traits>

// alias
template <int ... values>
using int_sequence = std::integer_sequence<int, values...>;
// 当然也可以重命名为
// template <long long ... values>
// using dlong_sequence = std::integer_sequence<long long, values...>;
// 不过我还没试过,233333



// 类似Haskell 中 `s:[]`
template <int V, typename int_sequence>
struct push_front;

template <int V, int ... values>
struct push_front<V, int_sequence<values...>> {
    using type = int_sequence<V, values...>;
};

template <int V, typename T>
using push_front_t = typename push_front<V, T>::type;


// if-else 表达式,
template <bool Cond, typename Then, typename Else>
struct conditional;

template <typename Then, typename Else>
struct conditional<true, Then, Else> { using type = Then; };

template <typename Then, typename Else>
struct conditional<false, Then, Else> { using type = Else; };

template <bool Cond, typename Then, typename Else>
using conditional_t = typename conditional<Cond, Then, Else>::type;



// insert func
template <template <int, int> typename Compare, int x, typename int_sequence>
struct insert;

template <template <int, int> typename Compare, int x>
struct insert<Compare, x, int_sequence<>> {
    using type = int_sequence<x>;
};

template <template <int, int> typename Compare, int x, int head, int ...tail>
struct insert<Compare, x, int_sequence<head, tail...>> {
    using type = typename conditional<Compare<x, head>::value,
          int_sequence<x, head, tail...>,
          typename push_front<head, typename insert<Compare, x, int_sequence<tail...>>::type>::type>::type;
};



// insert sort func
template <template <int, int> typename Compare, typename int_sequence>
struct insertion_sort;

template <template <int, int> typename Compare>
struct insertion_sort<Compare, int_sequence<>> {
    using type = int_sequence<>;
};

template <template <int, int> typename Compare, int head, int ...tail>
struct insertion_sort<Compare, int_sequence<head, tail...>> {
    using type = typename insert<Compare, head, typename insertion_sort<Compare, int_sequence<tail...>>::type>::type;
};

#endif

调用它

#include <iostream>
#include "test.hpp"

template <int a, int b>
struct lessThan {
    static const bool value = a < b;
};


// print func
template <int head>
void print(int_sequence<head> seq) {
    std::cout << head << std::endl;
}

template <int head, int ... tail>
void print(int_sequence<head, tail ...> seq) {
    std::cout << head << ' ';
    print(int_sequence<tail ...>());
}

int main(void)
{
    using s = int_sequence<4, 2, 7, 5, 3, 21>;
    print(typename insertion_sort<lessThan, s>::type());

    return 0;
}

编译的时候最好打开c++17 选项

g++ -std=c++17

error

在使用clang 和 vs 编译的时候,对于print 这个模板,都会抛出类似下面的错误.

"print": ambiguous call to overloaded function

表示在进行模板推到的时候,最后仅剩一个元素的时候,不仅匹配了print(int_sequence<1,>) 也匹配上了print(int_sequence<1>) 这两个不同的匹配项.产生出了二义化.做出下面的更改, 让它们都能编译通过.

// 不特化一个元素了,直接重载以空元素为参数的`print`
void print(int_sequence<> seq) {
    std::cout << std::endl;
}

template <int head, int ... tail>
void print(int_sequence<head, tail...> seq) {
    std::cout << head << ' ';
    print(int_sequence<tail...>());
}

上述的代码其实没有什么卵用, 2333 ~~除了好玩...~~

参考资料

模板代码来源 -> https://blog.csdn.net/huanghongxun/article/details/85065406

2019年5月

c++ Meta Templates & Haskell(Functional Programming) 和编译期插排