C++ index of type during variadic template expansion

Question

I have a simple yet daunting problem I can't solve by myself. I have something like

template<class T, class... Args>
T* create(SomeCastableType* args, size_t numArgs)
{
  return new T(static_cast<Args>(args[INDEX_OF_EXPANSION])...);
}

Suppose SomeCastableType is castable to any type. Obviously what I can't get is that INDEX_OF_EXPANSION.

Thank you very much for your help.

Inscribe

Answer 1

Indices trick, yay~

template<class T, class... Args, std::size_t... Is>
T* create(U* p, indices<Is...>){
  return new T(static_cast<Args>(p[Is])...);
}

template<class T, class... Args>
T* create(U* p, std::size_t num_args){
  assert(num_args == sizeof...(Args));
  return create<T, Args...>(p, build_indices<sizeof...(Args)>{});
}

Of course, I strongly advise using a smart pointer and a std::vector instead of raw pointers.

Misogamy

I always prefer both of them, it was just to make things simpler. – Inscribe

I never liked mucking up the function itself though, I think (philosophy-wise) these constructs should be a service, not a detail. – Chigger

@GMan: I have to admit, I don't quite get what you mean with "service". Care to elaborate? – Misogamy

@Xeo: Something you use rather than something you work with, if that makes sense. For example, I can just use std::vector<MyClass> without needing to change MyClass specifically for vector (assuming requirements are met); that is, I don't have to derive from any special classes or add special constructors. My deleted answer was close to that (it fails in general though). – Chigger

@GMan: I don't see how you have to adjust anything to use the indices trick. All you need is an extra overload, but with your method, you also needed that extra indirection through index_. – Misogamy

I confirm this works on GCC but NOT on VS2012 CTP (very unfortunately). Thank you though, it's clear now. – Inscribe

@user: Yeah, CTP variadics are very buggy. The indices trick was one thing I tried when I first laid my hands on it, and in total I filed 11 variadic bugs that night (of which 10 are fixed in the internal Microsoft builds). – Misogamy

That extra overload is pretty nasty to read though. That extra indirection is just a line within the function, not an overhaul of the function itself. If it can't be helped then it doesn't matter of course (I thought it could), but I find the separation of the "trick" from the function preferable. – Chigger

@GMan: Okay, I can partially agree with that, but the indices trick is just plainly more efficient to compile. It only recurses up to sizeof...(Args) once, while your index_ traverses from the beginning every time - in current C++, pack expansion is simply messy. – Misogamy

Can you include a version of that using the C++14-standardized std::index_sequence<...>? Or, perhaps, only use that, and link to here for the C++11 implementation? – Timofei

Answer 2

Suppose SomeCastableType is castable to any type. Obviously what I can't get is that INDEX_OF_EXPANSION.

Since C++14, you can do the indices trick @Xeo mentioned with the support from the standard library, by using the std::make_index_sequence helper, as follows:

template<class T, class... Args, std::size_t... Is>
T* create(SomeCastableType* p, std::index_sequence<Is...>)
{
    return new T(static_cast<Args>(p[Is])...);
}

template<class T, class... Args>
T* create(SomeCastableType* p, std::size_t num_args)
{
    return create<T, Args...>(p, std::make_index_sequence<sizeof...(Args)>());
}

Sentimental

You can also use std::index_sequence_for<Args...> as a shortcut to std::make_index_sequence<sizeof...(Args)>. – Pickens

Answer 3

With c++17's constexpr if, we can get a much more readable / intelligible implementation of an index-lookup function (I never managed to get my head around the other answers here):

template<typename Target, typename ListHead, typename... ListTails>
constexpr size_t getTypeIndexInTemplateList()
{
    if constexpr (std::is_same<Target, ListHead>::value)
        return 0;
    else
        return 1 + getTypeIndexInTemplateList<Target, ListTails...>();
}

This can be used as follows:

size_t index = getTypeIndexInTemplateList<X,  Foo,Bar,X,Baz>(); // this will return 2

Or if you have a variadically templated type and want to get an index in it:

template<typename... Types>
class Container
{
public:
    size_t getIndexOfType<typename T>() {  return getTypeIndexInTemplateList<T, Types...>(); }
};

...

Container<Foo, Bar, X, Baz> container;
size_t container.getIndexOfType<X>(); // will return 2

