Modern C++模板元编程

#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))
MAX(a++, b++) // (((a++) > (b++)) ? (a++) : (b++))
MAX(0, "123") // runtime error

void qsort( void *ptr, size_t count, size_t size,
    int (*comp)(const void *, const void *) );

int values[] = { 88, 56, 100, 2, 25 };
int cmpfunc (const void* a, const void* b) {
   return ( *(int*)a - *(int*)b );
}
qsort(values, 5, sizeof(int), cmpfunc);

template<typename T>
T max(T&& a, T&& b) {
    return a > b ? a : b;
}

max(0, "123"); // error: no matching function for call to 'max(int, const char [4])'

template<typename RandomIt, typename Compare>
void sort(RandomIt first, RandomIt last, Compare comp);

int values[] = { 88, 56, 100, 2, 25 };
std::sort(values, values + 5, [](int a, int b) {
    return a < b;
});

// collection.h
struct Collection_ ## TYPE {
    TYPE *array; (1)
    size_t size, n;
};

#ifdef INSTANCE (2)
Collection_ ## TYPE make_Collection_ ## TYPE(size_t sz) {
    // ...
}
#endif

// main.cpp
#define INSTANCE

#define TYPE int (1)
#include "collection.h"
#undef TYPE

#define TYPE double(1)
#include "collection.h"
#undef TYPE

int main() {
    Collection_int lstInt = make_Collection_int(5); (2)
    Collection_double lstDouble = make_Collection_double(5);
}

// collection.h
template <typename T> (1)
class Collection {
    T* array;
    size_t size, n;
public:
    Collection(size_t sz) {
        // ...
    }
};

// main.cpp
int main() {
    Collection<int> lstInt(5); (2)
    Collection<double> lstDouble(5); (2)
}

template <typename ...Ts> (1)
struct TypeList {
    using type = TypeList<Ts...>; (2)
    constexpr static size_t size = sizeof...(Ts); (3)
};

template <typename ...Ts>
struct TypeList {
  template <typename ...T> (1)
  using append = TypeList<Ts..., T...>; (2)
};

TypeList<int, char>::append<long, double> // TypeList<int, char, long, double>

template <typename ...Ts>
struct TypeList {
    template <template<typename...> typename T> (1)
    using exportTo = T<Ts...>; (2)
};

TypeList<int, char>::exportTo<std::tuple> // std::tuple<int, char>
TypeList<int, char>::exportTo<std::variant> // std::variant<int, char>

template<typename RandomIt, typename Compare>
void sort(RandomIt first, RandomIt last, Compare comp); (1)

SUBROUTINE example ( D, N, M, dirVs, ret )
  INTEGER i, j, k, D, N, M, len
  INTEGER ia(M), ret(D,N), dirVs(M,D)
  DO i = 1, N
    len = 0
    DO k = 1, M
      IF( test(i,k) ) THEN
        len     = len + 1
        ia(len) = k
    ENDIF  ENDDO
    DO j = 1, D
      ret(j, i) = 0
      DO k = 1, len
        ret(j,i) = ret(j,i) XOR dirVs(ia(k), j)
      ENDDO
      IF(i .GT. 1)
        ret(j,i) = ret(j,i) XOR ret(j,i-1)
    ENDDO
ENDDO END

example n m dirVs = --  d×m n×d
    let lbody i = (let ia     = filter (test i) [0..m-1]
                       xorV v = fold xor 0 [v!j| j<-ia]
                  in map xorV dirVs)
            ret = map lbody [1..n]
            e   = replicate (length dirVs) 0
    in tail (scan (zipWith xor) e ret)

template<typename IN, template <typename> class F> (1)
struct Map; (2)

template<template <typename> class F, typename ...Ts>
struct Map<TypeList<Ts...>, F> {
    using type = TypeList<typename F<Ts>::type...>; (3)
};

template<typename IN, template <typename> class F>
using Map_t = typename Map<IN, F>::type;

template<typename IN, typename IN2>    (1)
class Concat {
    template<typename ACC, typename E> (2)
    struct Append: ACC::template append<E> { };
public:
    using type = Fold_t<IN2, IN, Append>; (3)
};

template<typename IN, typename IN2>
using Concat_t = typename Concat<IN, IN2>::type;

Concat_t<TypeList<int, char>, TypeList<float>> // TypeList<int, char, float>

template<typename IN, typename IN2>
struct Concat;

template<typename ...Ts, typename ...Ts2>
struct Concat<TypeList<Ts...>, TypeList<Ts2...>> { (1)
    using type = TypeList<Ts..., Ts2...>; (2)
};

