How to order types at compile-time?

Question

Consider the following program:

#include <tuple>
#include <vector>
#include <iostream>
#include <type_traits>

template <class T>
struct ordered {};

template <class... T>
struct ordered<std::tuple<T...>>
{
    using type = /* a reordered tuple */;
};

template <class T>
using ordered_t = typename ordered<T>::type;

int main(int argc, char* argv[])
{
    using type1 = std::tuple<char, std::vector<int>, double>;
    using type2 = std::tuple<std::vector<int>, double, char>;
    std::cout << std::is_same_v<type1, type2> << "\n"; // 0
    std::cout << std::is_same_v<ordered_t<type1>, ordered_t<type2>> << "\n"; // 1
    return 0;
}

The ordered helper has to reorder types in a tuple, such that two tuples with the sames types, but ordered differently lead to the same tuple type: which can be the first one, the second one, or even another one: it just has to have the same size, and the same elements but in a unique order (regardless of this order).

Is it possible to do this at compile-time using template metaprogramming techniques?

Answer 1

The hard part is coming up with a way to order types. Sorting a type list by a predicate is a chore, but is doable. I'll focus here on just the comparison predicate.

One way is to just create a class template that defines a unique id for each type. That works and makes for an easy comparator to write:

template <typename T, typename U>
constexpr bool cmp() { return unique_id_v<T> < unique_id_v<U>; }

But coming up with these unique ids is a hurdle that isn't necessarily feasible. Do you register them all in one file? That doesn't scale super well.

What would be great is if we could just... get the names of all the types as compile time strings. Reflection will give us that, and then this problem is trivial. Until then, we could do something slightly more dirty: use __PRETTY_FUNCTION__. Both gcc and clang are okay with using that macro in a constexpr context, although they have different formats for this string. If we have a signature like:

template <typename T, typename U>
constexpr bool cmp();

Then gcc reports cmp<char, int> as "constexpr bool cmp() [with T = char; U = int]" while clang reports it as "bool cmp() [T = char, U = int]". It's different... but close enough that we can use the same algorithm. Which is basically: figure out where T and U are in there and just do normal string lexicographic comparison:

constexpr size_t cstrlen(const char* p) {
    size_t len = 0;
    while (*p) {
        ++len;
        ++p;
    }
    return len;
}

template <typename T, typename U>
constexpr bool cmp() {
    const char* pf = __PRETTY_FUNCTION__;
    const char* a = pf + 
#ifdef __clang__
        cstrlen("bool cmp() [T = ")
#else
        cstrlen("constexpr bool cmp() [with T = ")
#endif
        ;

    const char* b = a + 1;
#ifdef __clang__
    while (*b != ',') ++b;
#else
    while (*b != ';') ++b;
#endif
    size_t a_len = b - a;
    b += cstrlen("; U = ");
    const char* end = b + 1;
    while (*end != ']') ++end;
    size_t b_len = end - b;    

    for (size_t i = 0; i < std::min(a_len, b_len); ++i) {
        if (a[i] != b[i]) return a[i] < b[i];
    }

    return a_len < b_len;
}

with some tests:

static_assert(cmp<char, int>());
static_assert(!cmp<int, char>());
static_assert(!cmp<int, int>());
static_assert(!cmp<char, char>());
static_assert(cmp<int, std::vector<int>>());

It's not the prettiest implementation, and I'm not sure it's meaningfully sanctioned by the standard, but it lets you write your sort without having to manually and carefully register all your types. And it compiles on clang and gcc. So maybe it's good enough.