Sort a tuple of integral constants at compile-time

Question

In all the following T is std::integral_constant<int, X>.

How to design a structure and a function taking a list of integral constants as an input, and returning a std::tuple<std::integral_constant<int, X>...> in which the constants have been sorted?

template <class... T>
struct ordered_tuple;

template <class... T>
constexpr typename ordered_tuple<T...>::type make_ordered_tuple(T&&...);

The use would be:

std::integral_constant<int, 5> i5;
std::integral_constant<int, 4> i4;
std::integral_constant<int, 9> i9;
std::integral_constant<int, 1> i1;
auto tuple = make_ordered_tuple(i5, i4, i9, i1);

Have you taken a look to boost::mpl? I thought something like this is already done. Aleksandrescu sorted tuples in inheritance order long before C++11 PS: http://www.boost.org/doc/libs/1_55_0/libs/mpl/doc/refmanual/sort.html — Minor Threat, Dec 11 '15 at 23:19
@MinorThreat: doing a pure, self-contained C++11 solution using only variadic templates, pack expansions, etc., is also pretty useful though, and I guess that's what OP is after — Chris Beck, Dec 12 '15 at 00:06
In C++14 you can insert the values into an `std::array`, sort that using a `constexpr` implementation of insertion sort or whatnot, then unpack the array into a tuple. In C++11, it would be more painful. Do you have C++14 support? — Brian Bi, Dec 12 '15 at 00:08
Closely related: http://stackoverflow.com/questions/32169249/how-can-i-arbitrarily-sort-a-tuples-types — 101010, Dec 12 '15 at 00:36
In your example, `make_ordered_tuple` as declared will return an `ordered_tuple` of references. Is that what you want - references to the original `i1`, `i5`, etc. objects? If not, is there a reason for working with tuples of objects of `integral_constant<...>` type and not just simple type lists? — bogdan, Dec 12 '15 at 01:56

score 4 · Accepted Answer · edited May 23 '17 at 12:31

Here's one way to do it. I implemented merge sort, which is quite amenable to functional programming. It's less than 200 lines. Most of it is based on metafunctions I used in an earlier answer. And that is based on stuff that many other people have used in SO questions, related to basic operations on typelist's and such...

One way to improve would be to reduce the template recursion depth required, currently it is O(n). I guess that it could be O(log n) but I'm not actually sure, it depends if you can find a way to rewrite the merge metafunction. (Similarly to what Yakk pointed out in the other question.)

#include <type_traits>

template <class... T>
struct TypeList {
  static constexpr const std::size_t size = sizeof...(T);
};

/***
 * Concat metafunction
 */

template <typename A, typename B>
struct Concat;

template <class... As, class... Bs>
struct Concat<TypeList<As...>, TypeList<Bs...>> {
  typedef TypeList<As..., Bs...> type;
};

template <typename A, typename B>
using Concat_t = typename Concat<A, B>::type;

/***
 * Split metafunction
 */

template <int i, typename TL>
struct Split;

template <int k, typename... TL>
struct Split<k, TypeList<TL...>> {
private:
  typedef Split<k / 2, TypeList<TL...>> FirstSplit;
  typedef Split<k - k / 2, typename FirstSplit::R> SecondSplit;

public:
  typedef Concat_t<typename FirstSplit::L, typename SecondSplit::L> L;
  typedef typename SecondSplit::R R;
};

template <typename T, typename... TL>
struct Split<0, TypeList<T, TL...>> {
  typedef TypeList<> L;
  typedef TypeList<T, TL...> R;
};

template <typename T, typename... TL>
struct Split<1, TypeList<T, TL...>> {
  typedef TypeList<T> L;
  typedef TypeList<TL...> R;
};

template <int k>
struct Split<k, TypeList<>> {
  typedef TypeList<> L;
  typedef TypeList<> R;
};

// Metafunction Subdivide: Split a typelist into two roughly equal typelists
template <typename TL>
struct Subdivide : Split<TL::size / 2, TL> {};

