2

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/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.

  • For anyone else wanting to downvote this on the basis that it is off-topic, here are the guidelines. Please take the time to peruse them. – quant Nov 4 '14 at 2:53
  • Its not clear to me what O(N^2) types this induces. – Winston Ewert Nov 4 '14 at 3:09
  • @quant I suspect the downvote may be because this is on the Stack Overflow side of the gray area: it involves both algorithms and implementation details. My interpretation is it is on the Programmers side, maybe an edit to focus on the algorithmic complexity rather than the "fix my code" aspect would convince the downvoter (who did not leave a comment). – user22815 Nov 4 '14 at 3:27
  • @Snowman, yes that was my thinking as well. I did edit the page to focus on the complexity-side of it (around the same time you posted); do you think this needs to be clearer? – quant Nov 4 '14 at 4:36
  • @WinstonEwert for each element searched, it needs to generate N types, and it needs to search through N/2 types to find an element at the half-way point, creating N*N/2 types. – quant Nov 4 '14 at 4:38
2

The basic trick here is from a blog post describing an implementation of std::tuple. We are limited in our options for variadic template arguments, but we can use them to define the base classes for a class.

template<typename T, typename... Haystack>
struct SearchImpl : std::is_same<T, Haystack>...
{
};

This class inherits from std::true_type for each matching type and std::false_type for each non-matching type. Thus all we need to do is determine whether it inherits from std::true_type.

template<typename T, typename... Haystack>
struct Search : std::is_base_of<std::true_type, SearchImpl<T, Haystack...>>::type 
{
};
  • This fails if the same type occurs multiple times in the Haystack type pack (it gives duplicate base types) – Useless Nov 4 '14 at 16:55
  • @Useless why does this fail for duplicate types? – quant Nov 4 '14 at 21:42
  • @Useless Ah, that's why... – quant Nov 4 '14 at 21:57
1

Starting from Winston Ewart's answer, I figured out something that still uses only O(n) type instantiations, but also works when you have duplicate types in your parameter pack

// we want to get a different size if the types match
template <typename A, typename B> struct Same { char padding[3]; };
template <typename A> struct Same<A,A> { char padding[7]; };
template <typename T> struct Diff: public Same<int,bool> {};

#include <cstddef>
constexpr std::size_t SameSize = sizeof(Same<bool,bool>);       // size if really same
constexpr std::size_t DiffSize = SameSize - sizeof(Diff<bool>); // difference in size

// we instantiate only two flat tuples, hence O(n)
#include <tuple>
template <typename Needle, typename... Haystack>
struct SearchImpl {
    typedef std::tuple<Same<Needle,Haystack>...> SameTypes; // some may be matches
    typedef std::tuple<Diff<Haystack>...> DiffTypes;        // none will be matches

    static constexpr size_t matches = (sizeof(SameTypes)-sizeof(DiffTypes)) / DiffSize;
    static constexpr bool result = (matches > 0);
};

template <typename Needle, typename... Haystack>
struct Search: public std::integral_constant<bool, SearchImpl<Needle,Haystack...>::result>
{};

Note that the tuple can't compress the members (they're never empty), so the size calc is correct and you get the number of matches as a bonus.

  • 1
    I think you may actually be hitting o(n^2) due to the implementation of std::tuple. – Winston Ewert Nov 4 '14 at 22:03
  • 1
    You're right! I forgot std::tuple still recurses even though we're dealing with type packs instead of the old recursive typelists. – Useless Nov 4 '14 at 23:06
  • 1
    Actually, I found at least one implementation (libc++) that isn't recursive: so, I'll claim it's a QoI issue, but a complete solution could build in the non-recursive machinery direcly instead of relying on std::tuple. – Useless Nov 4 '14 at 23:13
  • The version I've seen still uses recursion to build up a list of indexes even if the class itself use inheritance to hold each value. – Winston Ewert Nov 5 '14 at 1:26
  • 1
    The libc++ version (here, after #ifndef _LIBCPP_HAS_NO_VARIADICS) uses a non-type pack of integral indices expanded in parallel with the types to make all bases unique without recursion. To be fair, the indices themselves (here) do require recursion, but should be memoized and shared between all uses. – Useless Nov 5 '14 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.