template<typename IN, typename IN2>
using Concat_t = typename Concat<IN, IN2>::type;

template<typename IN, typename IN2>
struct Concat: IN2::template exportTo<IN::template append> { }; (1)

template<typename IN, typename IN2>
using Concat_t = typename Concat<IN, IN2>::type;

template<typename IN, typename E> (1)
class Elem {
    template<typename ACC, typename T>
    struct FindE: std::conditional_t<ACC::value, ACC, std::is_same<T, E>> {} ; (2)

    using Found = Fold_t<IN, std::false_type, FindE>; (3)
public:
    constexpr static bool value = Found::value; (4)
};

template<typename IN, typename E>
constexpr bool Elem_v = Elem<IN, E>::value;

Elem_v<TypeList<int>, int>; // true
Elem_v<TypeList<int>, float>; // false

template<typename IN, typename E>
struct Elem {
    constexpr static bool value = false; (1)
};

template<typename E, typename ...Ts>
struct Elem<TypeList<Ts...>, E> {
    constexpr static bool value = (std::is_same_v<E, Ts> || ...); (2)
};

template<typename IN, typename E>
constexpr bool Elem_v = Elem<IN, E>::value;

template<typename IN, template<typename, typename> class CMP> (1)
struct QuickSort { using type = TypeList<>; };                (2)
template<typename IN, template<typename, typename> class CMP>
using QuickSort_t = typename QuickSort<IN, CMP>::type;

template<template<typename, typename> class CMP, typename PIVOT, typename ...Ts>
class QuickSort<TypeList<PIVOT, Ts...>, CMP> {
    using tails = TypeList<Ts...>;
    template<typename E>
    struct LT { constexpr static bool value = CMP<E, PIVOT>::value; };  (3)
    template<typename E>
    struct GE { constexpr static bool value = !CMP<E, PIVOT>::value; }; (3)

    using SmallerSorted = QuickSort_t<Filter_t<tails, LT>, CMP>; (4)
    using BiggerSorted = QuickSort_t<Filter_t<tails, GE>, CMP>;  (4)
public:
    using type = Concat_t<typename SmallerSorted::template append<PIVOT>, BiggerSorted>; (5)
};

template<typename LHS, typename RHS> (1)
struct SizeCmp {
    constexpr static bool value = sizeof(LHS) < sizeof(RHS); (1)
};

QuickSort_t<
    TypeList<char, float, double, int, char>,
    SizeCmp> // TypeList<char, char, float, int, double>>

def find_shortest_path(from, to, path = []):         (1)
    if from == to: return path   # reach target      (2)
    if from in path: return []   # find cycle        (3)
    for each (from, v) in edges: # expand next nodes (4)
        cur_path = from + find_shortest_path(v, to)  (5)
        path = min(path, cur_path)                   (6)
    return path

template<char ID>
struct Node { constexpr static char id = ID; };
using A = Node<'A'>;
using B = Node<'B'>;
using C = Node<'C'>;
using D = Node<'D'>;
using E = Node<'E'>;

using g = Graph< (1)
    link(node(A) -> node(B) -> node(C) -> node(D)),
    link(node(A) -> node(C)),  // test shortest path: A -> C -> D
    link(node(B) -> node(A)),  // test cycle
    link(node(A) -> node(E))>; // test D -> E unreachable

static_assert(g::getPath('A', 'D').sz == 3);    // compile-time test (2)
auto path = g::getPath(argv[1][0], argv[2][0]); // runtime test      (2)
std::cout << " path size: " << path.sz << std::endl;

using g = Graph< (1)
    link(node(A) -> node(B) -> node(C) -> node(D)),
    link(node(A) -> node(C)),  // test shortest path: A -> C -> D
    link(node(B) -> node(A)),  // test cycle
    link(node(A) -> node(E))>; // test D -> E unreachable

using g = Graph<
    auto(*)(A) -> auto(*)(B) -> auto(*)(C) -> auto(*)(D) -> void,
    auto(*)(A) -> auto(*)(C) -> void,
    auto(*)(B) -> auto(*)(A) -> void,
    auto(*)(A) -> auto(*)(E) -> void>;

template<typename F, typename T>
struct Edge {
    using From = F;
    using To = T;
};