/***
 * Ordered tuple
 */

template <int X>
using int_t = std::integral_constant<int, X>;

template <class... T>
struct Ordered_List : TypeList<T...> {};

template <class... As, class... Bs>
struct Concat<Ordered_List<As...>, Ordered_List<Bs...>> {
  typedef Ordered_List<As..., Bs...> type;
};

/***
 * Merge metafunction
 */

template <typename A, typename B>
struct Merge;

template <typename B>
struct Merge<Ordered_List<>, B> {
  typedef B type;
};

template <int a, class... As>
struct Merge<Ordered_List<int_t<a>, As...>, Ordered_List<>> {
  typedef Ordered_List<int_t<a>, As...> type;
};

template <int a, class... As, int b, class... Bs>
struct Merge<Ordered_List<int_t<a>, As...>, Ordered_List<int_t<b>, Bs...>> {
  typedef Ordered_List<int_t<a>, As...> A;
  typedef Ordered_List<int_t<b>, Bs...> B;

  typedef typename std::conditional<a <= b,
                                    Concat_t<Ordered_List<int_t<a>>, typename Merge<Ordered_List<As...>, B>::type>,
                                    Concat_t<Ordered_List<int_t<b>>, typename Merge<A, Ordered_List<Bs...>>::type>
                                   >::type type;
};

template <typename A, typename B>
using Merge_t = typename Merge<A, B>::type;

/***
 * Mergesort metafunction
 */

template <typename TL>
struct MergeSort;

// Boilerplate base-cases
template <>
struct MergeSort<TypeList<>> {
  typedef Ordered_List<> type;
};

template <int X>
struct MergeSort<TypeList<int_t<X>>> {
  typedef Ordered_List<int_t<X>> type;
};

// Inductive step
template <int X, class... Xs>
struct MergeSort<TypeList<int_t<X>, Xs...>> {
  typedef TypeList<int_t<X>, Xs...> input_t;
  typedef Subdivide<input_t> subdivide_t;
  typedef typename MergeSort<typename subdivide_t::L>::type left_sort_t;
  typedef typename MergeSort<typename subdivide_t::R>::type right_sort_t;
  typedef Merge_t<left_sort_t, right_sort_t> type;
};

template <typename T>
using MergeSort_t = typename MergeSort<T>::type;

/***
 * Make ordered tuple impl
 */

#include <tuple>

template <typename T>
struct MakeStdTuple;

template <class... Ts>
struct MakeStdTuple<Ordered_List<Ts...>> {
  typedef std::tuple<Ts...> type;
};

template <typename T>
using MakeStdTuple_t = typename MakeStdTuple<T>::type;

template <class... T>
constexpr MakeStdTuple_t<MergeSort_t<TypeList<T...>>> make_ordered_tuple(T&&...) {
  return {};
}

static_assert(std::is_same<Ordered_List<int_t<1>, int_t<2>, int_t<3>>,
                           MergeSort_t<TypeList<int_t<1>, int_t<2>, int_t<3>>>>::value, "Failed a unit test");

static_assert(std::is_same<Ordered_List<int_t<1>, int_t<2>, int_t<3>>,
                           MergeSort_t<TypeList<int_t<2>, int_t<1>, int_t<3>>>>::value, "Failed a unit test");

static_assert(std::is_same<Ordered_List<int_t<1>, int_t<2>, int_t<3>>,
                           MergeSort_t<TypeList<int_t<3>, int_t<2>, int_t<1>>>>::value, "Failed a unit test");

int main() {}

Note also: There is a significant inefficiency right now in that, when it merges the two type lists, it uses `std::conditional` which is not the same as ternary operator and always evaluates (instantiates) both of its arguments. (Since it's just a simple template.) This means the run time (at compile-time) is `2^O(n)`, much worse than it should be. I think I know how to fix this but I didn't get around to it yet. — Chris Beck, Dec 13 '15 at 17:56

Sort a tuple of integral constants at compile-time

1 Answers1