Как заказывать типы во время компиляции?

Рассмотрим следующую программу:

#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;
}

ordered помощник должен переупорядочить типы в кортеже, так что два кортежа с типами sames, но упорядоченные по-разному приводят к одному типу кортежа: который может быть первым, вторым или даже другим: он просто должен имеют одинаковый размер и одни и те же элементы, но в уникальном порядке (независимо от этого порядка).

Можно ли это сделать во время компиляции с использованием методов метапрограммирования шаблонов?

Ответы

Ответ 1

Трудная часть подходит для заказа типов. Сортировка списка типов по предикату является хором, но выполнима. Здесь я остановлюсь только на предикате сравнения.

Один из способов - просто создать шаблон класса, который определяет уникальный идентификатор для каждого типа. Это работает и позволяет легкому компаратору писать:

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

Но придумывание этих уникальных идентификаторов - это препятствие, которое не всегда возможно. Вы регистрируете их все в одном файле? Это не очень хорошо масштабируется.

Было бы здорово, если бы мы могли просто... получить имена всех типов в виде строк времени компиляции. Отражение даст нам это, и тогда эта проблема тривиальна. До тех пор мы могли сделать что-то немного более грязное: используйте __PRETTY_FUNCTION__. И gcc, и clang в порядке с использованием этого макроса в контексте constexpr, хотя у них есть разные форматы для этой строки. Если у нас есть подпись, например:

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

Затем gcc сообщает cmp<char, int> как "constexpr bool cmp() [with T = char; U = int]" то время как clang сообщает об этом как "bool cmp() [T = char, U = int]". Это другое... но достаточно близко, чтобы мы могли использовать тот же алгоритм. Что в основном: выяснить, где T и U находятся там, и просто выполнить нормальное линейное лексикографическое сравнение:

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;
}

с некоторыми тестами:

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>>());

Это не самая красивая реализация, и я не уверен, что она была осмысленно санкционирована стандартом, но она позволяет вам писать свой вид без необходимости вручную и тщательно регистрировать все ваши типы. И он компилируется на clang и gcc. Так что, может быть, это достаточно хорошо.