fork download
copy 
  1. #include <iostream>
  2. #include <type_traits>
  3.  
  4. // =====================================================================
  5. // 1. Boost.MPL Core Components
  6. // =====================================================================
  7.  
  8. // An MPL vector is just a type holding a list of other types.
  9. template <typename... Ts>
  10. struct vector {};
  11.  
  12. // An MPL int_ represents an integer as a TYPE.
  13. template <int N>
  14. struct int_ : std::integral_constant<int, N> {};
  15.  
  16. // A generic less-than predicate for types.
  17. template <typename T1, typename T2>
  18. struct less : std::integral_constant<bool, (T1::value < T2::value)> {};
  19.  
  20. // =====================================================================
  21. // 2. Type-Level Concatenation (Joining lists)
  22. // =====================================================================
  23. template <typename L1, typename L2, typename L3>
  24. struct concat;
  25.  
  26. // Specialization to extract the types from three vectors and merge them
  27. template <typename... T1, typename... T2, typename... T3>
  28. struct concat<vector<T1...>, vector<T2...>, vector<T3...>> {
  29.     using type = vector<T1..., T2..., T3...>;
  30. };
  31.  
  32. // =====================================================================
  33. // 3. Type-Level Partitioning (Splitting list around a pivot)
  34. // =====================================================================
  35. template <bool Cond, typename T, typename Less, typename GreaterEq>
  36. struct push_impl;
  37.  
  38. // If true: push to Less vector
  39. template <typename T, typename... L, typename... G>
  40. struct push_impl<true, T, vector<L...>, vector<G...>> {
  41.     using less = vector<L..., T>;
  42.     using greater_eq = vector<G...>;
  43. };
  44.  
  45. // If false: push to GreaterEq vector
  46. template <typename T, typename... L, typename... G>
  47. struct push_impl<false, T, vector<L...>, vector<G...>> {
  48.     using less = vector<L...>;
  49.     using greater_eq = vector<G..., T>;
  50. };
  51.  
  52. template <typename Pivot, typename List, template<typename, typename> class Pred, typename LessList = vector<>, typename GreaterEqList = vector<>>
  53. struct partition;
  54.  
  55. // Base Case: Empty List
  56. template <typename Pivot, template<typename, typename> class Pred, typename LessList, typename GreaterEqList>
  57. struct partition<Pivot, vector<>, Pred, LessList, GreaterEqList> {
  58.     using less = LessList;
  59.     using greater_eq = GreaterEqList;
  60. };
  61.  
  62. // Recursive Case: Evaluate Head against Pivot, push to correct list, recurse on Tail
  63. template <typename Pivot, typename Head, typename... Tail, template<typename, typename> class Pred, typename LessList, typename GreaterEqList>
  64. struct partition<Pivot, vector<Head, Tail...>, Pred, LessList, GreaterEqList> {
  65.     // 1. Check if Head < Pivot
  66.     static constexpr bool is_less = Pred<Head, Pivot>::value;
  67.  
  68.     // 2. Route the Head into the temporary less/greater lists
  69.     using step = push_impl<is_less, Head, LessList, GreaterEqList>;
  70.  
  71.     // 3. Recurse down the Tail
  72.     using recurse = partition<Pivot, vector<Tail...>, Pred, typename step::less, typename step::greater_eq>;
  73.  
  74.     using less = typename recurse::less;
  75.     using greater_eq = typename recurse::greater_eq;
  76. };
  77.  
  78. // =====================================================================
  79. // 4. THE SORT ALGORITHM (Type-Level Quicksort)
  80. // =====================================================================
  81. template <typename List, template<typename, typename> class Pred = less>
  82. struct sort;
  83.  
  84. // Base Case: Empty list is already sorted
  85. template <template<typename, typename> class Pred>
  86. struct sort<vector<>, Pred> {
  87.     using type = vector<>;
  88. };
  89.  
  90. // Recursive Quicksort
  91. template <typename Pivot, typename... Tail, template<typename, typename> class Pred>
  92. struct sort<vector<Pivot, Tail...>, Pred> {
  93.     // 1. Partition the Tail around the Pivot
  94.     using parts = partition<Pivot, vector<Tail...>, Pred>;
  95.  
  96.     // 2. Sort the Less list
  97.     using sorted_less = typename sort<typename parts::less, Pred>::type;
  98.  
  99.     // 3. Sort the Greater list
  100.     using sorted_greater = typename sort<typename parts::greater_eq, Pred>::type;
  101.  
  102.     // 4. Concat: [Sorted Less] + [Pivot] + [Sorted Greater]
  103.     using type = typename concat<sorted_less, vector<Pivot>, sorted_greater>::type;
  104. };
  105.  
  106. // =====================================================================
  107. // PROOF IT WORKS (Strictly Compile-Time Verification)
  108. // =====================================================================
  109.  
  110. using UnsortedData = vector<int_<8>, int_<3>, int_<9>, int_<1>, int_<4>>;
  111.  
  112. // 💥 THE COMPILER SORTS THE TYPES HERE 💥
  113. using SortedData = sort<UnsortedData>::type;
  114.  
  115. // We use std::is_same to prove to the compiler that SortedData is exactly 
  116. // equivalent to a manually sorted vector. If this fails, compilation stops.
  117. static_assert(std::is_same<
  118.     SortedData, 
  119.     vector<int_<1>, int_<3>, int_<4>, int_<8>, int_<9>>
  120. >::value, "Boost.MPL Sort Failed!");
  121.  
  122. int main() {
  123.     std::cout << "Type-Level Metaprogramming Sort successful!\n";
  124.     std::cout << "The sorting didn't happen in 0ms... it never 'happened' at all.\n";
  125.     std::cout << "The types themselves dictate the sorted order.\n";
  126.     return 0;
  127. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Type-Level Metaprogramming Sort successful!
The sorting didn't happen in 0ms... it never 'happened' at all.
The types themselves dictate the sorted order.
https://ideone.com/fVLLrM
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!