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.

Answer 2

This is a slight modification of the method presented by Barry, that works with Visual Studio. Instead of creating compile-time string that stores name of a function:

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

this method directly compares names of two types returned by type_name< T>::name(). Barry's method does not work when names of types T and U returned by macro __PRETTY_FUNCTION__ are separated by comma, since comma may also separate template arguments, when T or U are a class or function templates.

// length of null-terminated string
constexpr size_t cstrlen(const char* p) 
{
    size_t len = 0;
    while (*p) 
    {
        ++len;
        ++p;
    }

    return len;
}

// constexpr string representing type name
template<class T>
struct type_name
{
    static constexpr const char* name() 
    { 
        #if defined (_MSC_VER)
            return __FUNCSIG__; 
        #else
            return __PRETTY_FUNCTION__;
        #endif
    };
};

// comparison of types based on type names
template<class T1, class T2>
constexpr bool less()
{
    const char* A   = type_name<T1>::name();
    const char* B   = type_name<T2>::name();

    size_t a_len    = cstrlen(A);
    size_t b_len    = cstrlen(B);

    size_t ab_len   = (a_len < b_len) ? a_len : b_len;

    for (size_t i = 0; i < ab_len; ++i) 
    {
        if (A[i] != B[i]) 
            return A[i] < B[i];
    }

    return a_len < b_len;
}

// simple checks
template<class ... Type>
struct list;

static_assert(less<list<int, void, list<void, int>>, list<int, void, list<void, void>>>());
static_assert(less<list<int, void, list<void, int>>, list<int, void, list<void, int>, int>>());

This method works on VS. I am not sure if it works on Clang or GCC.

Answer 3

tl;dr: Get the type name at compile-time, and order by that.

Previous answers are, in my opinion, a bit idiosyncratic - at least in implementation.

At this point we have a very nice, multi-compiler-supporting, function for obtaining a type's name as a compile-time string, as a string view. I'll only quote its signature here:

template <typename T>
constexpr std::string_view type_name();

This constitutes an injective mapping from types to compile-time-comparable values. Given those, you can easily implement a selection-sort-like procedure to get the relative order of each type. Finally, you assemble a new tuple using those orders.