Ability to access the position of a type while unpacking a parameter pack

[sco...@gmail.com]

Hi,

Variadic template parameters are really nice, and it's really impressive how complex of expressions you can unpack (with more coming once C++17 allows folds). However, there is currently a glaring gap in the feature: you can't access the position number of a type when unpacking a parameter pack. This makes it unnecessarily hard to write code that mixes parameter packs and tuples, because the one works with variadic lists of types and the other requires use of std::get<size_t>.

The idea I'd like to float, then, is that the position of a given type within its pack should be accessible during unpacking:

template <typename...Ts>
std::vector<size_t> foo(Ts&& ...) { return {#Ts...}; }

int main() {
   std::vector a{0,1,2}, b=foo("hi", "ho", "hum");
   assert(a == b); // succeeds
}

The above function is clearly a toy example, and the exact syntax need not be '#Ts' but hopefully it conveys the idea. The feature would complement the existing sizeof...() operator, and I do not think it would be difficult to provide compiler support for it (though I am by no means a compiler expert).

The rest of this message consists of examples to show why such a syntax might be useful. The first three examples were extracted from real-life scenarios I encountered in my work, though they have been simplified drastically here to be more concise. The last example I made up, to show something that would be really unpleasant to express without the proposed syntax.

Apologies in advance if this idea has already been floated in the past---a search of this forum did not turn up any obvious matches, but that doesn't mean much.

Example 1:
====================

Suppose I have some code that assigns values to a std::tuple which are constructible and assignable---but not convertible---to the tuple's field types. This means I can't write this:

template <typename T>
struct StoredType { using type=T; };

/* various specializations of StoredType follow, but
 * std::is_constructible<StoredType<T>::type, T> always holds
 */
template <typename... FTs>
struct Foo {
   std::tuple<typename StoredType<FTs>::type...> _data;

   Foo(FTs const & ...args) : _data{args...} { } // error!
};

Instead, the constructor needs a hack like the following:

Foo(FTs const & ...args) { init_data<0,FTs...>(args...); }

template <size_t M, typename T, typename... Rest>
void init_data(T const &arg, Rest const & ...rest) {
   std::get<M>(_data) = arg;
   init_data<M+1, Rest...>(rest...);
}

template <size_t M, typename T>
void init_data(T const &arg) {
   std::get<M>(_data) = arg;
}

If there were a way to access type positions in a parameter pack, the constructor hack would be much simpler and cleaner:

Foo(FTs const & ...args) {
   auto x = {(std::get<#FTs>(_data)=args)...};
   (void) x;
}

(I know that N4387 will address this particular problem, but that's besides the point)

Example 2:
====================

Consider a fold function that accepts some number of inputs and applies an action to each of them (vaguely similar to what C++17 is likely to support). If the values to be folded are provided as arguments to a variadic template function, then it's really easy (assuming C++14 generic lambdas):

// workaround for fact that we can't make a std::initializer_list<void>
template <typename Action, typename T>
bool void_fold_one(Action &action, T &&t) {
   action(std::forward<T>(t));
   return true;
}

template <typename Action, typename T, typename... Ts>
void void_fold(Action &&action, T &&t, Ts&&... args)
{
   auto x = {void_fold_one(action, std::forward<T>(t))...};
   (void) x;
}

int main() {
   auto action = [](auto x) { std::cout << x << " "; };
   void_fold(action, 1, 3.14, "hi", std::endl);
}

Now try to do that with a std::tuple instead and you end up with something much less satisfying:

template <size_t I, size_t N>
struct void_fold_tuple_ {
   template <typename Action, typename Tuple>
   static void call(Action &action, Tuple &tup)
   {
      action.template operator()<I>(tup);
      using recursive = void_fold_tuple_<I+1, N>;
      recursive::call(action, tup);
   }
};

template <size_t N>
struct void_fold_tuple_<N, N> {
   template <typename Action, typename Tuple>
   static void call(Action&, Tuple&) { /* no-op */ }
};

struct print_action {
   template <typename Tuple, size_t I>
   void operator()(Tuple &tup) {
      using std::get; // ADL
      std::cout << std::get<I>(tup) << " ";
   }
};

template <typename Action, typename Tuple>
void void_fold_tuple(Action &&action, Tuple &&tup)
{
   using std::tuple_size; // ADL
   using tuple = typename std::remove_reference<Tuple>::type;
   using recursive = void_fold_tuple_<0, tuple_size<tuple>::value>;
   recursive::call(action, tup);
}

int main() {
   std::tuple<int, double, char const *> tup{1,3.14,"hi",std::endl};
   void_fold_tuple(print_action{}, tup);
};

If something like the #N syntax were available then it would simplify back to something that resembles strongly the first case:

template <typename Action, template <typename ...> class Tuple, typename ...FTs>
void void_fold_tuple(Action &&action, Tuple<FTs...> &&tup)
{
   auto x = {void_fold_one(action, std::get<#FTs>(tup)...)};
   (void) x;
}

int main() {
   std::tuple<int, double, char const *> tup{1, 3.14, "hi", std::endl};
   void_fold_tuple(print_action{}, tup);
};

Example 3
====================

Suppose we want to initialize the contents of a std::tuple using a std::vector (this actually arose in our code when we have templated child classes that specialize a virtual base class used elsewhere). Right now the only way to achieve it is something like the following:

template<int...>
struct Sequence { };

template<size_t N, size_t... S>
struct GenSequence {
   using type = typename GenSequence<N-1, N-1, S...>::type;
};

template<size_t... S>
struct GenSequence<0, S...>
{
   using type = Sequence<S...>;
};

template <typename... Ts>
struct Foo {
   using Tuple = std::tuple<Ts* ...>;
   using Vector = std::vector<void*>;
   using Seq = typename GenSequence<sizeof...(Ts)>::type;

   Foo(Vector const &v) {
      init_pointers(v, Seq());
   }

   template <size_t ... S>
   void init_pointers(Vector const &v, Seq) {
      _pointers = Tuple{dynamic_cast<Ts*>(v[S])...};
   }

   Tuple _pointers;
};

With the new syntax that would simplify to:

template <typename... Ts>
struct Foo {
   using Tuple = std::tuple<Ts* ...>;
   using Vector = std::vector<void*>;

   Foo(Vector const &v)
      : _pointers{dynamic_cast<Ts*>(v[#Ts])...}
   {
   }

   Tuple _pointers;
};


Example 4
====================

Suppose I wanted to define a function that reverses the fields of a tuple. With the proposed syntax it would not be difficult to write such a function:

template <size_t M, typename T, typename... Ts>
struct Select{
    using type = typename Select<M - 1, Ts...>::type;
};

template <typename T, typename... Ts>
struct Select<0, T, Ts...>{
    using type = T;
};

template <template <typename...> class Tuple, typename... Ts>
auto reverse(Tuple<Ts...> const &tup) {
   static constexpr size_t const N = sizeof...(Ts) - 1;
   using RTuple = Tuple<typename Select<N - #Ts, Ts...>::type...>;
   return RTuple<{std::get<N-#Ts>(tup)...};
}

I'll leave the vanilla C++14 version of the above function as an exercise for the reader...

Thoughts?
Ryan Johnson

[Edward Catmur]

I think n3728 or something similar would provide what you're after, with reasonable syntax. If typelists become enough of a first-class citizen that it becomes possible to introduce a typelist into scope and then expand it with natural syntax, then it becomes plausible that you could write:

template <typename...Ts>
std::vector<size_t> foo(Ts&& ...) { return {std::index_sequence_for<Ts...>::value...}; }

Here, std::integer_sequence has been augmented with a typelist holding its compile-time integer sequence:

template<class T, T... Ints>
struct integer_sequence {
    using value_type = T;
    using value = <Ints...>;    // new typelist member after n3728; syntax TBD
    static constexpr std::size_t size() { return sizeof...(Ints); }
};

Does anyone know what kind of reception Mike got at Chicago when presenting n3728? 

[sco...@gmail.com]

Hmm. That's a very interesting proposal I didn't know about (thanks for the heads-up!), but I'm not sure it actually solves the awkwardness I was pointing out here: even if you had proper typelists, you'd still need some (presumably recursive) variadic template helper(s) to convert a `template <typename... Ts>' into a `template <size_t... Is>' for cases where you need to index types. To implement this std::index_sequence_for that you mention, for example, my proposed syntax would lead to something like:

template <typename... Ts>
struct index_sequence_for {
   using value = <#Ts...>;
};

... which is rather simpler than the alternatives I could imagine.

Also, my proposed syntax would make such a class largely unnecessary because anyone wanting to turn a typelist into an integer sequence could just use the same technique directly.

Still, if the other proposal brought as a side effect the ability to turn type lists into integer sequences with less hoop-jumping than the current status quo, I'd not complain too loudly.

[David Krauss]

On 2015–07–21, at 2:08 AM, sco...@gmail.com wrote:

The idea I'd like to float, then, is that the position of a given type within its pack should be accessible during unpacking:

template <typename...Ts>
std::vector<size_t> foo(Ts&& ...) { return {#Ts...}; }


How about a special alias template, like this:

template< typename type, std::size_t index >

using indexed_type = type; // Compiler magic deduces index, too

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

An alias template can produce a deduced context as its result. Rather than introducing a new operator syntax for pack indexes, the library can encapsulate the “operator.” The standard only needs to say that index arguments are a deduced context when indexed_type is used in a pack pattern.

[Ryan Johnson]

Update: I have successfully implemented the feature in clang-3.8, by way of a new builtin `__indexof()' that takes an unexpanded parameter pack and expands to a sequence of size_t. Combined with C++17 fold expressions, a lot of messy code at work suddenly becomes enormously simpler.

For example, the following compiles and produces the expected result with the hacked clang:

template <typename T>
int hash(T const &t);
/* ^^^ to be specialized for lots of types */

template <template <typename...> class Tuple, typename... T>

int hash(Tuple<T...> const &tup)

{
   using std::get; // ADL

   return (... ^ hash(get<__indexof(T)>(tup)));
}

Thoughts?

Ryan

--

---
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-proposals/u9XLfRCKzGc/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Ryan Johnson]

On 22/07/2015 2:14 AM, David Krauss wrote:

How about a special alias template, like this:

template< typename type, std::size_t index >

using indexed_type = type; // Compiler magic deduces index, too

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

An alias template can produce a deduced context as its result. Rather than introducing a new operator syntax for pack indexes, the library can encapsulate the “operator.” The standard only needs to say that index arguments are a deduced context when indexed_type is used in a pack pattern.

Compiler magic can be a good thing... and the committee seems to favor it as well, with all those C++11 type traits being a prime example.

If I understand correctly, perhaps this might be another way of stating your idea?

template <typename T, size_t N=/*magic*/>
struct indexof {
    using type = T; /* for completeness */
    static constexpr size_t value = N;
};

I'm not sure I follow how foo in your example would be used, tho? That code would probably not compile, at least not if you invoked:

foo(1, 3.14, "hi")

Type deduction machinery generally fails if the types in the function's argument list are derived somehow from---rather than directly using---the types in the functions template parameter list.

The variant below compiles and runs with a normal C++11 compiler, though lacking compiler magic it prints "0 0 0" instead of "0 1 2":

template <typename T, size_t N=0>
struct indexof {
    using type = T; /* for completeness */
    static constexpr size_t value = N;
};

template <typename... T>
std::vector<size_t> foo(T && ...args) {
    return {std::indexof<T>::value...};
}

Versus a new keyword like __indexof, which operates in an unevaluated context like alignof() and sizeof(), a magic std::indexof template has the definite advantages of not polluting the global namespace. A slight advantage is that std::indexof could degrade gracefully to value=0 when passed a normal (non-pack) template parameter where __indexof would fail to compile---though I'm not sure that's important, given the intended use.

std::indexof has the disadvantage of requiring significantly more typing (though I'll admit it's impeccably C++-flavored boilerplate). A slight disadvantage is that std::indexof would not provide the analogue to __indexof(args) because it can only accept template packs [1].

Perhaps others could weigh in on which set of trade-offs is more desirable?

[1] I was shocked to discover that my prototype implementation of __indexof in clang actually handles __indexof(T) and __indexof(args) equally well, though I'd not considered the latter use case when I implemented it. It will make a good addition to the unit tests.

Thoughts?
Ryan

[Ryan Johnson]

On 22/07/2015 2:14 AM, David Krauss wrote:

How about a special alias template, like this:

template< typename type, std::size_t index >

using indexed_type = type; // Compiler magic deduces index, too

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

An alias template can produce a deduced context as its result. Rather than introducing a new operator syntax for pack indexes, the library can encapsulate the “operator.” The standard only needs to say that index arguments are a deduced context when indexed_type is used in a pack pattern.

On Wednesday, July 22, 2015 at 7:52:48 AM UTC-6, Ryan Johnson wrote:

On 22/07/2015 2:14 AM, David Krauss wrote:

How about a special alias template, like this:

template< typename type, std::size_t index >

using indexed_type = type; // Compiler magic deduces index, too

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

An alias template can produce a deduced context as its result. Rather than introducing a new operator syntax for pack indexes, the library can encapsulate the “operator.” The standard only needs to say that index arguments are a deduced context when indexed_type is used in a pack pattern.

Compiler magic can be a good thing... and the committee seems to favor it as well, with all those C++11 type traits being a prime example.

If I understand correctly, perhaps this might be another way of stating your idea?

template <typename T, size_t N=/*magic*/>
struct indexof {
    using type = T; /* for completeness */
    static constexpr size_t value = N;
};

Hmm. After spending a bit of time trying to update my prototype to support a std::indexof<T> approach, a couple of problems emerged:

1. Most "compiler magic" templates are actually normal templates whose definition happens to wrap up built-in functions. For example, in clang, you could define a simplified version of std::is_trivially_destructible as:
   
   
   template <typename T>
   struct is_trivially_destructible {
      static constexpr bool value = __is_trivially_destructible(T);
   };
   
   
   Unfortunately, the obvious analogue for std::indexof<T> would be:
   
   
   template <typename T, size_t N=__indexof(T)>
   struct indexof {
   

1.    static constexpr size_t value = N;
   };
   

1. 
   Without special treatment, that use of __indexof(T) will almost certainly be evaluated at the wrong time and so fail to detect that T is part of a parameter pack; the result would be either a compilation error or a hard-wired N=0. I don't know yet how difficult it would be to arrange for that special treatment. The alternative would be to make the actual template name std::indexof special and have the compiler propagate that special-ness across using, typedef, etc. I don't think clang has any machinery in place for that, though, so it would probably not be a fun change to make.
   
   
2. More worrisome, the std::indexof<T> approach cannot support non-type template parameters: once you have this:
   
   
   template <typename T, size_t N=__indexof(T)> struct indexof;
   
   It is an error to define these:
   
   
   template <int... T, size_t N=__indexof(T)> struct indexof;
   template <template <typename...> class T, size_t N=__indexof(T)> struct indexof;
   
   
   Thus, you'd need three different names for the std::indexof<T> concept, one for each kind of parameter pack, which would be pretty annoying. The __indexof() built-in faces no such difficulty.
   
   

Thoughts?
Ryan

[Bengt Gustafsson]

Why not make indexof a magic variable template? Then you don't need the ::value at the point of use and you don't need three different versions. You still face the implementation issue of not being able to use the pattern of a normal template calling a magic function though.

return { std::indexof<Ts>... };

And this magically works whether Ts is a pack of types, values or templates.

[David Krauss]

On 2015–07–23, at 7:39 AM, Ryan Johnson <sco...@gmail.com> wrote:

1. 
   Unfortunately, the obvious analogue for std::indexof<T> would be:
   
   
   template <typename T, size_t N=__indexof(T)>
   struct indexof {
      static constexpr size_t value = N;
   };
   

That’s why I suggested an alias template. Alias template substitutions occur before argument substitutions or type deduction. So, the usage

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

gets transformed into something like

template <typename ... Ts, std::size_t ... Xs>

std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

What I’m trying to illustrate here is that the parameter type will be Ts && regardless of the Xs values, but Xs can still be deduced from the context where the alias template was used, because the alias template has been substituted away before deduction begins.

This is a completely different animal from type traits.

1. More worrisome, the std::indexof<T> approach cannot support non-type template parameters:

The alias template adds a different restriction: there needs to be a sequence of deduced types in the function signature or partial specialization template-id. The main pack can be non-type.

2. Thus, you'd need three different names for the std::indexof<T> concept, one for each kind of parameter pack, which would be pretty annoying. The __indexof() built-in faces no such difficulty.
   

Maybe Clang can implement __indexof() without difficulty, but an operator that equally accepts a template name, type, or expression as an argument doesn’t fit into the language grammar (and might not fit into other implementations) as easily.

Personally, I consider non-type template parameters as second-class citizens and keep them quarantined in the smallest possible utility classes. Unfortunately, not everyone feels this way, and the workarounds are inconvenient to impossible.

[Giovanni Piero Deretta]

On Thursday, July 23, 2015 at 7:53:00 AM UTC+1, David Krauss wrote:

[...]

2. Thus, you'd need three different names for the std::indexof<T> concept, one for each kind of parameter pack, which would be pretty annoying. The __indexof() built-in faces no such difficulty.
   

Maybe Clang can implement __indexof() without difficulty, but an operator that equally accepts a template name, type, or expression as an argument doesn’t fit into the language grammar (and might not fit into other implementations) as easily.

don't know about template name, but sizeof has accepted either type or an expression without issues since forever. Also new operators have been added recently (decltype, alignas, noexcept), without the need to wrap them in a metafunction veneer. Ryan should just propose the __indexof operator as implemented and leave the non-clashing-name bikeshedding to the committee.

-- gpd
 

[Ryan Johnson]

On 23/07/2015 12:52 AM, David Krauss wrote:

On 2015–07–23, at 7:39 AM, Ryan Johnson <sco...@gmail.com> wrote:

1. 
   Unfortunately, the obvious analogue for std::indexof<T> would be:
   
   
   template <typename T, size_t N=__indexof(T)>
   struct indexof {
      static constexpr size_t value = N;
   };
   

That’s why I suggested an alias template. Alias template substitutions occur before argument substitutions or type deduction. So, the usage

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

gets transformed into something like

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

What I’m trying to illustrate here is that the parameter type will be Ts && regardless of the Xs values, but Xs can still be deduced from the context where the alias template was used, because the alias template has been substituted away before deduction begins.

OK, I read that too quickly before and didn't "get" that std::indexed_type<Ts,Xs> *is* Ts.

However, the compiler won't know that, and I'm still struggling to see how the code you propose could actually compile. I'm not aware of any case where today's compilers can "work backward" from a function arg whose type is both instantiation-dependent and type-dependent on T, and successfully infer what T should be (unless T is also used directly).

Can you elaborate on that part?

Also, even if it can somehow be made to compile, that style of syntax is very different from today's C++, which would worry me. The committee seems to be less enthusiastic about proposals that require novel new syntax in order to work.

2. Thus, you'd need three different names for the std::indexof<T> concept, one for each kind of parameter pack, which would be pretty annoying. The __indexof() built-in faces no such difficulty.
   

...

Personally, I consider non-type template parameters as second-class citizens and keep them quarantined in the smallest possible utility classes.

Actually, that's a good point, and the whole point of this proposal is drastically reduce the need for `template <typename... Ts> template <sizeof_t... Ns>' nesting that's often required for working with std::tuple. Template template parameters are handy in the cases where they're useful---I think template <template <typename...> class Tuple, typename... Ts> is the official way to work with tuple-like objects, for example---but those are definitely less common than type parameters.

Anyway, I guess the world would not end if there were a std::indexof for typed, std::indexofN for non-type, and std::indexofT for template template or some such. Still ugly, though.

Thoughts?
Ryan

[Ryan Johnson]

Good point. If this ends up going the template route rather than the new-keyword route, variable templates would definitely be the way to go.

Still not sure about giving a particular template name special treatment by the compiler, tho... tracing its heritage across various aliases would require non-trivial work, and argument dependent lookup would be a mess. For example:

template <typename T>
using my_indexof = std::indexof<T>; // why not?
template <size_t N>
using int_indexof = std::indexof<N>; // eh???
namespace foo { template <typename T> size_t indexof = /* something */; }
namespace bar { template <int N> size_t indexof = /* something */; }

using std::indexof;
using foo::indexof;
using bar::indexof;
/* what now? */

I'm sure it could all be worked through, but it would all be new, prone to causing unintended consequences, and feels orthogonal to this proposal. The additional complexity and feature creep would worry me.

Ryan

[Ryan Johnson]

On 23/07/2015 3:25 AM, Giovanni Piero Deretta wrote:

On Thursday, July 23, 2015 at 7:53:00 AM UTC+1, David Krauss wrote:

[...]

2. Thus, you'd need three different names for the std::indexof<T> concept, one for each kind of parameter pack, which would be pretty annoying. The __indexof() built-in faces no such difficulty.
   

Maybe Clang can implement __indexof() without difficulty, but an operator that equally accepts a template name, type, or expression as an argument doesn’t fit into the language grammar (and might not fit into other implementations) as easily.

don't know about template name, but sizeof has accepted either type or an expression without issues since forever.

Exactly. I was able to implement __indexof() in just a few hours by copy-pasting Clang's code for sizeof...(). No reason to expect a drastically different situation in other compilers.

Also new operators have been added recently (decltype, alignas, noexcept), without the need to wrap them in a metafunction veneer. Ryan should just propose the __indexof operator as implemented and leave the non-clashing-name bikeshedding to the committee.

What I'm hoping I can do, just to give the proposal maximum traction, is propose the magic __indexof() function and make a convincing argument that it can be implemented in a way that admits a metafunction veneer, should the committee decide to go that route.

The hope is that something like this (borrowing from Bengt's idea) would be to let __indexof(T) accept non-pack arguments (defaulting to value 0), and then have this definition:

template <typename T, size_t N=__indexof(T)>

constexpr size_t const indexof = N;

Because N is instantiation-dependent on T, __indexof(T) cannot take a value at template declaration time. The hope, then, is that code like this:

template <typename... Ts>
struct indexes {
   static constexpr size_t values[] = {std::indexof<Ts>...};
};

Would substitute the parameter pack into std::indexof before pack expansion begins (which seems likely), at which point the magic I've already implemented could kick in during pack expansion as usual. So far my clang-foo has not been up to the task of hooking into template parameter substitution process, though, because I'm not aware of any similar operator whose implementation I can use for inspiration.

Thanks,
Ryan

[David Krauss]

On 2015–07–23, at 7:59 PM, Ryan Johnson <sco...@gmail.com> wrote:

On 23/07/2015 12:52 AM, David Krauss wrote:

That’s why I suggested an alias template. Alias template substitutions occur before argument substitutions or type deduction. So, the usage

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

gets transformed into something like

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

What I’m trying to illustrate here is that the parameter type will be Ts && regardless of the Xs values, but Xs can still be deduced from the context where the alias template was used, because the alias template has been substituted away before deduction begins.

OK, I read that too quickly before and didn't "get" that std::indexed_type<Ts,Xs> *is* Ts.

However, the compiler won't know that, and I'm still struggling to see how the code you propose could actually compile. I'm not aware of any case where today's compilers can "work backward" from a function arg whose type is both instantiation-dependent and type-dependent on T, and successfully infer what T should be (unless T is also used directly).

Since C++11, this will compile:

template< typename t >

using same_type = t;

template< typename t >

t id( same_type< t > value ) { return value; }

int q = id( 3 );

same_type is an alias template, hence it is substituted before deduction. There’s no working backward.

My suggestion is to add a hidden deduced context, e.g. in an internal attribute. That’s what the compiler would know about.

Also, even if it can somehow be made to compile, that style of syntax is very different from today's C++, which would worry me. The committee seems to be less enthusiastic about proposals that require novel new syntax in order to work.

It’s nothing new: mention a template parameter in a deduced context, and its value is determined.

Actually, that's a good point, and the whole point of this proposal is drastically reduce the need for `template <typename... Ts> template <sizeof_t... Ns>' nesting that's often required for working with std::tuple.

Can you cite some code with this symptom? The problem doesn’t look familiar to me.

Template template parameters are handy in the cases where they're useful---I think template <template <typename...> class Tuple, typename... Ts> is the official way to work with tuple-like objects, for example---but those are definitely less common than type parameters.

Template template parameters are less powerful than a conventional “concept” of classes with a member template named temp. I tend to prefer the latter. Except, of course, when it’s a parameter of a partial specialization and the purpose is introspection.

Tuple-like objects are not guaranteed to have the form template< typename ... > class Tuple. In fact std::array is already an exception to that rule. Templates work by duck typing, and unless it’s part of the class interface that template arguments can be unpacked and inspected, that operation is off-limits. (That’s a terrible style of interface definition — that’s why classes have members.)

Anyway, I guess the world would not end if there were a std::indexof for typed, std::indexofN for non-type, and std::indexofT for template template or some such. Still ugly, though.

At some point, you start to rationalize dropping the std:: and making it a first-class operator. I think the most intuitive behavior, if operators are allowed, is to have something that expands to an index sequence pack of a given length — no enclosing pack pattern needed.

template <typename...Ts>
std::vector<size_t> foo(Ts&& ...) {

    constexpr std::size_t pack_length = sizeof ... (Ts);

    return { index_sequence( pack_length ) ... };

}

This would allow users to generate expressions from patterns without introducing templates at all.

[Ryan Johnson]

On 23/07/2015 6:48 AM, David Krauss wrote:

On 2015–07–23, at 7:59 PM, Ryan Johnson <sco...@gmail.com> wrote:

On 23/07/2015 12:52 AM, David Krauss wrote:

That’s why I suggested an alias template. Alias template substitutions occur before argument substitutions or type deduction. So, the usage

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

gets transformed into something like

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

What I’m trying to illustrate here is that the parameter type will be Ts && regardless of the Xs values, but Xs can still be deduced from the context where the alias template was used, because the alias template has been substituted away before deduction begins.

OK, I read that too quickly before and didn't "get" that std::indexed_type<Ts,Xs> *is* Ts.

However, the compiler won't know that, and I'm still struggling to see how the code you propose could actually compile. I'm not aware of any case where today's compilers can "work backward" from a function arg whose type is both instantiation-dependent and type-dependent on T, and successfully infer what T should be (unless T is also used directly).

Since C++11, this will compile:

template< typename t >

using same_type = t;

template< typename t >

t id( same_type< t > value ) { return value; }

int q = id( 3 );

same_type is an alias template, hence it is substituted before deduction. There’s no working backward.

My suggestion is to add a hidden deduced context, e.g. in an internal attribute. That’s what the compiler would know about.

The part that worries me is this code does not compile:

template <typename T, size_t N=0>

using indexed_type = T;

template <typename T, typename N>
size_t foo(indexed_type<T,N> &&) { return N; }

int main() { return foo("hi"); }

Because the compiler cannot figure out how to come up with N while instantiating foo. On gcc-4.9 for example:

scratch.cpp: In function ‘int main()’:
scratch.cpp:15:20: error: no matching function for call to ‘foo(const char [3])’
     return foo("hi");
                    ^
scratch.cpp:15:20: note: candidate is:
scratch.cpp:12:8: note: template<class T, long unsigned int N> size_t foo(indexed_type<T, N>&&)
 size_t foo(indexed_type<T, N> &&) { return N; }
        ^
scratch.cpp:12:8: note:   template argument deduction/substitution failed:
scratch.cpp:15:20: note:   couldn't deduce template parameter ‘N’
     return foo("hi");
                    ^

I fail to see how adding magic to indexed_type, so that N takes a meaningful value, would get past the deduction failure that has already occurred before the compiler ever tried to instantiate indexed_type. Today's compiler can't work backwards from the magical N of indexed_type in order to deduce the ordinary N of foo; type aliases do not change that situation as far as I can tell---your example compiles because the user has already supplied T and so alias substitution can go ahead; the user has *not* supplied N and so the compiler is unable to continue.

That's the part I was hoping you could elaborate on.

Actually, that's a good point, and the whole point of this proposal is drastically reduce the need for `template <typename... Ts> template <sizeof_t... Ns>' nesting that's often required for working with std::tuple.

Can you cite some code with this symptom? The problem doesn’t look familiar to me.

The code examples I cited in my original message can all be cast to use integer sequences instead of recursion; we chose to go with recursion rather than a variadic template helper function that takes a std::integer_sequence as an argument (following advice that variadic templates are slow and should be avoided when possible).

The documentation for std::integer_sequence has some nice examples:
http://en.cppreference.com/w/cpp/utility/integer_sequence

Stack Overflow is crawling with questions on the theme of how to turn <typename ...Ts> into <size_t ...Ns> when dealing with tuples. Here are just a few that turned up when I searched for "c++11 index tuple"

http://stackoverflow.com/questions/28997271/c11-way-to-index-tuple-at-runtime-without-using-switch
http://stackoverflow.com/questions/27936332/c11-building-a-stdtuple-from-a-template-function
http://stackoverflow.com/questions/17854219/creating-a-sub-tuple-starting-from-a-stdtuplesome-type

As a concrete example, suppose you're writing a set of generic hash functions:

template <typename T>
int hash(T const &t); // to be specialized/overridden

template <typename... Ts>
struct helper {
   template <size_t... Ns>
   static int hash(std::tuple<Ts...> const &tup, std::integer_sequence<Ns...>)
   {
      return (... ^ hash(std::get<Ts>(tup)));
   }
};

template <typename... Ts>
int hash(std::tuple<Ts...> const &tup) {
   return helper<Ts...>::hash(tup, std::integer_sequence_for<Ts...>());
}

With __indexof() the body of the hash function for std::tuple reduces to:

return (... ^ hash(std::get<__indexof(Ts)>(tup)));

Anyway, I guess the world would not end if there were a std::indexof for typed, std::indexofN for non-type, and std::indexofT for template template or some such. Still ugly, though.

At some point, you start to rationalize dropping the std:: and making it a first-class operator. I think the most intuitive behavior, if operators are allowed, is to have something that expands to an index sequence pack of a given length — no enclosing pack pattern needed.

template <typename...Ts>
std::vector<size_t> foo(Ts&& ...) {

    constexpr std::size_t pack_length = sizeof ... (Ts);

    return { index_sequence( pack_length ) ... };

}

This would allow users to generate expressions from patterns without introducing templates at all.

It would take someone smarter than me to figure out how to implement that in a compiler. index_sequence takes a constant integer expression and so there is no indication that it has anything to do with parameter packs.

Seems like, if you're going to go this route, you'd want something like the N3723 someone mentioned earlier in this thread. That's a vastly bigger and more invasive feature than what I was proposing here, tho. Plus, I get the sense that the two are orthogonal: you could still benefit from an __indexof() as a simpler alternative to marshalling all that parameter pack manipulation machinery N3723 proposes.

Thoughts?
Ryan

[David Krauss]

On 2015–07–23, at 9:27 PM, Ryan Johnson <sco...@gmail.com> wrote:

On 23/07/2015 6:48 AM, David Krauss wrote:

On 2015–07–23, at 7:59 PM, Ryan Johnson <sco...@gmail.com> wrote:

On 23/07/2015 12:52 AM, David Krauss wrote:

That’s why I suggested an alias template. Alias template substitutions occur before argument substitutions or type deduction. So, the usage

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

gets transformed into something like

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

What I’m trying to illustrate here is that the parameter type will be Ts && regardless of the Xs values, but Xs can still be deduced from the context where the alias template was used, because the alias template has been substituted away before deduction begins.

OK, I read that too quickly before and didn't "get" that std::indexed_type<Ts,Xs> *is* Ts.

However, the compiler won't know that, and I'm still struggling to see how the code you propose could actually compile. I'm not aware of any case where today's compilers can "work backward" from a function arg whose type is both instantiation-dependent and type-dependent on T, and successfully infer what T should be (unless T is also used directly).

Since C++11, this will compile:

template< typename t >

using same_type = t;

template< typename t >

t id( same_type< t > value ) { return value; }

int q = id( 3 );

same_type is an alias template, hence it is substituted before deduction. There’s no working backward.

My suggestion is to add a hidden deduced context, e.g. in an internal attribute. That’s what the compiler would know about.

The part that worries me is this code does not compile:

template <typename T, size_t N=0>

What’s the default argument for?

using indexed_type = T;

template <typename T, typename N>
size_t foo(indexed_type<T,N> &&) { return N; }

int main() { return foo("hi"); }

Because the compiler cannot figure out how to come up with N while instantiating foo. On gcc-4.9 for example:

Yes, that is the hidden magic. It’s not a pure library solution. It’s a library interface with no need to add new syntax.

(What were you expecting? There are no instructions for sequential counting in that program.)

I fail to see how adding magic to indexed_type, so that N takes a meaningful value, would get past the deduction failure that has already occurred before the compiler ever tried to instantiate indexed_type.

Today's compiler can't work backwards from the magical N of indexed_type in order to deduce the ordinary N of foo; type aliases do not change that situation as far as I can tell---your example compiles because the user has already supplied T and so alias substitution can go ahead; the user has *not* supplied N and so the compiler is unable to continue.

The user doesn’t supply N, deduction (the “compiler magic”) does. I illustrated it as an attribute:

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

__index(Xs) is the deduced context. The double brackets are unnecessary, serving only for illustrative syntactic orientation. For comparison, consider this:

template< typename t, std::size_t v >
using ic = std::integral_constant< t, v >;

template <typename ... Ts, std::size_t ... Xs>

std::vector<std::size_t> foo( ic< Ts, Xs > ...) { return {Xs...}; }

int main() {

    auto v = foo( std::integral_constant< std::size_t, 3 >{}, std::integral_constant< std::size_t, 42 >{} );
}

This is valid C++11. The compiler doesn’t need the arguments of template parameters in order to substitute them into an alias template. (Default template arguments of alias templates don’t work the same way, so you might get confused if you tend to add default arguments everywhere. I never suggested any default arguments.)

That's the part I was hoping you could elaborate on.

Actually, that's a good point, and the whole point of this proposal is drastically reduce the need for `template <typename... Ts> template <sizeof_t... Ns>' nesting that's often required for working with std::tuple.

Can you cite some code with this symptom? The problem doesn’t look familiar to me.

The code examples I cited in my original message can all be cast to use integer sequences instead of recursion; we chose to go with recursion rather than a variadic template helper function that takes a std::integer_sequence as an argument (following advice that variadic templates are slow and should be avoided when possible).

Huh? std::tuple_element is not slower than a recursive template that reinvents it. Parameter packs are usually faster than recursive templates. Recursive templates are the C++98-era solution.

The GenSequence example makes it look like you were unaware of the existence of std::make_index_sequence.

The documentation for std::integer_sequence has some nice examples:
http://en.cppreference.com/w/cpp/utility/integer_sequence

Stack Overflow is crawling with questions on the theme of how to turn <typename ...Ts> into <size_t ...Ns> when dealing with tuples. Here are just a few that turned up when I searched for "c++11 index tuple”

I see. So "`template <typename... Ts> template <sizeof_t... Ns>’ nesting” is referring to the practice of declaring a nested class template, and then defining it out side the enclosing class definition. But why would someone write it that way?

http://stackoverflow.com/questions/28997271/c11-way-to-index-tuple-at-runtime-without-using-switch
http://stackoverflow.com/questions/27936332/c11-building-a-stdtuple-from-a-template-function
http://stackoverflow.com/questions/17854219/creating-a-sub-tuple-starting-from-a-stdtuplesome-type

I don’t see the objectionable syntax anywhere in there. Perhaps you could be more specific.

template <typename... Ts>
int hash(std::tuple<Ts...> const &tup) {
   return helper<Ts...>::hash(tup, std::integer_sequence_for<Ts...>());
}

With __indexof() the body of the hash function for std::tuple reduces to:

return (... ^ hash(std::get<__indexof(Ts)>(tup)));

You still didn’t use any "template <typename... Ts> template <sizeof_t... Ns> nesting,” at least not per se.

Anyway, given a sequence pack operator, call it unpack_sequence, you wouldn’t need to declare anything extra. The function would also be generically applicable to tuple-like types. The entire solution is reduced to:

template < typename tuple_like >
int hash(tuple_like const &tup) {
   return hash( ... ^ std::get< unpack_sequence( std::tuple_size< tuple_like >::value ) >( tup ) );
}

Seems like, if you're going to go this route, you'd want something like the N3723 someone mentioned earlier in this thread. That's a vastly bigger and more invasive feature than what I was proposing here, tho. Plus, I get the sense that the two are orthogonal: you could still benefit from an __indexof() as a simpler alternative to marshalling all that parameter pack manipulation machinery N3723 proposes.

An unpack_sequence operator would be self-contained. N3728 is about dropping std::tuple from std::tuple< a, b, c > such that <a, b, c> is its own entity. There’s no particular connection.

[Edward Catmur]

On Friday, 24 July 2015 04:06:43 UTC+1, David Krauss wrote:

An unpack_sequence operator would be self-contained. N3728 is about dropping std::tuple from std::tuple< a, b, c > such that <a, b, c> is its own entity. There’s no particular connection.

N3728 is about having typelists that can be returned by metafunctions and unpacked directly, rather than having to be passed in (down the stack or metastack) to be inferred as parameter packs. It mentions std::tuple only in context of the somewhat prevalent usage of std::tuple as a typelist vocabulary type; N3728 typelists can't be instantiated so they don't replace std::tuple as a runtime data type.

In this case, the connection would be that the library can given N generate a typelist for the sequence 0..N-1 that can be unpacked directly:

template < typename tuple_like >
int hash(tuple_like const &tup) {

   return ... ^ hash( std::get< std::make_index_sequence_v< std::tuple_size< tuple_like >::value > >( tup ) );
} //                            ^-- metafunction returning typelist 0..N-1

As Ryan has mentioned, N3728 is a more extensive feature than indexof - although arguably less "magic".

[Ryan Johnson]

Do you have any sense of how likely your proposal is to be accepted? Because if it got in, the need for __indexof() would decrease precipitously... though it might still be convenient to have both around.

(David, I'm still digesting your email, a reply is in the works)

Ryan

[Edward Catmur]

Ah, n3728 is not my proposal, it's from Mike Spertus (I'm just a bystander here). Mike looks to be quite busy shepherding template argument type deduction (n4469), variadic lock_guard (n4470) and constructor template parameter deduction (n4471) through, but maybe he'll be able to pick n3728 back up at some point. (Really, I have absolutely no idea what its prospects are.)

[Ryan Johnson]

A stand-in for the missing compiler magic. Makes N available without the user having to specify it directly. Though I start to get the impression you want the magic to happen directly in the signature/declaration of foo, triggered by the compiler's recognizing the (otherwise utterly mundane) std::indexed_type?

using indexed_type = T;

template <typename T, typename N>
size_t foo(indexed_type<T,N> &&) { return N; }

int main() { return foo("hi"); }

Because the compiler cannot figure out how to come up with N while instantiating foo. On gcc-4.9 for example:

Yes, that is the hidden magic. It’s not a pure library solution. It’s a library interface with no need to add new syntax.

You still haven't given any hint of how this hidden magic you propose would be compatible with standard C++ template selection, see below.

I fail to see how adding magic to indexed_type, so that N takes a meaningful value, would get past the deduction failure that has already occurred before the compiler ever tried to instantiate indexed_type.

Today's compiler can't work backwards from the magical N of indexed_type in order to deduce the ordinary N of foo; type aliases do not change that situation as far as I can tell---your example compiles because the user has already supplied T and so alias substitution can go ahead; the user has *not* supplied N and so the compiler is unable to continue.

The user doesn’t supply N, deduction (the “compiler magic”) does. I illustrated it as an attribute:

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

__index(Xs) is the deduced context. The double brackets are unnecessary, serving only for illustrative syntactic orientation. For comparison, consider this:

template< typename t, std::size_t v >
using ic = std::integral_constant< t, v >;

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( ic< Ts, Xs > ...) { return {Xs...}; }

int main() {

    auto v = foo( std::integral_constant< std::size_t, 3 >{}, std::integral_constant< std::size_t, 42 >{} );
}

This is valid C++11. The compiler doesn’t need the arguments of template parameters in order to substitute them into an alias template. (Default template arguments of alias templates don’t work the same way, so you might get confused if you tend to add default arguments everywhere. I never suggested any default arguments.)

Eh??? The compiler most certainly needs the arguments if it is to substitute them. The above code is valid C++11 precisely because the caller provides both the Ts and Xs when calling foo(). The template alias does nothing to change that, it merely provides a shorter name for std::integral_constant.

If I understand correctly, you are proposing to make foo() itself magical, with the magic triggered by the appearance of an otherwise mundane std::indexed_type in its signature, or by some variable attribute affixed to the args. The problem is, the way template deduction works in C++, the compiler will not even consider foo() because the Xs cannot be deduced from information supplied *at the call site* and so it will never see the bits that are supposed to trigger the magic that would provide Xs.

Changing that behavior would be a Big Deal, because it changes the semantics of template selection---which would already be a big deal by itself---in a way that requires the compiler to do significantly more work for all template candidates (searching for bits of magic in their signatures), when the vast majority of them will not actually make use of the feature. I doubt the Committee would be interested in making such a large change to the language to support such a small feature.

Now, I could have missed some key detail here. I am by no means an authority on the C++ standard or compiler internals (though I know enough about the latter to get myself in trouble, at least). If you know of some clean way your suggestion could actually be defined at the language level and implemented in a compiler, I'd be delighted to hear details about it.

Actually, that's a good point, and the whole point of this proposal is drastically reduce the need for `template <typename... Ts> template <sizeof_t... Ns>' nesting that's often required for working with std::tuple.

Can you cite some code with this symptom? The problem doesn’t look familiar to me.

The code examples I cited in my original message can all be cast to use integer sequences instead of recursion; we chose to go with recursion rather than a variadic template helper function that takes a std::integer_sequence as an argument (following advice that variadic templates are slow and should be avoided when possible).

Huh? std::tuple_element is not slower than a recursive template that reinvents it. Parameter packs are usually faster than recursive templates. Recursive templates are the C++98-era solution.

The GenSequence example makes it look like you were unaware of the existence of std::make_index_sequence.

I know about std::index_sequence and std::make_index_sequence (see below). GenSequence came from our code base, which is C++11-only because the versions of gcc we can use don't support C++14 yet.

Anyway, recursion is alive and well in C++11 and beyond, though perhaps we've gotten better at hiding that fact behind standardized types. Huge amounts of meta-programming techniques rely on various flavors of recursion. Many of the various template helpers in the STL are recursive---std::make_index_sequence and std::tuple being especially relevant to this discussion.

That said, it's true that we're slowly moving away from recursion as the be-all/end-all. C++11 variadic templates start to address some reasons we use recursion so much, as do its restricted constexpr functions. C++14 std::index_sequence helps a bit (by at least hiding some kinds of recursion in a library class), and its generalized constexpr functions-help a lot (by moving more complex meta-computations to function rather than template code); C++17 fold expressions are another big step (by eliminating recursion entirely from compatible kinds of computations). Most of those approaches don't eliminate the explosion of template helper functions, though (fold expressions being a massive exception to that claim).

This proposal is just trying to eliminate a source of recursion and/or helper functions that these previous advances don't seem to have covered. The main messiness that would be left is std::tuple and std::get, both of which seem pretty difficult to achieve non-recursively.

The documentation for std::integer_sequence has some nice examples:
http://en.cppreference.com/w/cpp/utility/integer_sequence

Stack Overflow is crawling with questions on the theme of how to turn <typename ...Ts> into <size_t ...Ns> when dealing with tuples. Here are just a few that turned up when I searched for "c++11 index tuple”

I see. So "`template <typename... Ts> template <sizeof_t... Ns>’ nesting” is referring to the practice of declaring a nested class template, and then defining it out side the enclosing class definition. But why would someone write it that way?

I don’t see the objectionable syntax anywhere in [the StackOverflow links]. Perhaps you could be more specific.

template <typename... Ts>
int hash(std::tuple<Ts...> const &tup) {
   return helper<Ts...>::hash(tup, std::integer_sequence_for<Ts...>());
}

You still didn’t use any "template <typename... Ts> template <sizeof_t... Ns> nesting,” at least not per se.

The nesting is here:

template <typename... Ts> struct helper {
   template <size_t... Ns>

   static int hash(std::tuple<Ts...> const &tup, std::index_sequence<Ns...>);
};

You could mask the nesting in various ways, for example by doing instead:

template <typename Tuple> struct helper2 {
   template <size_t... Ns>
   static int hash(Tuple const &tup, std::index_sequence<Ns...>);
};

But that doesn't change the complexity of the types the compiler has to work with when instantiating the member function template:

    int helper<int, float, double, bool>::hash<0ul, 1ul, 2ul, 3ul>(
        std::tuple<int, float, double, bool> const&,
        std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul>)
vs.

    int helper2<std::tuple<int, float, double, bool> >::hash<0ul, 1ul, 2ul, 3ul>(
        std::tuple<int, float, double, bool> const&,
        std::integer_sequence<unsigned long, 0ul, 1ul, 2ul, 3ul>)

If anything, the latter is slightly more complex, because it handles tuple-like objects in addition to std::tuple. In contrast, with __indexof or similar in place, you wouldn't have that second layer of templating and would instead have only:

    int hash<int, float, double, bool>
        (std::tuple<int, float, double, bool> const&);

    int hash2<std::tuple<int, float, double, bool> >
        (std::tuple<int, float, double, bool> const&);

template < typename tuple_like >
int hash(tuple_like const &tup) {
   return hash( ... ^ std::get< unpack_sequence( std::tuple_size< tuple_like >::value ) >( tup ) );
}

In contrast, your unpack_sequence would have to "hoist" an otherwise non-pack statement, giving it a second set of variadic templates (the size_t... sequence). N3728 would give something nearly identical. Both create a new parameter pack to be unpacked, in addition to any packs that were already present.

On the other hand, these "create-a-pack" approaches have the benefit of *not* needing to explicitly bring in a <typename...> pack. That could be useful at times, such as the tuple_like idiom you make a good argument for using. Creating a pack also means the code won't care whether there are other packs around; nor would it care whether those other packs are type, non-type, or template template.

Thoughts?
Ryan

[Ryan Johnson]

On 24/07/2015 11:52 AM, Edward Catmur wrote:
> Ah, n3728 is not my proposal, it's from Mike Spertus (I'm just a
> bystander here). Mike looks to be quite busy shepherding template
> argument type deduction (n4469), variadic lock_guard (n4470) and
> constructor template parameter deduction (n4471) through, but maybe
> he'll be able to pick n3728 back up at some point. (Really, I have
> absolutely no idea what its prospects are.)

Ah. N4471 will be really nice to have, and N4469 wouldn't be unwelcome
either. Go Mike!

Ryan

[David Krauss]

On 2015–07–25, at 4:33 AM, Ryan Johnson <sco...@gmail.com> wrote:

On 23/07/2015 9:06 PM, David Krauss wrote:

What’s the default argument for?

A stand-in for the missing compiler magic. Makes N available without the user having to specify it directly. Though I start to get the impression you want the magic to happen directly in the signature/declaration of foo, triggered by the compiler's recognizing the (otherwise utterly mundane) std::indexed_type? 

The magic would happen in a modification to the type T generated by indexed_type<T>. In terms of the [[__index]] attribute:

// Standard library source code

template< typename type >

using indexed_type = Ts [[__index (Xs)]];

// User source code

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

// After alias template substitution

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

                           // ^ both deduced ^

The implementation work would be in adding a new deduced context. (Again, the implementation would not likely use actual double-bracket attribute syntax, I’m just showing where such an internal keyword could fit in the grammar.)

You could say that std::indexed_type would generate a magic signature, but only by applying ordinary alias template substitution to a magic keyword.

If I understand correctly, you are proposing to make foo() itself magical, with the magic triggered by the appearance of an otherwise mundane std::indexed_type in its signature, or by some variable attribute affixed to the args. The problem is, the way template deduction works in C++, the compiler will not even consider foo() because the Xs cannot be deduced from information supplied *at the call site* and so it will never see the bits that are supposed to trigger the magic that would provide Xs.

Parameters are deduced when they are mentioned in deduced contexts. If the compiler’s internals need an argument to correspond to the index sequence parameter, it can simply generate such a pack, upon encountering the magic keyword in the signature.

Changing that behavior would be a Big Deal, because it changes the semantics of template selection---which would already be a big deal by itself---in a way that requires the compiler to do significantly more work for all template candidates (searching for bits of magic in their signatures), when the vast majority of them will not actually make use of the feature. I doubt the Committee would be interested in making such a large change to the language to support such a small feature.

We can’t prove the implementation difficulty without trying to implement it. The proof (or disproof) is in the pudding.

That said, it's true that we're slowly moving away from recursion as the be-all/end-all. C++11 variadic templates start to address some reasons we use recursion so much, as do its restricted constexpr functions. C++14 std::index_sequence helps a bit (by at least hiding some kinds of recursion in a library class), and its generalized constexpr functions-help a lot (by moving more complex meta-computations to function rather than template code); C++17 fold expressions are another big step (by eliminating recursion entirely from compatible kinds of computations). Most of those approaches don't eliminate the explosion of template helper functions, though (fold expressions being a massive exception to that claim).

This proposal is just trying to eliminate a source of recursion and/or helper functions that these previous advances don't seem to have covered. The main messiness that would be left is std::tuple and std::get, both of which seem pretty difficult to achieve non-recursively.

The proposal doesn’t eliminate any template recursion, it eliminates [make_]index_sequence uses and attendant helper template declarations. Recursion is needed for algorithms where each iteration depends on the last. index_sequence and your proposal are useful when each pack item is treated independently.

template < typename tuple_like >
int hash(tuple_like const &tup) {
   return hash( ... ^ std::get< unpack_sequence( std::tuple_size< tuple_like >::value ) >( tup ) );
}

In contrast, your unpack_sequence would have to "hoist" an otherwise non-pack statement, giving it a second set of variadic templates (the size_t... sequence).

unpack_sequence(N) would simply be an unexpanded pack (§14.5.3/6). “Hoisting” is just what happens whenever you name a pack. The possibility of an unexpanded pack in a non-template context is also part of the price of N3728.

N3728 would give something nearly identical. Both create a new parameter pack to be unpacked, in addition to any packs that were already present.

On the other hand, these "create-a-pack" approaches have the benefit of *not* needing to explicitly bring in a <typename...> pack. That could be useful at times, such as the tuple_like idiom you make a good argument for using. Creating a pack also means the code won't care whether there are other packs around; nor would it care whether those other packs are type, non-type, or template template.

Right.

I see this as a dichotomy between two local optimums: If no new keyword is allowed, the best solution is indexed_type because it doesn’t care whether the pack is type or non-type, it only requires a type in a deduced pack pattern. It’s as close to a drop-in replacement as we can get. If a new keyword is allowed, the best solution is unpack_sequence because it allows you to locally unpack things (even numeric sequences with other pack basis), without introducing any new kind of entity to the language.

Even if my sensibility about optimality is off, there are two mutually exclusive alternatives. I think the committee is willing to make a bigger change, so it’s not too much to worry about adding keyword or such.

[David Krauss]

On 2015–07–25, at 10:09 AM, David Krauss <pot...@gmail.com> wrote:

The magic would happen in a modification to the type T generated by indexed_type<T>. In terms of the [[__index]] attribute:

// Standard library source code

template< typename type >

using indexed_type = Ts [[__index (Xs)]];

Sorry, that should be:

template< typename type, size_t index >
using indexed_type = type [[__index (index)]];

[Myriachan]

What if there were a keyword "restof...(Xs)" (not real name) that returned a template parameter pack of everything after the currently-expanding one?  This would work and even be more flexible than an "indexof...(Xs)" operator.

void test_function(const std::tuple<int, int, int> &, const std::tuple<int, int> &, const std::tuple<int> &)
{
    std::puts("meow");
}

template <typename... Ts>
void intermediate_function()
{
    test_function(std::tuple<Ts, restof...(Ts)>()...);
}

void caller_function()
{
    intermediate_function<int, int, int>();
}

Then the example from the beginning of the thread becomes:

template <typename...Ts>
std::vector<std::size_t> foo(Ts&& ...) { return {sizeof...(Ts) - sizeof...(restof...(Ts)) - 1}; }

int main() {
   std::vector a{0,1,2}, b=foo("hi", "ho", "hum");
   assert(a == b); // succeeds
}

Melissa

[Ryan Johnson]

On 24/07/2015 9:49 PM, Myriachan wrote:

What if there were a keyword "restof...(Xs)" (not real name) that returned a template parameter pack of everything after the currently-expanding one? 

Interesting... kind of a lispy car/cdr for parameter packs?

This would work and even be more flexible than an "indexof...(Xs)" operator.

void test_function(const std::tuple<int, int, int> &, const std::tuple<int, int> &, const std::tuple<int> &)
{
    std::puts("meow");
}

template <typename... Ts>
void intermediate_function()
{
    test_function(std::tuple<Ts, restof...(Ts)>()...);
}

void caller_function()
{
    intermediate_function<int, int, int>();
}

This one can be achieved already, simply by having `template <typename T, typename... Ts>', and is
often used to require 1+ parameters rather than the 0+ a parameter pack allows.

Then the example from the beginning of the thread becomes:

template <typename...Ts>
std::vector<std::size_t> foo(Ts&& ...) { return {sizeof...(Ts) - sizeof...(restof...(Ts)) - 1}; }


Something is off with this example; a missing "..." perhaps?

template <typename...Ts>
std::vector<std::size_t> foo(Ts&& ...)
{


   return {(sizeof...(Ts) - sizeof...(restof...(Ts)) - 1)...};
}


That's actually rather clever.

I feel like this would be a nice addition to N3728. Once you have first-class parameter packs, having the ability to slice and dice them would be very useful, and pack manipulation operations are notably absent from that proposal.

I'm not so sure it makes a good stand-alone feature, though, because C++ currently has no concept of manipulating parameter packs inside a function.

Ryan

[Ryan Johnson]

On 24/07/2015 8:09 PM, David Krauss wrote:

On 2015–07–25, at 4:33 AM, Ryan Johnson <sco...@gmail.com> wrote:

On 23/07/2015 9:06 PM, David Krauss wrote:

What’s the default argument for?

A stand-in for the missing compiler magic. Makes N available without the user having to specify it directly. Though I start to get the impression you want the magic to happen directly in the signature/declaration of foo, triggered by the compiler's recognizing the (otherwise utterly mundane) std::indexed_type? 

The magic would happen in a modification to the type T generated by indexed_type<T>. In terms of the [[__index]] attribute:

// Standard library source code

template< typename type >

using indexed_type = Ts [[__index (Xs)]];

// User source code

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( std::indexed_type< Ts, Xs > && ...) { return {Xs...}; }

// After alias template substitution

template <typename ... Ts, std::size_t ... Xs>
std::vector<std::size_t> foo( Ts [[__index (Xs)]] && ...) { return {Xs...}; }

                           // ^ both deduced ^

The implementation work would be in adding a new deduced context. (Again, the implementation would not likely use actual double-bracket attribute syntax, I’m just showing where such an internal keyword could fit in the grammar.)

You could say that std::indexed_type would generate a magic signature, but only by applying ordinary alias template substitution to a magic keyword.

OK, that's about what I thought you were saying.

If I understand correctly, you are proposing to make foo() itself magical, with the magic triggered by the appearance of an otherwise mundane std::indexed_type in its signature, or by some variable attribute affixed to the args. The problem is, the way template deduction works in C++, the compiler will not even consider foo() because the Xs cannot be deduced from information supplied *at the call site* and so it will never see the bits that are supposed to trigger the magic that would provide Xs.

Parameters are deduced when they are mentioned in deduced contexts. If the compiler’s internals need an argument to correspond to the index sequence parameter, it can simply generate such a pack, upon encountering the magic keyword in the signature.

From that perspective, the `Ts [[__index (Xs)]]' is vastly more likely to be implementable, because the compiler (clang at least) has no machinery in place to detect "special" template class names (which could be obfuscated arbitrarily by use of typedefs, aliases, etc.). Putting the magic in an attribute also solves the namespace pollution problem an operator would face.

However... I just realized there's a glaring problem with this approach: it does not work with member functions of a template class. To give a simplistic example:

template <typename... Ts>
struct my_tuple : std::tuple<Ts...>
{
   using std::tuple<Ts...>::tuple;
   int hash()
   {
      /* Nothing to attach [[__index(Xs)]] to, nor std::indexed_type */
   }
};

There's no clear way to make my_tuple::hash() a template function in a way that allowed the necessary Ts,Xs pairing, because doing so would create a new/different typed parameter pack and hash() doesn't take any arguments to kick-start deduction with. It also wouldn't work to require the Xs... at class level, because that would force the user to supply all the Xs when instantiating the class. You couldn't hide the extra template parameters behind an alias template, because those suffer the same shortcoming.

The __indexof operator doesn't suffer this problem because it can work directly with the existing parameter pack, rather than having to manufacture its own "special" one.
  
Based on that, I'd say both the std::indexed_type<Ts,Xs> and Ts [[__index(Xs)]] ideas are out of the running.

Changing that behavior would be a Big Deal, because it changes the semantics of template selection---which would already be a big deal by itself---in a way that requires the compiler to do significantly more work for all template candidates (searching for bits of magic in their signatures), when the vast majority of them will not actually make use of the feature. I doubt the Committee would be interested in making such a large change to the language to support such a small feature.

We can’t prove the implementation difficulty without trying to implement it. The proof (or disproof) is in the pudding.

Potentially fatal flaws aside, I've spent a bit of time around the relevant parts of clang's implementation, while implementing the __indexof operator.

I think I know enough that I could attempt a prototype of the Ts [[pack_index(Xs)]] attribute approach to see whether it's easy or even possible to generate the extra parameter Xs parameter pack at the right moment.

The std::indexed_type<Ts,Xs> flavor of magic would be a non-starter, though, because there is no machinery in place to detect a "special" template class name (which could be obfuscated arbitrarily by use of typedefs and template aliases).

All Standards-mandated template classes are implemented either without magic, or by invoking magical built-in operators as part of their (otherwise mundane) definition. Everything I've seen of gcc's libstdc++-v3 says the same approach is used there. No doubt the functionality could be jammed in by someone with enough motivation, but my impression is that it wouldn't be a pleasant task, and I definitely don't know enough about clang to attempt it myself.

This proposal is just trying to eliminate a source of recursion and/or helper functions that these previous advances don't seem to have covered. The main messiness that would be left is std::tuple and std::get, both of which seem pretty difficult to achieve non-recursively.

The proposal doesn’t eliminate any template recursion, it eliminates [make_]index_sequence uses and attendant helper template declarations.

Using std::make_index_sequence just moves the recursion from the call site into library code, which changes nothing from the compiler's perspective (see below). That's what I meant when I described it as "hiding some kinds of recursion in a library class."

In libstdc++v3 (gcc) the recursion lurks in this helper template:

  template<size_t _Num>
    struct _Build_index_tuple
    {
      typedef typename _Build_index_tuple<_Num - 1>::__type::__next __type;
    };
  template<>
    struct _Build_index_tuple<0>
    {
      typedef _Index_tuple<> __type;
    };

In libc++ (clang), things are a *lot* more complex. It does 8x unwinding of the recursion by means of helper template structs __make, __repeat, __parity (an effort to improve compilation speed I imagine). The actual recursion comes because the definitions of __make and __parity mutually depend on each other. You can search for "struct __parity" in the source browser if you're interested in the gory details.

If you want to get rid of the recursion entirely, you have to either eliminate the need for std::make_index_sequence (e.g. by introducing the sort of feature this proposal focuses on), or else implement it non-recursively (again, using the sort of feature this proposal focuses on). I'd strongly prefer the former because it eliminates the boilerplate that users have to deal with when using std::index_sequence.

template < typename tuple_like >
int hash(tuple_like const &tup) {
   return hash( ... ^ std::get< unpack_sequence( std::tuple_size< tuple_like >::value ) >( tup ) );
}

In contrast, your unpack_sequence would have to "hoist" an otherwise non-pack statement, giving it a second set of variadic templates (the size_t... sequence).

unpack_sequence(N) would simply be an unexpanded pack (§14.5.3/6). “Hoisting” is just what happens whenever you name a pack. The possibility of an unexpanded pack in a non-template context is also part of the price of N3728.

By "hoisting" I meant the use of an unexpanded parameter pack in a context where one is not otherwise expected (thank you for helping me nail that down with your concise statement). IMO that capability is the main feature of N3728. Without the first-class parameter packs that N3728 proposes, the notion of an unexpanded parameter pack outside any variadic template context---or inside a variadic template context, but in an expression that does not mention any of the formal parameter packs---is completely foreign.

BTW, even if something like N3728 were accepted, it does not provide a clean mechanism for converting a parameter pack into a <size_t...> pack, so this proposal would still be useful. It does close an important gap, though, by providing a way to define std::tuple non-recursively.

N3728 would give something nearly identical. Both create a new parameter pack to be unpacked, in addition to any packs that were already present.

On the other hand, these "create-a-pack" approaches have the benefit of *not* needing to explicitly bring in a <typename...> pack. That could be useful at times, such as the tuple_like idiom you make a good argument for using. Creating a pack also means the code won't care whether there are other packs around; nor would it care whether those other packs are type, non-type, or template template.

Right.

I see this as a dichotomy between two local optimums: If no new keyword is allowed, the best solution is indexed_type because it doesn’t care whether the pack is type or non-type, it only requires a type in a deduced pack pattern.

I'm not seeing how you could use indexed_type with non-type or template template parameter packs. If you still want to pursue it in spite of the flaws discussed earlier, could you provide an example?

If a new keyword is allowed, the best solution is unpack_sequence because it allows you to locally unpack things (even numeric sequences with other pack basis), without introducing any new kind of entity to the language.

Eh? It does require a new entity: an unexpanded parameter pack that is not part of any enclosing variadic template definition. While it might be tempting to hack it in quietly for this one (very limited) use case, I suspect the Committee would much rather that any new entity be fleshed out fully to avoid surprises and ugliness later on, when people inevitably try to apply the concept in new and unanticipated ways.

That said, the unpack_sequence idea *is* tempting because it lets you work with subsequences, an ability that __indexof() operator would not provide. But I also feel like ability to slice and dice parameter packs would be better integrated with N3728 or proposed as a separate feature (which would fill the one remaining gap when working with tuples, namely how to implement things like std::get and std::tuple_element non-recursively).

Ryan

[David Krauss]

On 2015–07–25, at 11:18 PM, Ryan Johnson <sco...@gmail.com> wrote:

However... I just realized there's a glaring problem with this approach: it does not work with member functions of a template class. To give a simplistic example:

template <typename... Ts>
struct my_tuple : std::tuple<Ts...>
{
   using std::tuple<Ts...>::tuple;
   int hash()
   {
      /* Nothing to attach [[__index(Xs)]] to, nor std::indexed_type */
   }
};

There's no clear way to make my_tuple::hash() a template function in a way that allowed the necessary Ts,Xs pairing, because doing so would create a new/different typed parameter pack and hash() doesn't take any arguments to kick-start deduction with. It also wouldn't work to require the Xs... at class level, because that would force the user to supply all the Xs when instantiating the class. You couldn't hide the extra template parameters behind an alias template, because those suffer the same shortcoming.

Yeah, good point. It would be no improvement on the status quo here.

It’s a fatal flaw that it wouldn’t work with primary class templates, and that the obvious application of partial specialization would produce a template that isn’t actually more specialized than the primary.

The __indexof operator doesn't suffer this problem because it can work directly with the existing parameter pack, rather than having to manufacture its own "special" one.
  
Based on that, I'd say both the std::indexed_type<Ts,Xs> and Ts [[__index(Xs)]] ideas are out of the running.

…

I think I know enough that I could attempt a prototype of the Ts [[pack_index(Xs)]] attribute approach to see whether it's easy or even possible to generate the extra parameter Xs parameter pack at the right moment.

The std::indexed_type<Ts,Xs> flavor of magic would be a non-starter, though, because there is no machinery in place to detect a "special" template class name (which could be obfuscated arbitrarily by use of typedefs and template aliases).

Again, indexed_type is an alias template, so it vanishes before deduction begins. indexed_type and [[pack_index(Xs)]] are one and the same solution. There’s no class template involved.

This proposal is just trying to eliminate a source of recursion and/or helper functions that these previous advances don't seem to have covered. The main messiness that would be left is std::tuple and std::get, both of which seem pretty difficult to achieve non-recursively.

The proposal doesn’t eliminate any template recursion, it eliminates [make_]index_sequence uses and attendant helper template declarations.

Using std::make_index_sequence just moves the recursion from the call site into library code, which changes nothing from the compiler's perspective (see below). That's what I meant when I described it as "hiding some kinds of recursion in a library class."

It’s not really the same, since the library-internal helper gets memoized. All the optimizations you found in libc++, for instance, only matter when first encountering a sequence that’s longer than anything yet seen in the TU.

Also, std::tuple doesn’t actually get instantiated when it’s used only as a pack holder type. Pure metaprogramming shouldn’t ever care whether it’s a complete class or not.

By "hoisting" I meant the use of an unexpanded parameter pack in a context where one is not otherwise expected (thank you for helping me nail that down with your concise statement). IMO that capability is the main feature of N3728. Without the first-class parameter packs that N3728 proposes, the notion of an unexpanded parameter pack outside any variadic template context---or inside a variadic template context, but in an expression that does not mention any of the formal parameter packs---is completely foreign.

Disembodied template argument lists, and members that evaluate to pack expansions, are nothing to sneeze at, either.

BTW, even if something like N3728 were accepted, it does not provide a clean mechanism for converting a parameter pack into a <size_t...> pack, so this proposal would still be useful. It does close an important gap, though, by providing a way to define std::tuple non-recursively.

N3728 would allow something like

template< std::size_t len >

std::size_t ... unpack_sequence = std::make_index_sequence< len >::value ...;

An operator to do the same would be redundant.

I'm not seeing how you could use indexed_type with non-type or template template parameter packs. If you still want to pursue it in spite of the flaws discussed earlier, could you provide an example?

I don’t plan to pursue it, but the non-type pack would need to appear inside a template-id naming a type. For example:

template< int ... i, template< int > class ... tt, std::size_t ... x >

void f( std::indexed_type< tt< i >, x > ... );

If a new keyword is allowed, the best solution is unpack_sequence because it allows you to locally unpack things (even numeric sequences with other pack basis), without introducing any new kind of entity to the language.

Eh? It does require a new entity: an unexpanded parameter pack that is not part of any enclosing variadic template definition.

Nothing in the language specification requires that unexpanded pack names must occur inside variadic template declarations. That just happens to be the only way to get one.

It’s perhaps a new sort of entity to the implementation, but not to the language.

While it might be tempting to hack it in quietly for this one (very limited) use case, I suspect the Committee would much rather that any new entity be fleshed out fully to avoid surprises and ugliness later on, when people inevitably try to apply the concept in new and unanticipated ways.

What potential complication? The grammar outside templates is the same as the grammar inside. Non-dependent contexts are usually easier to process than dependent ones.

That said, the unpack_sequence idea *is* tempting because it lets you work with subsequences, an ability that __indexof() operator would not provide. But I also feel like ability to slice and dice parameter packs would be better integrated with N3728 or proposed as a separate feature (which would fill the one remaining gap when working with tuples, namely how to implement things like std::get and std::tuple_element non-recursively).

It seems like the proposals in this thread fall into a spectrum of degrees of decoupling between the numbers and the pack. indexof is most tightly coupled because it goes into the pack expansion, indexed_type is less coupled because it goes into the pack declaration, and unpack_sequence is least coupled because it goes anywhere and it only knows about an integral constant expression.

The way to implement std::tuple_element non-recursively is with an intrinsic. Given non-recursive tuple_element, recursion disappears from std::get too. This optimization apparently has a lower priority than the various others that have already been implemented. If users are rolling their own tuple_element, that’s another problem that may be addressed by providing a more convenient interface, e.g.:

template< std::size_t n, typename ... t >

using nth_type = std::tuple_element_t< n, std::tuple< t ... > >;

FWIW, the only subsequences I’ve ever wanted are the nth element, the tail sequence obtained by recursive list-unwinding, and the head sequence up to an element found by recursion (whose index is not known beforehand). These three cases each happen a lot, and they’re already the easy ones.

[Edward Catmur]

std::get is already nonrecursive in any modern implementation using variadic inheritance. Admittedly, you still need recursion to generate the index_sequence - but as you pointed out above, that gets memoized for any N and smaller.

[David Krauss]

On 2015–07–27, at 6:52 AM, Edward Catmur <e...@catmur.co.uk> wrote:

std::get is already nonrecursive in any modern implementation using variadic inheritance. Admittedly, you still need recursion to generate the index_sequence - but as you pointed out above, that gets memoized for any N and smaller. 

The return type of std::get is usually determined by std::tuple_element, so my assertion is that a nonrecursive tuple_element implies a nonrecursive get.

It’s also possible to eliminate the tuple_element metafunction by replacing it with C++14 deduced return type. That would require the tuple base classes (one per element) to have types like __tuple_base< tuple< element ... >, index > whereas current implementations use something like __tuple_base< element, index >.

If it’s really such a win to eliminate template recursion from std::get, implementations already have various means to do so.

[Edward Catmur]

On Monday, 27 July 2015 03:00:04 UTC+1, David Krauss wrote:

The return type of std::get is usually determined by std::tuple_element, so my assertion is that a nonrecursive tuple_element implies a nonrecursive get.

It’s also possible to eliminate the tuple_element metafunction by replacing it with C++14 deduced return type. That would require the tuple base classes (one per element) to have types like __tuple_base< tuple< element ... >, index > whereas current implementations use something like __tuple_base< element, index >.

Actually, you can have nonrecursive get without having to put all the elements into tuple_base. I find the most natural implementation is the following:

template<std::size_t I, class T> T& tuple_get(tuple_base<I, T>& obj) { return obj.value; }

If you call tuple_get<N> on the variadically derived class then everything gets sorted out by overload resolution on the implicit object parameter.

Similarly, there's a nice trick using variadic inheritance to compute tuple_element (and/or nth_type) without recursion or any magic:

template<bool, class> struct nth_type_base {};
template<class T> struct nth_type_base<true, T> { using type = T; };
template<std::size_t I, class...> struct nth_type_impl;
template<std::size_t I, std::size_t... Is, class... Ts>
  struct nth_type_impl<I, std::index_sequence<Is...>, Ts...> : nth_type_base<I == Is, Ts>... {};

template<std::size_t I, class T> struct tuple_element;
template<std::size_t I, class... Ts>
  struct tuple_element<I, tuple<Ts...>> : nth_type_impl<I, std::index_sequence_for<Ts...>, Ts...> {};

If it’s really such a win to eliminate template recursion from std::get, implementations already have various means to do so.

 

Definitely - and as you say, it's surprising that they haven't yet.

[David Krauss]

On 2015–07–27, at 4:23 PM, Edward Catmur <e...@catmur.co.uk> wrote:

Actually, you can have nonrecursive get without having to put all the elements into tuple_base. I find the most natural implementation is the following:

template<std::size_t I, class T> T& tuple_get(tuple_base<I, T>& obj) { return obj.value; }


If you call tuple_get<N> on the variadically derived class then everything gets sorted out by overload resolution on the implicit object parameter.

We’re getting a bit off topic here, but you can’t get class T without using recursion in the form of tuple_element.

You can implement get without changing __tuple_base, by using overload resolution over indexed dispatch tags, but that adds inefficiency.

Naming the derived type tuple<T...> as a template argument merely mentions a preexisting specialization, which doesn’t require any extra compiler resources. Anyway, the same effect could be achieved by nesting tuple_base inside a class parameterized on <T...>.

Here’s a working proof of concept. amalgam_ftor can be found here.

template< typename t >
struct tag {
    typedef t type;
};

template< typename ... elem >
struct tuple_impl {
    template< typename e, std::size_t x >
    struct type_map_entry {
        tag< e > operator () ( std::integral_constant< std::size_t, x > );
    };

    template< typename = std::make_index_sequence< sizeof ... (elem) > >
    struct type_map;

    template< std::size_t ... x >
    struct type_map< std::index_sequence< x ... > > {
        typedef amalgam_ftor< type_map_entry< elem, x > ... > type;
    };

    template< std::size_t x >
    struct tuple_entry {
        typename decltype( typename type_map<>::type{}( std::integral_constant< std::size_t, x >{} ) )::type value;

        template< typename ... arg >
        tuple_entry( arg && ... a )
            : value( std::forward< arg >( a ) ... ) {}
    };

    template< typename = std::make_index_sequence< sizeof ... (elem) > >
    struct base;

    template< std::size_t ... x >
    struct base< std::index_sequence< x ... > >
        : tuple_entry< x > ... {
        // Most of the std::tuple implementation goes here.
    };
};

template< typename ... elem >
struct tuple
    : tuple_impl< elem ... >::template base<> {
    using tuple_impl< elem ... >::template base<>::base;
};

// test
extern tuple< int, char, long > q;
char c = { q.tuple_entry< 1 >::value }; // no narrowing => it found the type

The complexity here is in forming and using the overload set at the time tuple is instantiated. Hopefully all the bootstrap stuff (overload set, etc) gets garbage collected, and what’s left is an ideal map from numbers, through base classes, to types.

Similarly, there's a nice trick using variadic inheritance to compute tuple_element (and/or nth_type) without recursion or any magic:

I remembered that something like that existed, but couldn’t remember how, and didn’t find it in the current libc++. I think that recursion is more efficient in practice.

That particular form of the trick requires N instantiations, so it looks less efficient than recursion. Unless you have a parallelized template engine, recursion will win by early exit.

If it’s really such a win to eliminate template recursion from std::get, implementations already have various means to do so.

 

Definitely - and as you say, it's surprising that they haven't yet.

I didn’t say it was surprising. In my experience, when a metaprogram needs random access, an overload set is a better tool. Instantiating very large std::tuple objects is a red flag. std::tuple_element really shouldn’t be a bottleneck. Implementation effort is better spent optimizing the real fundamentals: name lookup, class template instantiation, overload resolution constexpr evaluation, etc. The true performance culprits can be found by running real workloads in profiler, and there’s no sense in second guessing the work of guys who do that.

[Ryan Johnson]

That's very clever. The recursion is still there---hiding in amalgam_ftor's abuse of std::common_type ---but at least it only has to happen once when a instantiating each kind of tuple that way.

FYI, the code fails to compile with gcc-4.9.

First problem is minor: struct amalgam has no default constructor (needed when playing with the type_map decltype stuff). Solution is to either add "amalgam() = default" to the amalgam class definition, or to use std::declval<> inside the decltype() to obtain an amalgam instance.

Second problem is weird: "error: request for member ‘tuple_entry’ is ambiguous" (naming tuple_entry<2>, tuple_entry<1>, and tuple_entry<0> as candidates). Compiles fine with clang-3.6, so I don't know whether it's a gcc bug or if your code relies on a clang-ism. I suspect the former since I see no reason why asking for tuple_entry<1> should consider tuple_entry<0> or tuple_entry<2> at all, let alone consider them to be ambiguous.

Ryan

[David Krauss]

On 2015–07–27, at 8:40 PM, Ryan Johnson <sco...@gmail.com> wrote:

That's very clever. The recursion is still there---hiding in amalgam_ftor's abuse of std::common_type ---but at least it only has to happen once when a instantiating each kind of tuple that way.

Ah, I forgot that part was recursive. It really shouldn’t be; using declarations should support pack expansion. Anyway, still, it reduces the O(N^2) instantiations that result from applying tuple_element<T,i> over i : [0, N) to just O(N) instantiations.

It also shouldn’t be specializing std::common_type, but it works :P . The year was 2011, I was naive and carefree…

FYI, the code fails to compile with gcc-4.9. 

First problem is minor: struct amalgam has no default constructor (needed when playing with the type_map decltype stuff). Solution is to either add "amalgam() = default" to the amalgam class definition, or to use std::declval<> inside the decltype() to obtain an amalgam instance. 

This doesn’t happen with GCC 5.1.

Second problem is weird: "error: request for member ‘tuple_entry’ is ambiguous" (naming tuple_entry<2>, tuple_entry<1>, and tuple_entry<0> as candidates). Compiles fine with clang-3.6, so I don't know whether it's a gcc bug or if your code relies on a clang-ism. I suspect the former since I see no reason why asking for tuple_entry<1> should consider tuple_entry<0> or tuple_entry<2> at all, let alone consider them to be ambiguous.

Hmm, GCC does have a point. The injected-class-names are declared “following the opening brace of the class definition” which suggests that they’re local to each specialization. Perhaps there should be a DR; since C++11 it makes more sense for the template-like behavior of injected-class-names to be modeled after alias templates.

Anyway, using a different lookup route fixes it:

template< typename ... elem >
struct tuple
    : tuple_impl< elem ... >::template base<> {

    typedef tuple_impl< elem ... > impl;

    using impl::template base<>::base;
};

extern tuple< int, char, long > q;

char c = { q.impl::tuple_entry< 1 >::value };

[Ryan Johnson]

On 26/07/2015 12:19 AM, David Krauss wrote:

On 2015–07–25, at 11:18 PM, Ryan Johnson <sco...@gmail.com> wrote:

The std::indexed_type<Ts,Xs> flavor of magic would be a non-starter, though, because there is no machinery in place to detect a "special" template class name (which could be obfuscated arbitrarily by use of typedefs and template aliases).

Again, indexed_type is an alias template, so it vanishes before deduction begins. indexed_type and [[pack_index(Xs)]] are one and the same solution. There’s no class template involved.

The point was that compilers don't have any machinery for detecting "special" template names in that way---whether aliases or classes. The machinery exists---at parse time---to detect an unqualified name (e.g. "sizeof") as a keyword or built-in operator; that happens all the time. That's not the same as checking during semantic analysis whether some qualified name (e.g. std::foo) is somehow special, *especially* in the face of aliases: std::foo could actually be a template alias for something else, or the user could have a "using std::foo" somewhere and give an unqualified name (and they could even have introduced their own templates which would then compete for ADL and cause confusion). Maybe it wouldn't be difficult to add that machinery, but it's definitely not there right now.

This proposal is just trying to eliminate a source of recursion and/or helper functions that these previous advances don't seem to have covered. The main messiness that would be left is std::tuple and std::get, both of which seem pretty difficult to achieve non-recursively.

The proposal doesn’t eliminate any template recursion, it eliminates [make_]index_sequence uses and attendant helper template declarations.

Using std::make_index_sequence just moves the recursion from the call site into library code, which changes nothing from the compiler's perspective (see below). That's what I meant when I described it as "hiding some kinds of recursion in a library class."

It’s not really the same, since the library-internal helper gets memoized. All the optimizations you found in libc++, for instance, only matter when first encountering a sequence that’s longer than anything yet seen in the TU.

Fair enough. That's why we have libraries in the first place: for the reuse benefit that comes from factoring out bits of functionality (and the subsequent ability to optimize that functionality once and for all).

It still leaves a lot of boilerplate behind, though.

By "hoisting" I meant the use of an unexpanded parameter pack in a context where one is not otherwise expected (thank you for helping me nail that down with your concise statement). IMO that capability is the main feature of N3728. Without the first-class parameter packs that N3728 proposes, the notion of an unexpanded parameter pack outside any variadic template context---or inside a variadic template context, but in an expression that does not mention any of the formal parameter packs---is completely foreign.

Disembodied template argument lists, and members that evaluate to pack expansions, are nothing to sneeze at, either.

True. N3728 go well beyond what your unpack_sequence would demand. But unpack_sequence opens the genie's bottle so to speak, by creating a disembodied parameter pack.

BTW, even if something like N3728 were accepted, it does not provide a clean mechanism for converting a parameter pack into a <size_t...> pack, so this proposal would still be useful. It does close an important gap, though, by providing a way to define std::tuple non-recursively.

N3728 would allow something like

template< std::size_t len >

std::size_t ... unpack_sequence = std::make_index_sequence< len >::value ...;

An operator to do the same would be redundant.

Interesting point. And as I said early on, if something like N3728 were to improve the situation I'd not complain.

Unfortunately, that proposal looks extremely undercooked at this point. It is sorely lacking in specific details, and I don't think it would actually work to use parameter packs as concepts the way it proposes:

using integral_types = <int, char, long, /* etc */>;
auto sum(integral_types... x) { return (... + x); }

Rather than magically selecting one type out of the pack for each argument, the above would attempt to expand to a pack of packs, which would be nonsensical. Unless the proposal specifically adds that magic... but the text seemed to imply that the above was an intuitive/natural consequence of allowing first-class parameter packs. Anyway, I digress...

I'm not seeing how you could use indexed_type with non-type or template template parameter packs. If you still want to pursue it in spite of the flaws discussed earlier, could you provide an example?

I don’t plan to pursue it, but the non-type pack would need to appear inside a template-id naming a type. For example:

template< int ... i, template< int > class ... tt, std::size_t ... x >

void f( std::indexed_type< tt< i >, x > ... );

If a new keyword is allowed, the best solution is unpack_sequence because it allows you to locally unpack things (even numeric sequences with other pack basis), without introducing any new kind of entity to the language.

Eh? It does require a new entity: an unexpanded parameter pack that is not part of any enclosing variadic template definition.

Nothing in the language specification requires that unexpanded pack names must occur inside variadic template declarations. That just happens to be the only way to get one.

IMO that's splitting hairs: the Standard is---or at least attempts to be---a prescriptive document where behaviors are forbidden unless explicitly stated otherwise.

It’s perhaps a new sort of entity to the implementation, but not to the language.

While it might be tempting to hack it in quietly for this one (very limited) use case, I suspect the Committee would much rather that any new entity be fleshed out fully to avoid surprises and ugliness later on, when people inevitably try to apply the concept in new and unanticipated ways.

What potential complication? The grammar outside templates is the same as the grammar inside. Non-dependent contexts are usually easier to process than dependent ones.

Once people see that disembodied parameter packs are allowed, they would want to use them in other ways other than this one extremely limited use case, and be confused/annoyed to learn that they can't. Then comes another proposal to fill the gaps, but it would be constrained by whatever semantics the existing entity already defined.

Constexpr and template variables would be a very good example of this: all sorts of utility and type traits classes (esp. those descending from std::integral_constant) would be cleaned up significantly if changed to constexpr template variables. But that would break backwards compatibility so we'll be stuck with unnecessarily complex code.

That said, the unpack_sequence idea *is* tempting because it lets you work with subsequences, an ability that __indexof() operator would not provide. But I also feel like ability to slice and dice parameter packs would be better integrated with N3728 or proposed as a separate feature (which would fill the one remaining gap when working with tuples, namely how to implement things like std::get and std::tuple_element non-recursively).

It seems like the proposals in this thread fall into a spectrum of degrees of decoupling between the numbers and the pack. indexof is most tightly coupled because it goes into the pack expansion, indexed_type is less coupled because it goes into the pack declaration, and unpack_sequence is least coupled because it goes anywhere and it only knows about an integral constant expression.

Sure. And each comes with its own warts and benefits.

The indexof operator is kind of nice because it's extremely clear about where those numbers come from, and there's no way to accidentally come up with mismatched parameter packs when trying to use it. That means less cognitive overhead for the user and less complexity for the compiler. At the cost of being very direct and difficult to hide behind a template type.

The unpack_sequence is kind of nice because you don't need an "external" parameter pack at all, which widens the number of use cases it can help with. At the cost of introducing a new concept to the language in an incomplete way.

Ryan

[David Krauss]

On 2015–07–27, at 9:11 PM, David Krauss <pot...@gmail.com> wrote:

Perhaps there should be a DR; since C++11 it makes more sense for the template-like behavior of injected-class-names to be modeled after alias templates.

On second thought, that doesn’t help. The template-name of each nested alias template would still be unique to its class. It’s a Clang bug.

[Ryan Johnson]

On 27/07/2015 7:11 AM, David Krauss wrote:

On 2015–07–27, at 8:40 PM, Ryan Johnson <sco...@gmail.com> wrote:

That's very clever. The recursion is still there---hiding in amalgam_ftor's abuse of std::common_type ---but at least it only has to happen once when a instantiating each kind of tuple that way.

Ah, I forgot that part was recursive. It really shouldn’t be; using declarations should support pack expansion. Anyway, still, it reduces the O(N^2) instantiations that result from applying tuple_element<T,i> over i : [0, N) to just O(N) instantiations.

100% agree, on both counts.

It also shouldn’t be specializing std::common_type, but it works :P . The year was 2011, I was naive and carefree…

That one definitely makes you want to wash your hands after looking at it... but if it works and the alternatives are vastly more hairy, I'd go for the dirty hack any time.

Ryan

[David Krauss]

On 2015–07–27, at 9:12 PM, Ryan Johnson <sco...@gmail.com> wrote:

The point was that compilers don't have any machinery for detecting "special" template names in that way---whether aliases or classes.

There’s nothing special about the alias that needs to be detected. The alias specialization gets converted to a dependent attribute before the “detection” step — deduction — begins.

The point is moot, so maybe we should give it a rest.

Disembodied template argument lists, and members that evaluate to pack expansions, are nothing to sneeze at, either.

True. N3728 go well beyond what your unpack_sequence would demand. But unpack_sequence opens the genie's bottle so to speak, by creating a disembodied parameter pack.

N3728 proposes disembodied argument list syntax like typedef <int, short, void> ts. That’s different from unpack_sequence(N) which is an ordinary pack, but potentially in a non-template context.

Once people see that disembodied parameter packs are allowed, they would want to use them in other ways other than this one extremely limited use case, and be confused/annoyed to learn that they can't. Then comes another proposal to fill the gaps, but it would be constrained by whatever semantics the existing entity already defined.

This is a slippery slope argument. But it goes further: if you can define your own freestanding sequence of types, why not a sequence of templates or values? When should you use a compile-time value sequence as opposed to a constexpr array or initializer_list? What about mixed argument lists; shouldn’t <int, 3, std::tuple> be supported if <int, short, void> is?

unpack_sequence generates a pack of values, but N3728 actually only addresses types. The library implementation I suggested earlier was a bit of extrapolation. As you said, N3728 isn’t fully cooked. As a result, we tend to use it as a blank canvas. That can generate a false sense of consensus.

A single, minimal operator avoids all that. If there are so many orthogonal directions down the slippery slope, that’s in itself an argument to stay at the top.

Constexpr and template variables would be a very good example of this: all sorts of utility and type traits classes (esp. those descending from std::integral_constant) would be cleaned up significantly if changed to constexpr template variables. But that would break backwards compatibility so we'll be stuck with unnecessarily complex code.

C++14 does have the _v suffix.

The indexof operator is kind of nice because it's extremely clear about where those numbers come from, and there's no way to accidentally come up with mismatched parameter packs when trying to use it. That means less cognitive overhead for the user and less complexity for the compiler. At the cost of being very direct and difficult to hide behind a template type.

The unpack_sequence is kind of nice because you don't need an "external" parameter pack at all, which widens the number of use cases it can help with. At the cost of introducing a new concept to the language in an incomplete way.

Fair assessment.

unpack_sequence is a bit verbose in its own way, but it potentially saves the effort of making any template declaration in the first place. It would be nice to see an apples to apples comparison between indexof and unpack_sequence.

My guess is that the committee would prefer to see all these proposals presented side-by-side and working through identical example problems.

[Ryan Johnson]

On 27/07/2015 9:20 AM, David Krauss wrote:

Disembodied template argument lists, and members that evaluate to pack expansions, are nothing to sneeze at, either.

True. N3728 go well beyond what your unpack_sequence would demand. But unpack_sequence opens the genie's bottle so to speak, by creating a disembodied parameter pack.

N3728 proposes disembodied argument list syntax like typedef <int, short, void> ts. That’s different from unpack_sequence(N) which is an ordinary pack, but potentially in a non-template context.

You actually make a very good point that N3728 only addresses types, not integer sequences, and so is orthogonal in that respect. I also suspect strongly that N3728 will not mature in time for C++17, so let's drop it from the discussion and focus on stand-alone solutions to the problem at hand.

Constexpr and template variables would be a very good example of this: all sorts of utility and type traits classes (esp. those descending from std::integral_constant) would be cleaned up significantly if changed to constexpr template variables. But that would break backwards compatibility so we'll be stuck with unnecessarily complex code.

C++14 does have the _v suffix.

Definitely better than nothing, but still a hack to paper over the backwards compatibility issue. Anyway, there's nothing to be done for it. The language evolved in a way that would have been difficult to predict (or at least define precisely) up front, and this is the result.

The indexof operator is kind of nice because it's extremely clear about where those numbers come from, and there's no way to accidentally come up with mismatched parameter packs when trying to use it. That means less cognitive overhead for the user and less complexity for the compiler. At the cost of being very direct and difficult to hide behind a template type.

The unpack_sequence is kind of nice because you don't need an "external" parameter pack at all, which widens the number of use cases it can help with. At the cost of introducing a new concept to the language in an incomplete way.

Fair assessment.

unpack_sequence is a bit verbose in its own way, but it potentially saves the effort of making any template declaration in the first place. It would be nice to see an apples to apples comparison between indexof and unpack_sequence.

My guess is that the committee would prefer to see all these proposals presented side-by-side and working through identical example problems.

You're probably right. I'll have to dive back into clang when I get a chance, to get a sense of how easy or difficult it would be to implement unpack_sequence.

We agree that those two are the only viable candidates that have come up so far?

A follow-up question about unpack_sequence(): should it always take a constexpr size_t as its argument? Or should it also accept a parameter pack, for cases where you have one handy already? E.g.:

template <typename... Ts>
int hash(std::tuple<Ts...> const &tup)
{

   using std::hash; // ADL
   return (... ^ hash(std::get<unpack_sequence(Ts)>(tup)));
}

That would make it a superset of the __indexof() operator I implemented already, and avoid the need for boilerplate like unpack_sequence(sizeof...(Ts)). Though perhaps it's best to present the two fully independently, and let the Committee hash out any potential convergence of the two.

Actually, I should also throw in one idea I've considered but not had time to pursue:

Based on clang's internals, it should be relatively easy to define a slightly modified operator, call it __unsafe_spooky_pack_indexof(T) that returns the parser's current pack expansion index regardless of whether T itself is actually a parameter pack. This would be spooky black magic of the worst kind (and I couldn't say whether it could be easily implemented in another compiler), but it would allow:

namespace std
{
template <typename T, size_t N=__unsafe_spooky_pack_indexof(T)>

constexpr size_t const indexof = N;
}

template <typename... Ts>
int hash(std::tuple<Ts...> const &tup)
{

   using std::hash; // ADL
   return (... ^ hash(std::get<std::indexof<Ts>>(tup)));
}

The long, scary name should discourage use of the operator outside the intended library implementation, and use of std::indexof<T> with any T not directly expanded from a parameter pack would invoke undefined behavior (no diagnostic, because the rules of template instantiation would make it difficult for the compiler to detect improper use). In particular:

template <typename T>
struct foo { static constexpr size_t const N = std::indexof<T>; };
// undefined behavior

template <typename T>
constexpr size_t const bar = std::indexof<T>;
// undefined behavior

template <typename T>
using baz = std::indexof<T>;
// iffy but probably well-defined anywhere std::indexof would be well-defined

Behavior of std::indexof<T, N> (with user-supplied N) is perfectly well-defined because that would sidestep the spooky/unsafe default value computation. It would also be perfectly useless, unless you happened to need a mapping from types to size_t in some other context, and were willing to set it up manually.

I'm torn: namespace std is much less crowded than the global namespace, so std::indexof is more likely to be available than a new indexof keyword. But the __indexof() operator is much safer because improper uses fail to compile.

Thoughts?
Ryan

[Edward Catmur]

On Monday, 27 July 2015 12:13:29 UTC+1, David Krauss wrote:

On 2015–07–27, at 4:23 PM, Edward Catmur <e...@catmur.co.uk> wrote:

template<std::size_t I, class T> T& tuple_get(tuple_base<I, T>& obj) { return obj.value; }


We’re getting a bit off topic here, but you can’t get class T without using recursion in the form of tuple_element.

Sorry for the continued derailing; I'd like to know if I'm doing anything illegal. Can't the compiler deduce T from the tuple_base argument?

template<int I, class T> struct B { T value; };
template<int I, class T> T& get(B<I, T>& b) { return b.value; }
struct X : B<0, int>, B<1, float> {} x;
float& f = get<1>(x);  // seems to work

You can implement get without changing __tuple_base, by using overload resolution over indexed dispatch tags, but that adds inefficiency.

Naming the derived type tuple<T...> as a template argument merely mentions a preexisting specialization, which doesn’t require any extra compiler resources. Anyway, the same effect could be achieved by nesting tuple_base inside a class parameterized on <T...>.

Yes, but that makes the initial base classes of tuple<int, float> and tuple<int, float, char> distinct when they could be the same type, which does require extra compiler resources; and it bloats the symbol table.

Here’s a working proof of concept. amalgam_ftor can be found here.

[...]

The complexity here is in forming and using the overload set at the time tuple is instantiated. Hopefully all the bootstrap stuff (overload set, etc) gets garbage collected, and what’s left is an ideal map from numbers, through base classes, to types.

 Very impressive. I get a bit uncomfortable seeing decltype in metaprogramming, but maybe I'm just showing my age.

That particular form of the trick requires N instantiations, so it looks less efficient than recursion. Unless you have a parallelized template engine, recursion will win by early exit.

O(N/2) beats O(N) only when the constants are the same, and nonrecursive code can be more amenable to optimization - vectorization as well as parallelization. I guess the only way to tell is profiling.

I didn’t say it was surprising. In my experience, when a metaprogram needs random access, an overload set is a better tool. Instantiating very large std::tuple objects is a red flag. std::tuple_element really shouldn’t be a bottleneck. Implementation effort is better spent optimizing the real fundamentals: name lookup, class template instantiation, overload resolution constexpr evaluation, etc. The true performance culprits can be found by running real workloads in profiler, and there’s no sense in second guessing the work of guys who do that.

It's not just about the compiler, though; recursive implementations spill details into error messages and into linker and debug symbols. Stepping through a deep recursive call to std::get is annoying when it could be done in a single frame (or 2 at most).

[Edward Catmur]

On Monday, 27 July 2015 19:00:56 UTC+1, Ryan Johnson wrote:

You actually make a very good point that N3728 only addresses types, not integer sequences, and so is orthogonal in that respect.

Hey! N3728 mentions non-type parameters (in the context of reflection, but still) and in any case even if restricted to type parameters one could use a sequence of integral_constant as a stand-in for an integer sequence (at some cost of efficiency, perhaps).

 

I also suspect strongly that N3728 will not mature in time for C++17, so let's drop it from the discussion and focus on stand-alone solutions to the problem at hand. 

Agreed; I'll shut up now.

 

I'm torn: namespace std is much less crowded than the global namespace, so std::indexof is more likely to be available than a new indexof keyword. But the __indexof() operator is much safer because improper uses fail to compile.

In order to avoid adding a new keyword, is there any potential to stack a ... token on top of an existing keyword or operator, as was done with sizeof...? It'd have to avoid colliding with fold-expression, of course.

[Ryan Johnson]

Actually, that's a good point: indexof...(T) would probably parse unambiguously while still allowing `indexof' to be a normal identifier. As a bonus, it would be obvious at a glance that the operator is related to parameter packs, which is not true of the __indexof() I originally proposed:

template <typename... Ts>
int hash(std::tuple<Ts...> const &tup)
{
   using std::hash; // ADL

   return (... ^ hash(tup.get<indexof...(Ts)>(tup)));
}

template <typename... Ts>
auto reverse(std::tuple<Ts...> const &tup)
{
   using rtuple = std::tuple<
      std::tuple<Ts...>,
      typename std::tuple_element_t<sizeof...(Ts) - indexof...(Ts) - 1>>;
   return rtuple{std::get<sizeof...(Ts) - indexof...(Ts) - 1>(tup)...};
}

There's a bit of a mismatch with sizeof...(T) because the latter is a simple scalar expression that happens to take an unexpanded parameter pack as an argument, while the former expands with its parameter pack.  But maybe that doesn't matter too much?

Ryan

[Ryan Johnson]

On 27/07/2015 1:29 PM, Edward Catmur wrote:

Actually, that's a good point: indexof...(T) would probably parse unambiguously while still allowing `indexof' to be a normal identifier. As a bonus, it would be obvious at a glance that the operator is related to parameter packs, which is not true of the __indexof() I originally proposed:

template <typename... Ts>
int hash(std::tuple<Ts...> const &tup)
{
   using std::hash; // ADL

[Ryan Johnson]

On 27/07/2015 12:42 PM, Edward Catmur wrote:

On Monday, 27 July 2015 12:13:29 UTC+1, David Krauss wrote:

On 2015–07–27, at 4:23 PM, Edward Catmur <e...@catmur.co.uk> wrote:

template<std::size_t I, class T> T& tuple_get(tuple_base<I, T>& obj) { return obj.value; }


We’re getting a bit off topic here, but you can’t get class T without using recursion in the form of tuple_element.

Sorry for the continued derailing; I'd like to know if I'm doing anything illegal. Can't the compiler deduce T from the tuple_base argument?

From what I understood, he agreed it would work, but thought it would require more overload resolution effort from the compiler at the call site than his mapping trick did:

You can implement get without changing __tuple_base, by using overload resolution over indexed dispatch tags, but that adds inefficiency.

O(N/2) beats O(N) only when the constants are the same, and nonrecursive code can be more amenable to optimization - vectorization as well as parallelization. I guess the only way to tell is profiling.

But on the other hand these compilers have been optimizing the recursive case for years and only recently started worrying about parameter packs, so there could be a performance differential there (albeit a temporary one, hopefully).

I didn’t say it was surprising. In my experience, when a metaprogram needs random access, an overload set is a better tool. Instantiating very large std::tuple objects is a red flag. std::tuple_element really shouldn’t be a bottleneck. Implementation effort is better spent optimizing the real fundamentals: name lookup, class template instantiation, overload resolution constexpr evaluation, etc. The true performance culprits can be found by running real workloads in profiler, and there’s no sense in second guessing the work of guys who do that.

It's not just about the compiler, though; recursive implementations spill details into error messages and into linker and debug symbols. Stepping through a deep recursive call to std::get is annoying when it could be done in a single frame (or 2 at most).

Agree. Anything that allows the compiler to vomit simpler/fewer lines of template names is a Good Thing.

Ryan