使用快速排序排序可变模板参数的编译错误求助

引言 #

我的需求是：无论模板参数的顺序如何，包含相同模板的对象的Family::identifier()返回值需保持一致。本尝试可作为「是否存在一致排序类型模板参数的方法？」的一种实现思路。

我参考了某实现，但核心差异在于我使用快速排序，而原方案采用归并排序，二者并不相似。为了学习，我决定自行实现而非直接复制代码。

我的潜在解决方案 #

我的代码接近可用，但存在一些问题

Family.h #

#pragma once

#include <type_traits>

struct TypeIndex 
{
    inline static size_t counter = 0;
    
    template<typename T>
    static size_t get() 
    { 
        static size_t value = counter++;
        return value;
    }
};

template <typename... Ts>
class Family 
{
    template<typename T>
    struct TypeID
    {
        static char storage;
        static constexpr void* const value = &storage;
    };

    template <typename T, typename U>
    static constexpr bool isSmaller()
    {
        return TypeID<T>::value < TypeID<U>::value;
    }

    template <typename... Ts>
    struct List { };

    template <typename... Ts>
    struct Concat;

    template <typename... Ts, typename... Us>
    struct Concat<List<Ts...>, List<Us...>> {
        using type = List<Ts..., Us...>;
    };

    template <typename... Ts>
    struct Append;

    template <typename... Ts, typename T>
    struct Append<List<Ts...>, T> {
        using type = List<Ts..., T>;
    };

    template <typename Pivot, typename List, template <typename, typename> class Condition>
    struct Partition;

    template <typename Pivot, template <typename, typename> class Condition>
    struct Partition<Pivot, List<>, Condition> {
        using type = List<>;
    };

    template <typename Pivot, typename Head, typename... Tail, template <typename, typename> class Condition>
    struct Partition<Pivot, List<Head, Tail...>, Condition> {
        using type = typename std::conditional_t<
            Condition<Pivot, Head>::value,
            typename Append<typename Partition<Pivot, List<Tail...>, Condition>::type, Head>::type,
            typename Partition<Pivot, List<Tail...>, Condition>::type
        >;
    };

    template <typename Pivot, typename T>
    struct Less {
        static constexpr bool value = isSmaller<T, Pivot>();
    };

    template <typename Pivot, typename T>
    struct Greater {
        static constexpr bool value = !isSmaller<T, Pivot>();
    };

    template <typename List>
    struct QuickSort;

    template <typename Pivot, typename... Tail>
    struct QuickSort<List<Pivot, Tail...>> {

        using LowerPartition = typename Partition<Pivot, List<Tail...>, Less>::type;
        using UpperPartition = typename Partition<Pivot, List<Tail...>, Greater>::type;

        using SortedLowerPartition = typename QuickSort<LowerPartition>::type;
        using SortedUpperPartition = typename QuickSort<UpperPartition>::type;

        using type = typename Concat<
            typename Append<SortedLowerPartition, Pivot>::type,
            SortedUpperPartition
        >::type;
    };

    template <>
    struct QuickSort<List<>> {
        using type = List;
    };

public:
    static size_t identifier()
    {
        return TypeIndex::get<typename QuickSort<List<Ts...>>::type>();
    }
};

main.cpp示例 #

...

class c1 {};
class c2 {};
class c3 {};
class c4 {};

int main()
{
    std::cout << Family<c1, c2, c3, c4>::identifier() << '\n';
    std::cout << Family<c1, c3, c2, c4>::identifier() << '\n';
    std::cout << Family<c2, c1, c3>::identifier() << '\n';
    std::cout << Family<c4, c3, c1>::identifier() << '\n';
    std::cout << Family<c3        >::identifier() << '\n';
    std::cout << Family<c3, c2, c1>::identifier() << '\n';
    
    ...
}

编译错误 #

编译代码时，编译器针对QuickSort::type报错：

using type = typename Concat<
            typename Append<SortedLowerPartition, Pivot>::type,
            SortedUpperPartition
        >::type;

错误信息：

• Error C2027 使用未定义的类型“Family<c3,c2,c1>::Append<int,Pivot>”
• Error C2027 使用未定义的类型“Family<c3,c2,c1>::Append<int,Pivot>”
• Error C2027 使用未定义的类型“Family<c3,c2,c1>::Append<int,Pivot>”
• Error C2146 语法错误: 标识符“type”前缺少“>”
• Error C2146 语法错误: 标识符“type”前缺少“;”
• Error C2039 “type”: 不是“全局命名空间”的成员
• Error C3203 “List”: 未特化的类模板不能用作模板参数“Ts”的模板实参，需要实际类型
• Error C2602 “Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List>::type”不是“Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List>”基类的成员
• Error C2602 “Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List<c3,c2,c1>>::type”不是“Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List<c3,c2,c1>>”基类的成员
• Error C2602 “Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List<c1,T>>::type”不是“Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List<c1,T>>”基类的成员

我的排查推测 #

我测试过Partition结构体，功能正常，其他部分似乎也无问题。一个可能的线索是：若将SortedLowerPartition和SortedUpperPartition替换为LowerPartition和UpperPartition（即移除快速排序的递归逻辑），代码可正常编译。这说明SortedLowerPartition可能并非预期的List<>类型，但Concat<>::type应该返回List<>类型，SortedLowerPartition也理应为List类型，这与实际情况矛盾。恳请各位帮忙排查问题。

内容的提问来源于stack exchange，提问作者bibanac