template<typename Node = void>
struct EdgeTrait {
    template<typename Edge> struct IsFrom (1)
    { constexpr static bool value = std::is_same_v<typename Edge::From, Node>; };
    template<typename Edge> struct IsTo   (1)
    { constexpr static bool value = std::is_same_v<typename Edge::To, Node>; };
    template<typename Edge> (2)
    struct GetFrom { using type = typename Edge::From; };
    template<typename Edge> (2)
    struct GetTo { using type = typename Edge::To; };
};

template<typename T, typename OUT = TypeList<>>
struct Chain;

template<typename F, typename OUT>
struct Chain<auto(*)(F) -> void, OUT> {
    using From = F;
    using type = OUT; (1)
};

template<typename F, typename T, typename OUT>
struct Chain<auto(*)(F) -> T, OUT> {
private:
    using To = typename Chain<T, OUT>::From;
public:
    using From = F;
    using type = typename Chain<T,
          typename OUT::template append<Edge<From, To>>>::type; (2)
};

template<typename... Chains> (1)
class Graph {
    using Edges = Fold_t<    (2)
        TypeList<typename Chain<Chains>::type...>,
        TypeList<>,
        Concat>;
    ...
};

// def find_shortest_path(from, to, path = []):
template<typename FROM, typename TARGET,         (1)
    typename PATH = TypeList<>, typename = void> (2)
struct PathFinder;

// if from == to: return path # reach target
template<typename TARGET, typename PATH>
struct PathFinder<TARGET, TARGET, PATH>: (1)
    PATH::template append<TARGET> { };   (2)

// if from in path: return []   # find cycle
template<typename CURR_NODE, typename TARGET, typename PATH>
struct PathFinder<CURR_NODE, TARGET, PATH,
    std::enable_if_t<Elem_v<PATH, CURR_NODE>>>: (1)
    TypeList<> {}; // return empty path (2)

template<typename CURR_NODE, typename TARGET, typename PATH>
class PathFinder<CURR_NODE, TARGET, PATH,
    std::enable_if_t<! std::is_same_v<CURR_NODE, TARGET>
        && !Elem_v<PATH, CURR_NODE>>> { (1)
    using EdgesFrom = Filter_t<Edges, EdgeTrait<CURR_NODE>::template IsFrom>; (2)
    // for each (from, v) in edges: # expand next nodes
    using NextNodes = Map_t<EdgesFrom, EdgeTrait<>::GetTo>; (3)
    // cur_path = from + find_shortest_path(v, to)
    template<typename NEXT_NODE>
    struct GetPath: PathFinder<NEXT_NODE, TARGET,
        typename PATH::template append<CURR_NODE>> {};
    using AllPaths = Map_t<NextNodes, GetPath>; (4)
    template<typename ACC, typename Path> struct MinPath:
        std::conditional_t<(ACC::size == 0 ||
            ((ACC::size > Path::size) && Path::size > 0)), Path, ACC> {};
public:
    // path = min(path, cur_path)
    using type = Fold_t<AllPaths, TypeList<>, MinPath>; (5)
};

template<typename A, typename B,
    template<typename, typename> class PAIR>
struct CrossProduct;

template<typename A, typename B, template<typename, typename> class PAIR>
using CrossProduct_t = typename CrossProduct<A, B, PAIR>::type;

template<typename A, typename B, template<typename, typename> class PAIR>
class CrossProduct {
    template<typename RESULT_OUTTER, typename TA>    (1)
    struct OuterAppend {
        template<typename RESULT_INNER, typename TB> (2)
        struct InnerAppend: RESULT_INNER::template append<PAIR<TA, TB>> { };
        using type = Fold_t<B, RESULT_OUTTER, InnerAppend>;
    };
public:
    using type = Fold_t<A, TypeList<>, OuterAppend>;
};

using AllPairs = CrossProduct_t<
    Unique_t<Map_t<Edges, EdgeTrait<>::GetFrom>>,
    Unique_t<Map_t<Edges, EdgeTrait<>::GetTo>>,
    std::pair>;

template<typename NODE_TYPE>
struct Path {
    const NODE_TYPE* path;
    size_t sz;
};

template<typename NODE, typename... NODEs>
class PathStorage { (1)
    using NODE_TYPE = std::decay_t<decltype(NODE::id)>;
    constexpr static NODE_TYPE pathStorage[] { NODE::id, NODEs::id... };
public:
    constexpr static Path<NODE_TYPE> path {
        .path = pathStorage,
        .sz   = sizeof...(NODEs) + 1,
    };
};

template<typename PAIR>
struct GetPath {
    using type = std::pair<PAIR,
        typename PathFinder<typename PAIR::first_type,
                            typename PAIR::second_type>::type>;
};

