Introduction
What I want to do is: Regardless of the order of template arguments, I want the objects which contain the same templates, to also have the same return value of Family::identifier(). What I tried to do could be considered an answer to Is there a way to consistently sort type template parameters?.
I've taken some inspiration from the answer with the link to https://godbolt.org/z/KPc9Kd, but the main difference is that I do is Quick Sorting, while what the answer suggests using Merge Sort, so not that similar. I wanted to not just copy paste the code from there, so I decided to make my own implementation so that I learn something.
My possible solution:
My code almost, works, but there are some hiccups
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>();
}
};
An example of 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';
...
}
The errors
When I try to compile this code, it complains about the QuickSort::type
using type = typename Concat<
typename Append<SortedLowerPartition, Pivot>::type,
SortedUpperPartition
>::type;
Error C2027 use of undefined type 'Family<c3,c2,c1>::Append<int,Pivot>'
Error C2027 use of undefined type 'Family<c3,c2,c1>::Append<int,Pivot>'
Error C2027 use of undefined type 'Family<c3,c2,c1>::Append<int,Pivot>'
Error C2146 syntax error: missing '>' before identifier 'type'
Error C2146 syntax error: missing ';' before identifier 'type'
Error C2039 'type': is not a member of '`global namespace''
Error C3203 'List': unspecialized class template can't be used as a template argument for template parameter 'Ts', expected a real type
Error C2602 'Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List>::type' is not a member of a base class of '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' is not a member of a base class of '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' is not a member of a base class of 'Family<c3,c2,c1>::QuickSort<Family<c3,c2,c1>::List<c1,T>>'
What I suspect is happening
I've tested the Partition structure and it works fine -everything else seems to be fine too. One possible indication for the underlying problem could be that when I replace the SortedLowerPartition, and the SortedUpperPartition with LowerPartition, and also UpperPartition. Everything compiles fine. ( Note that this would also mean that there is no more recursion in the Quick Sort ). This may mean that SortedLowerPartition and LowerPartition are not of type List<>, as I expected them to be. This would be weird because Concat<>::type should be a List<>, and therefore also the SortedLowerPartition<> should be List's. However, this seems not to be the case here.
Any help would be very much appreciated, I'm going insane here
