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.

Improve this question
14
  • 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. Commented Nov 4, 2014 at 2:53
  • Its not clear to me what O(N^2) types this induces. Commented Nov 4, 2014 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). Commented Nov 4, 2014 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? Commented Nov 4, 2014 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. Commented Nov 4, 2014 at 4:38

2 Answers 2

Reset to default
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 
{
};
Improve this answer
3
  • This fails if the same type occurs multiple times in the Haystack type pack (it gives duplicate base types) Commented Nov 4, 2014 at 16:55
  • @Useless why does this fail for duplicate types? Commented Nov 4, 2014 at 21:42
  • @Useless Ah, that's why... Commented Nov 4, 2014 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.

Improve this answer
5
  • 1
    I think you may actually be hitting o(n^2) due to the implementation of std::tuple. Commented Nov 4, 2014 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. Commented Nov 4, 2014 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. Commented Nov 4, 2014 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. Commented Nov 5, 2014 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. Commented Nov 5, 2014 at 10:55

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.