using AllPaths = Map_t<AllPairs, GetPath>;

template<typename PATH_PAIR>
struct IsNonEmptyPath {
    constexpr static bool value = (PATH_PAIR::second_type::size > 0);
};

using AllNonEmptyPaths = Filter_t<AllPaths, IsNonEmptyPath>;

template<typename PATH_PAIR>
struct SavePath {
    using type = std::pair<typename PATH_PAIR::first_type,
            typename PATH_PAIR::second_type::template exportTo<PathStorage>>; (1)
};

using SavedPaths = Map_t<AllNonEmptyPaths, SavePath>; (2)

template<typename NODE_TYPE, typename FROM, typename TARGET, typename PATH>
constexpr static bool matchPath(NODE_TYPE from, NODE_TYPE to,
        Path<NODE_TYPE>& result, std::pair<std::pair<FROM, TARGET>, PATH>) {
    if (FROM::id == from && TARGET::id == to) { (1)
        result = PATH::path;                    (1)
        return true;
    }
    return false;
}

template<typename NODE_TYPE, typename ...PATH_PAIRs>
constexpr static void matchPath(NODE_TYPE from, NODE_TYPE to,
        Path<NODE_TYPE>& result, TypeList<PATH_PAIRs...>) {
    (matchPath(from, to, result, PATH_PAIRs{}) || ...); (2)
}

// export compile/run-time interface
template<typename NODE_TYPE>
constexpr static Path<NODE_TYPE> getPath(NODE_TYPE from, NODE_TYPE to) { (3)
    Path<NODE_TYPE> result{};
    matchPath(from, to, result, SavedPaths{});
    return result;
}

template<char ID>
struct Node { constexpr static char id = ID; };
using A = Node<'A'>;
using B = Node<'B'>;
using C = Node<'C'>;
using D = Node<'D'>;
using E = Node<'E'>;

using g = Graph<
    link(node(A) -> node(B) -> node(C) -> node(D)),
    link(node(A) -> node(C)),  // test shortest path: A -> C -> D
    link(node(B) -> node(A)),  // test cycle
    link(node(A) -> node(E))>; // test D -> E unreachable

static_assert(g::getPath('A', 'D').sz == 3);    // compile-time test
auto path = g::getPath(argv[1][0], argv[2][0]); // runtime test
std::cout << " path size: " << path.sz << std::endl;

tf::Executor executor;
tf::Taskflow taskflow("simple");
auto A = taskflow.emplace([]() { std::cout << "TaskA\n"; });  //          +---+
auto B = taskflow.emplace([]() { std::cout << "TaskB\n"; });  //    +---->| B |-----+
auto C = taskflow.emplace([]() { std::cout << "TaskC\n"; });  //    |     +---+     |
auto D = taskflow.emplace([]() { std::cout << "TaskD\n"; });  //  +---+           +-v-+
                                                              //  | A |           | D |
A.precede(B);  // B runs after A                              //  +---+           +-^-+
A.precede(C);  // C runs after A                              //    |     +---+     |
B.precede(D);  // D runs after B                              //    +---->| C |-----+
C.precede(D);  // D runs after C                              //          +---+
executor.run(taskflow).wait();

tf::Executor executor;
tf::Taskflow taskflow("simple");
def_task((A), { std::cout << "TaskA\n"; }); //          +---+
def_task((B), { std::cout << "TaskB\n"; }); //    +---->| B |-----+
def_task((C), { std::cout << "TaskC\n"; }); //    |     +---+     |
def_task((D), { std::cout << "TaskD\n"; }); //  +---+           +-v-+
                                            //  | A |           | D |
taskbuild(                                  //  +---+           +-^-+
  task(A)                                   //    |     +---+     |
    ->fork(B, C)                            //    +---->| C |-----+
    ->task(D)                               //          +---+
)(taskflow);
executor.run(taskflow).wait();

int counter;
struct Context {
    int &rcounter; // use counter(borrow)
} context{counter};

def_task((A, Context), { rcounter=0; });
def_task((B, Context), { rcounter++; });
def_task((C, Context), {
    if (rcounter != 5) std::cout << "loops again (goes to B)\n"; return 0;
    std::cout << "breaks the loop (goes to D)\n"; return 1;
});
def_task((D, Context), { std::cout << "done with counter equal to " << rcounter << '\n'; });

auto tasks = taskbuild(
    task(A) -> task(B) -> task(C),
    task(C) -> fork(B, D)
)(taskflow, context);