Suppose I have a type sequence through which I want to search:
template <typename...> struct TypeSequence { using type = TypeSequence; };
I want to create a metafunction Search that returns true if a given type exists in my type sequence, or false otherwise, and I want it to have better than O(N^2) space-complexity!
Currently I basically have to iterate through each element and create a true_type if the first element matches, or continue with 1 of the types truncated until I reach the end.
In C++ that looks something like this:
template <typename Enable, typename Type, typename... T>
struct SearchImpl;
// empty type sequence
template <typename Type>
struct SearchImpl<void, Type> : std::false_type
{
};
// first element matches
template <typename Type, typename T1, typename... T>
struct SearchImpl<
typename std::enable_if<std::is_same<Type, T1>::value>::type,
Type, T1, T...>
:
std::true_type
{
};
// first element doesn't match
template <typename Type, typename T1, typename... T>
struct SearchImpl<
typename std::enable_if<!std::is_same<Type, T1>::value>::type,
Type, T1, T...>
:
SearchImpl<void, Type, T...>
{
};
// check if a type exists within a type list
template <typename TypeList, typename T>
struct Search;
template <template <typename...> class TypeList, typename T, typename... Types>
struct Search<TypeList<Types...>, T>
:
SearchImpl<void, T, Types...>
{
};
For a type sequence of length N with the matching type located at N/2, this search operation creates N^2N/2 unique types with a length of order N each, equating to something in the order of O(N^2) space complexity at compile time.
Is there a way of performing such a search with lower complexity?
The following would be very cheap, but is illegal because it requires a variadic pack not at the end of the argument list:
template <typename T, typename... Types>
struct Has : std::false_type
{
};
template <typename T, typename... T1, typename... T2>
struct Has<T, T1..., T, T2...> : std::true_type // illegal!
{
};
How can I better frame a solution to this problem to reduce the space-complexity (ie. number of types instantiated). I know I can reduce it by simply searching through larger blocks, but this doesn't reduce the complexity itself (ie. it doesn't scale well).
The answer can be in pseudo-code, as long as it writable in c++ template code.