The way it works is by recursively eliminating types from the list. So the call order for the first example is basically:

getTypeIndexInTemplateList<X,  Foo,  Bar,X,Baz>() // ListHead = Foo, ListTails = Bar,X,Baz
getTypeIndexInTemplateList<X,  Bar,  X,Baz>()     // ListHead = Bar, ListTails = X, Baz
getTypeIndexInTemplateList<X,  X,    Baz>()       // ListHead = X, so now we return. Recursive addition takes care of calculating the correct index

The function is constexpr, so this will all get executed at compile time, it will just be a constant at runtime.

If you ask for a type that is not present in the list, it will generate a compile error, as it will try to call the function with too few template arguments. And of course, this will just return the index of the first instance of the type in the list, if the type is present more than once.

Revive

I think, you are not answering the OPs question, but your answer is actually what I had been looking for ;-) – Rogovy

Answer 4

You need a helper:

#include <tuple>

template <typename T, bool, typename Tuple, unsigned int ...I>
struct helper
{
    static T * go(S * args)
    {
        return helper<T, sizeof...(I) + 1 == std::tuple_size<Tuple>::value,
                      Tuple, I..., sizeof...(I)>::go(args);
    }
};

template <typename T, typename ...Args, unsigned int ...I>
struct helper<T, true, std::tuple<Args...>, I...>
{
    static T * go(S * args)
    {
        return new T(static_cast<Args>(args[I])...);
    }
};

template <typename T, typename ...Args>
T * create(S * args)
{
    return helper<T, sizeof...(Args) == 0, std::tuple<Args...>>::go(args);
}

Edit: Tested, seems to work.

Flavine

Sorry, but this code won't work on both GCC 4.7.1 and VS2012 Nov2012 CTP. Reason is that a templete parameter pack must appear at the end of the list which likely means no multiple packs supported? – Inscribe

@user1191954: Yeah, fixed :-) – Flavine

@Xeo: I can never remember that one. Feel free to post (or edit). – Flavine

Done, and we have a Lounge Wiki site for that for a reason. :) – Misogamy

@Xeo: Hehe, indeed! I'll write this down somewhere safe. I was meant to be offline an hour ago, but who can resist variadic templates? – Flavine

@Xeo: Nevertheless, I'm semi-pleased that even half-asleep and without reference I came up with something that looks very similar to the Indices library, including the name Tuple :-) – Flavine

Thanks this works fine in GCC, but VS2012 can't compile it (it's just its plain fault). I think the reason is because their implementation of tuple still uses their emulation of v.t. through macros. Thank you anyway. – Inscribe

@user1191954: That's very possible. You really do need proper variadic templates for this. The tuple itself is irrelevant, we just need some kind of wrapper type to hold the argument pack. (Xeo's index trick uses a separate wrapper to wrap the integer pack as well, which is a very good idea.) And seriously you should accept Xeo's answer. – Flavine

@KerrekSB: To answer your question on my deleted answer: nope. :( – Chigger

@Kerrek: Nov 2012 CTP of VC++11 adds support to proper var templates. The stl is though not yet updated to the real v.t.. – Inscribe

@GManNickG: Hehe, cheers -- though I would have given you +1 for the sheer effort alone! – Flavine

Answer 5

Here's a slight variation with fold expressions (no recursion needed):

        template <typename Target, size_t Idx, typename... List>
        constexpr size_t type_index() {
            size_t idx   = 0;
            size_t count = Idx;
            bool   found = false;
    //This is effectively an unrolled for loop
    //we're checking each T in the parameter pack one by one
    //as we go we update whether we've found the right index
    //we assume multiple matching types may be in a parameter list 
    //so we need Idx to distinguish which one we're after
    //if we enter a type that's not in our parameter pack we'll
    //return sizeof...(List) like if we're using std::find()
            ((
                 found = found || (std::is_same<Target, List>::value && count == 0),
                 idx   = idx +
                           (!std::is_same<Target, List>::value && !found) ||
                       (std::is_same<Target, List>::value && count > 0),
                 count = count - (std::is_same<Target, List>::value && count > 0)),
                ...);
            return idx;
        }

//example:
type_index<int, 0, double, int, double, int>() == 1
type_index<int, 1, double, int, double, int>() == 3

Snapback