如何在编译时订购类型？ [英] How to order types at compile-time?

问题描述

考虑以下程序：

  #include< tuple> 
 #include< vector> 
 #include< iostream> 
 #include< type_traits> 
 
模板< class T> 
 struct订购{}; 
 
模板< class ... T> 
 structordered< std :: tuple< T ...>> 
 {
使用类型= / *一个重新排序的元组* /; 
}; 
 
模板< class T> 
使用ordered_t =类型名ordered< T> :: type; 
 
 int main（int argc，char * argv []）
 {
使用type1 = std :: tuple< char，std :: vector< int> ;, double&; 
使用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 
返回0; 
} 
  

排序的助手必须对一个元组中的类型进行重新排序，以便两个具有相同类型的元组，但顺序不同的结果会导致相同的元组类型：可以是第一个，第二个甚至另一个：它只需要具有相同的

是否有可能使用模板元编程技术在编译时执行此操作？

p>

解决方案

最困难的部分是提出了一种订购类型的方法。按谓词对类型列表进行排序是一件很麻烦的事，但是是可行的。我将只关注比较谓词。

一种方法是只创建一个为每种类型定义唯一ID的类模板。这行之有效，并使比较器易于编写：

  template< typename T，typename U> 
 constexpr bool cmp（）{return unique_id_v< T> < unique_id_v< U> ;; } 
  

但是想出这些唯一的ID是一个障碍，不一定可行。您是否将它们全部注册在一个文件中？扩展性不够好。

如果可以...将所有类型的名称作为编译时间字符串，那将是很棒的。反思将使我们明白这一点，然后这个问题就变得微不足道了。在此之前，我们可以做些更脏的事情：使用 __ PRETTY_FUNCTION __ 。 gcc和clang都可以在 constexpr 上下文中使用该宏，尽管它们的字符串格式不同。如果我们有这样的签名：

  template< typename T，typename U> 
 constexpr bool cmp（）; 
  

然后gcc报告 cmp< char，int> as 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; 
而（* p）{
 ++ len; 
 ++ p; 
} 
 return len; 
} 
 
模板< 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__ 
而（* b！=’，’）++ b; 
 #else 
而（* b！=’;’）++ b; 
 #endif 
 size_t a_len = b-a; 
 b + = cstrlen（; U =）; 
 const char * end = b +1; 
 while（* end！=’]’）++ end; 
 size_t b_len =结束-b; 
 
 for（size_t i = 0; i< std :: min（a_len，b_len）; ++ i）{
 if（a [i]！= b [i]）返回a [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 。所以也许就足够了。

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?

解决方案

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.

这篇关于如何在编译时订购类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！