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?

Ahem

Is it possible? Yes. Whatever answer you get, Andrei Alexandrescu wrote about doing such things in "Modern C++ Design" way back in 2001. The details undoubtedly will differ, but the core idea is the same. – Ovule

@StoryTeller: What if T != T2 but sizeof(T1) == sizeof(T2)? How would you uniquely sort them so that std::is_same works as expected? – Heinous

@Nawaz - Same way one does it for any other sort of data. Force the user to supply an arbitrary ordering if the library can't. It's not impossible. Could be as simple as adding a template specialization or two. – Ovule

@StoryTeller: and that turns the algorithm into a monster since it'd be very difficult to provide template specialization or such for each such pair which are equals in size. then why the question would be, why would one use such sort metafn to begin with? why not do this manually? Seems like C++ is lacking in this area. There should be a way to order types at compile-time.. a compile-time operator, equivalent to std::less<> for types, or such. – Heinous

@Nawaz - Not really a monster. A user of the library knows the handful of types they use. So they can provide specialization. And as for why using such a sort? Likely to minimize the resulting tuple size. Make it fit in a cache line, all those good stuff. – Ovule

@StoryTeller: To minimize the resulting tuple-size, one doesn't need to sort in any unique way when T1 and T2 are equal size, as any ordering (for such pair) would work then. – Heinous

@Nawaz - Yes, but what does that have to do with the issue of having more types which can be reordered to reduce a tuple size? The fact two are different and may be presented in any order is immaterial to the goal. – Ovule

@StoryTeller: Exactly. But the OP seems to be interested in the producing types which can be compared using std::is_same. So not sure about OP's eventual goal. – Heinous

@Nawaz - Well, maybe typeid could be used to break the tie in C++20. I hear there's a "constexpr all the things" proposal. Maybe... – Ovule

If your types do not repeat in tuple and these types reside in single .dll/.so I can write you a template function. Otherwise it's a lost fight – Cadaverine

@Vincent: Is it possible that this whole question is the XY problem? If all you need is to compare two tuples for equivalency, than probably there is no need to sort them - searching using type aliases techniques, even though n^2 might be faster than sorting two collections and comparing them (well, I wouldn't bet on it, but it's worth checking). – Hyperphagia

This answer required a long work to be developed, but at the end I managed to complete it. Please, leave a feedback if there is something unclear or improbable. – Oxime

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.

Somebody

In boost::hana, representations of types are equality comparable static_assert( boost::hana::type_c<char> == boost::hana::type_c<char> );, but unfortunately not less-than comparable because the type are not Orderable. This here would be a nice addition to Hana to make them orderables, a potential pitfall is that the order can end up being platform/compiler dependent. – Probability

Given template<auto> S{};, do you have any ideas on cmp<S<42>, S<42u>>()? Clang and gcc both doesn't have the type of an auto argument in the signature. BTW here's a more complete implementation godbolt.org/z/My3ktR. – Few

@PasserBy Uh... well that's unfortunate. typeid differentiates the two, but that doesn't really help here. – Somebody

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.

Communitarian

It actually does work on Clang and GCC, bar a minor error (name() needs to return a const char *: I've submitted an edit to your post). See it live on godbolt: godbolt.org/z/6FwH7x – Acrophobia

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.

Hailstorm

This answer worked great for me, but I guess I am the only upvote atm since it does not contain full working code... But yeah you solved my problem(with difference that I did not bother to trim the name since I do not care what content is as long as it enables me to order types). – Cleanthes

@NoSenseEtAl: Fixed a typo and added the missing include. Seems to compile now. – Hailstorm

See this working on GodBolt. – Hailstorm

nice, nitpick: add the msvc to link also. people will not see output since it is not supported, but it is nice to see it compiles with latest msvc on godbolt. – Cleanthes

flags I suggest are /std:c++latest /O2 – Cleanthes

@NoSenseEtAl: That actually makes more sense on the page of the question about determing type names rather than here. So I actually just decided to remove the whole thing. Plus, on that page, I've suggested a slightly more robust (though longer) implementation. – Hailstorm

Answer 4

It is possible to implement a type trait, sort, which, provided a certain type T, defines a tuple containing all the types of the original tuple sorted according to a strict-weak ordering criterion. If the type T is not a specialization of the std::tuple class, the program is ill-formed.

Implementation

Insertion sort has been chosen as sorting algorithm. The reasons can be summarized as the best trade-off between simplicity and performance.

It works by repeatedly extracting an element from the input list and inserting it into the correct position within the sorted list. In particular, the algorithm can be divided into two components: the main loop, which takes an element from the unsorted range and passes it to the insert operation; the insert function, which performs a linear probing on the sorted range until the correct position, where the new element is placed.

The average cost has a quadratic computational cost (O(N²)). This makes it not a good generic sorting algorithm for large lists. However, it performs efficiently on small or partly sorted lists, even better than quicksort.

Example:

namespace detail {
  template <typename, typename, typename, template <typename...> typename>
  struct insert
  {};

  template <typename T, typename ...Ts, template <typename...> typename Comp>
  struct insert<T, std::tuple<Ts...>, std::tuple<>, Comp>
  { using type = std::tuple<Ts..., T>; };

  template <typename T, typename ...Ts, typename U, typename ...Us, template <typename...> typename Comp>
  struct insert<T, std::tuple<Ts...>, std::tuple<U, Us...>, Comp>
  { using type = std::conditional_t<!Comp<T, U>::value, typename insert<T, std::tuple<Ts..., U>, std::tuple<Us...>, Comp>::type, std::tuple<Ts..., T, U, Us...>>; };

  template <typename, typename, template <typename...> typename>
  struct sort
  {};

  template <typename ...Ts, typename U, typename ...Us, template <typename...> typename Comp>
  struct sort<std::tuple<Ts...>, std::tuple<U, Us...>, Comp>
   : sort<typename insert<U, std::tuple<>, std::tuple<Ts...>, Comp>::type, std::tuple<Us...>, Comp> {};

  template <typename ...Ts, template <typename...> typename Comp>
  struct sort<std::tuple<Ts...>, std::tuple<>, Comp>
  { using type = std::tuple<Ts...>; };
}

template <typename T, template <typename...> typename Comp = less>
struct sort
 : detail::sort<std::tuple<>, T, Comp> {};

template <typename T, template <typename...> typename Comp = less>
using sort_t = typename sort<T, Comp>::type;

Design choices

1. Insert operation

In a generic insertion sort, the insert operation is performed by probing the sorted list in reverse order, while, for each element, it is compared to the new one. If the new element is greater than or equal to the current one, it is inserted; otherwise, the operation is repeated. It is important to note that, if the sorted list is empty or the entire list has already been probed without finding a proper position, the new element is inserted at the beginning of the sequence.

The implementation is similar to the description, but has an important difference: the linear probing is performed forwards. It derives from the fact that a parameter pack can not be expanded backwards.

The sort class extracts the first type of the input list and passes it to the insert class. This maintains the type T to be inserted and two tuples, the left list, which contains all types less than or equal to T, and the right list, which contains the remaining types. If the type T is greater than the first type U of the right list, it is inserted in the current position; otherwise, the type U is moved to the left list and the operation is repeated. It is important to note that, if the right is empty, the type T is directly inserted.

2. Best / Worst cases

If the list is already sorted, it is in the best case, which reduces the computational cost to linear (O(N)). This happens because, at each iteration, as it is verified that the new element is greater than or equal to the rightmost element in the sorted list, the insert operation is not even performed. The worst case, which has also a quadratic computational cost, may happen if the input list is sorted in the reverse order. Specifically, the sorting algorithm performs a linear probing on i elements, in the insert operation, for n times. Provided that i represents the length of the sorted list, which increases by one at each insert operation, the total number of passes is n(n + 1)/2.

They would be the best and worst cases if the linear probing was performed backwards. However, the metaprogramming algorithm, due to the limitation of the parameter pack expansion, can perform the scanning only forwards. This means that the common conditions that lead to the best case and worst case are swapped: if the input list is sorted in reverse order, the computational cost is linear; otherwise, the computational cost remains quadratic. When the input list is already sorted, the maximum number of passes is executed.

3. Ordering criterion

The greatest limitation with types is that they can not be compared. Thus, it is necessary to identify a different way to define the strict-weak ordering criterion, which can be potentially performed on any couple of types. The simplest solution concerns with the comparison between the sizes of types, which can be computed at compile-time through the sizeof operator and, since the returning type is always an unsigned integer, allows to have a trivial less-than comparison.

The solution determines also a performance improvement: by ordering types in an increasing or decreasing order, the structure can be packed in such a way that the padding be minimized.

It is important to note that the order is actually considered either ascending or descending, since there is no guarantee that the implementation of the std::tuple class store types in the same order as template arguments are defined. Indeed, the C++ Standard does not mandate any particular order for storing types, but just requires that they can be accessed with the same index as that of the corresponding template argument. Provided that implementations that may store types in a completely random order are not considered in this analysis, it is possible to conclude that the requirements allow libraries to pack types in two opposite orders. This divides the three greatest libraries into two groups: libc++, which store types in the same order as template arguments are declared; libstdc++, MSVC, which store types in the reversed order.

4. Comparison object

A more generic approach would be the use of a custom compare object. In this way, it would be possible to specify the type as a template argument, which may or may not be defaulted, with the possibility of defining a more appropriated strict-weak ordering criterion.

To achieve this goal, it is possible to exploit the existing practice of standard type traits in order that the metaprogramming version of the compare object can be defined in a well-known way. However, in absence of a standard design, an alternative one can be used, maybe inspired by robust and popular libraries, such as Boost.

In this case, the tmpbook's design is adopted. With a little adjustment, the generic comparison object can be defined in the following way.

A template class Comp, which can be specialized for two types T, U, is a metaprogrammaing comparison object if its static constant attribute value is contextually convertible to bool, and yields true if the first argument appears before the second argument in the strict-weak ordering criterion and false otherwise.

For simplicity, the default comparison object less, which performs a less-than comparison between the size of the first type and that of the second type, is provided.

Example:

template <typename T, typename U>
struct less
 : std::bool_constant<sizeof(T) < sizeof(U)> {};

---

Unique sorting is a sorting that, for every permutation of a certain list of elements, rearrange it in an unique manner. This means that, given an ordering criterion Comp, for every couple of elements x, y from a set S, with x ≠ y, either the Comp(x, y) or Comp(y, x) expression is always true.

In your case, solution would be to obtain a distinct value for every type. For example, it would be useful to get the original name of the type as a string and then performs a lexicographical comparison.

The problem is that C++ does not offer a generic type reflection. As a result, many pathetic attempts have been made to emulate the same effect. The best one is the use of a GCC identifier, PRETTY_FUNCTION, which holds the name of the specified function printed in a language specific fashion.

Oxime