[utility] [C++0x] indices/make_indices
While playing with GCC 4.3 and variadic templates, I came across the following problem: Say I have to write a function that takes a tuple as a parameter and needs to call another function with the expanded tuple. In code: template< typename... Ts > void f( const std::tuple< Ts... >& tp ) { g( tp... ); } OK, tp... doesn't work. Next try: template< typename... Ts > void f( const std::tuple< Ts... >& tp ) { g( std::get< Ns >( tp )... ); } That doesn't work either, but it's close, except that I only have Ts, not Ns (which need to expand from 0 to sizeof...( Ts ) - 1. Doug Gregor pointed me to N2080, which inspired me to create a light-weight general helper for cases where you need indices instead of types (or both). Here's the code that actually works: template< typename... Ts, std::size_t... Ns > void fimpl( const std::tuple< Ts... >& tp, const indices< Ns... >& ) { g( std::get< Ns >( tp )... ); } template< typename... Ts > void f( const std::tuple< Ts... >& tp ) { fimpl( tp, typename make_indices< sizeof...( Ts ) >::type() ); } with the following helpers: template< std::size_t... Ns > struct indices { }; template< std::size_t N, std::size_t... Ns > struct make_indices { typedef typename make_indices< N - 1, N - 1, Ns... >::type type; }; template< std::size_t... Ns > struct make_indices< 0, Ns... > { typedef indices< Ns... > type; }; While I appreciate any feedback/improvement/... on the specific problem/solution, there's also another issue here: These helpers are useful only for C++0x - I don't see how they could make any sense for the current C++ standard. There seem to be three options: a) Consider them an internal, undocumented implementation detail that other Boost libraries may use. No problem here, could be done today if there is interest. b) Make them part of the MPL. My gut feeling is that this is the wrong place - they don't belong to meta-programming because (as the example shows) they are useful in a variety of contexts. c) Make them a user-visible, documented feature of Boost. They are rather small so I'd compare them to next/prior: Not worth to be a full-fledged Boost library, but maybe part of Boost.Utilities. Thoughts? Regards, Daniel
on Sat Jul 19 2008, Daniel Frey <d.frey-AT-gmx.de> wrote:
OK, tp... doesn't work. Next try:
template< typename... Ts > void f( const std::tuple< Ts... >& tp ) { g( std::get< Ns >( tp )... ); }
Only slightly OT: in C++03, anyway, using a sequece of get<i> with increasing i to access all elements of a cons-list style tuple induces O(N^2) template instantiations. Have we done anything to fix that for C++0x? Did we legalize a flat (fusion-style) tuple implementation? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
AMDG David Abrahams wrote:
Only slightly OT: in C++03, anyway, using a sequece of get<i> with increasing i to access all elements of a cons-list style tuple induces O(N^2) template instantiations. Have we done anything to fix that for C++0x? Did we legalize a flat (fusion-style) tuple implementation?
get can be implemented such that even for cons-list tuples, it takes O(n) template instantiations to access all elements. In Christ, Steven Watanabe
How? -- Dave Abrahams Boostpro Computing http://boostpro.com On Jul 19, 2008, at 11:47 AM, Steven Watanabe <watanabesj@gmail.com> wrote:
AMDG
David Abrahams wrote:
Only slightly OT: in C++03, anyway, using a sequece of get<i> with increasing i to access all elements of a cons-list style tuple induces O(N^2) template instantiations. Have we done anything to fix that for C++0x? Did we legalize a flat (fusion-style) tuple implementation?
get can be implemented such that even for cons-list tuples, it takes O(n) template instantiations to access all elements.
In Christ, Steven Watanabe
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
AMDG David Abrahams wrote:
How?
In pseudocode using iterators: deref(advance(begin(tuple)), n) where advance is implemented as iterator advance(iterator x, int n) { if(n == 0) { return(x); } else { return(advance(x, n - 1)); } } This way we maximize memoization for a single tuple. In Christ, Steven Watanabe
Looks to me like you get O(n^2) instantiations of advance. You get N instantiations for the begin iterator, N-1 for the next and so on. What am I missing? -- Dave Abrahams Boostpro Computing http://boostpro.com On Jul 19, 2008, at 1:13 PM, Steven Watanabe <watanabesj@gmail.com> wrote:
AMDG
David Abrahams wrote:
How?
In pseudocode using iterators:
deref(advance(begin(tuple)), n)
where advance is implemented as
iterator advance(iterator x, int n) { if(n == 0) { return(x); } else { return(advance(x, n - 1)); } }
This way we maximize memoization for a single tuple.
In Christ, Steven Watanabe
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
AMDG David Abrahams wrote:
Looks to me like you get O(n^2) instantiations of advance. You get N instantiations for the begin iterator, N-1 for the next and so on. What am I missing?
get<0> instantiates advance<x, 0> get<1> instantiates advance<x, 1> and reuses advance<x, 0> get<2> instantiates advance<x, 2> and reuses advance<x, 1> ... In Christ, Steven Watanabe
on Sat Jul 19 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
David Abrahams wrote:
Looks to me like you get O(n^2) instantiations of advance. You get N instantiations for the begin iterator, N-1 for the next and so on. What am I missing?
get<0> instantiates advance<x, 0> get<1> instantiates advance<x, 1> and reuses advance<x, 0> get<2> instantiates advance<x, 2> and reuses advance<x, 1> ...
With the ++ in there, it all makes sense. Very clever! -- Dave Abrahams BoostPro Computing http://www.boostpro.com
________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Steven Watanabe [watanabesj@gmail.com] Enviado el: sábado, 19 de julio de 2008 19:13 Para: boost@lists.boost.org Asunto: Re: [boost] [utility] [C++0x] indices/make_indices
AMDG
In pseudocode using iterators:
deref(advance(begin(tuple)), n)
where advance is implemented as
iterator advance(iterator x, int n) { if(n == 0) { return(x); } else { return(advance(x, n - 1));
Shouldn't this last line be return(advance(++x, n - 1)); thus ruining the memoization? Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
on Sat Jul 19 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
AMDG
David Abrahams wrote:
How?
In pseudocode using iterators:
deref(advance(begin(tuple)), n)
where advance is implemented as
iterator advance(iterator x, int n) { if(n == 0) { return(x); } else { return(advance(x, n - 1)); } }
Wow, looking at the tuples code it seems there's a lot of optimization we can do now! // -- proof of concept -- // doesn't even need partial specialization (in case we care) template <unsigned N> struct tuple_drop_front { template <class Tuple> // compute resultant tuple struct result_ { typedef typename tuple_drop_front<N-1>::template result_<Tuple>::type::tail_type type; }; template <class Tuple> typename result_<Tuple>::type const& operator()(Tuple const& x) const { return tuple_drop_front<N-1>()(x).tail; } template <class Tuple> typename result_<Tuple>::type& operator()(Tuple& x) const { return tuple_drop_front<N-1>()(x).tail; } }; template <> struct tuple_drop_front<0> { template <class Tuple> struct result_ { typedef Tuple type; }; template <class Tuple> Tuple const& operator()(Tuple const& x) const { return x; } template <class Tuple> Tuple& operator()(Tuple& x) const { return x; } }; template <unsigned N, class Tuple> typename tuple_drop_front<N>::template result_<Tuple>::type::head_type& get(Tuple& t) { return tuple_drop_front<N>()(t).head; } template <unsigned N, class Tuple> typename tuple_drop_front<N>::template result_<Tuple>::type::head_type const& get(Tuple const& t) { return tuple_drop_front<N>()(t).head; } struct null_type {}; template <class HT, class TT = null_type> struct cons { cons() : head(), tail() {} template <class T, class U> cons(T const& x, U const& y) : head(x), tail(y) {} template <class T, class U> cons(T& x, U& y) : head(x), tail(y) {} template <class T, class U> cons(T const& x, U& y) : head(x), tail(y) {} template <class T, class U> cons(T& x, U const& y) : head(x), tail(y) {} template <class T> cons(T const& x) : head(x), tail() {} typedef HT head_type; HT head; typedef TT tail_type; TT tail; }; int main() { assert( get<0>( cons<int>(42) ) == 42 ); assert( get<0>( cons<int, cons<long> >(42, 10) ) == 42 ); assert( get<1>( cons<int, cons<long> >(42, 10) ) == 10 ); assert( get<0>( cons<int, cons<long, cons<char> > >(42, 3) ) == 42 ); assert( get<1>( cons<int, cons<long, cons<char> > >(42, 3) ) == 3 ); assert( get<2>( cons<int, cons<long, cons<char> > >(42, 3) ) == 0 ); } -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
Wow, looking at the tuples code it seems there's a lot of optimization we can do now!
So... deref(advance(begin(tuple)), n) where advance is implemented as iterator advance(iterator x, int n) { if (n == 0) return x; else return ++advance(x, n - 1); // corrected } Isn't this what we are already doing in fusion? template <> struct at_impl<cons_tag> { template <typename Sequence, typename N> struct apply { typedef typename mpl::eval_if< is_const<Sequence> , add_const<typename Sequence::cdr_type> , mpl::identity<typename Sequence::cdr_type> >::type cdr_type; typedef typename mpl::eval_if< mpl::bool_<N::value == 0> , mpl::identity<typename Sequence::car_type> , apply<cdr_type, mpl::int_<N::value-1> > > element; typedef typename mpl::eval_if< is_const<Sequence> , detail::cref_result<element> , detail::ref_result<element> >::type type; template <typename Cons, int N2> static type call(Cons& s, mpl::int_<N2>) { return call(s.cdr, mpl::int_<N2-1>()); } template <typename Cons> static type call(Cons& s, mpl::int_<0>) { return s.car; } static type call(Sequence& s) { return call(s, mpl::int_<N::value>()); } }; }; Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net
on Sat Jul 19 2008, Joel de Guzman <joel-AT-boost-consulting.com> wrote:
David Abrahams wrote:
Wow, looking at the tuples code it seems there's a lot of optimization we can do now!
So...
deref(advance(begin(tuple)), n)
where advance is implemented as
iterator advance(iterator x, int n) { if (n == 0) return x; else return ++advance(x, n - 1); // corrected }
Isn't this what we are already doing in fusion?
Nope...
template <> struct at_impl<cons_tag> { template <typename Sequence, typename N> struct apply { typedef typename mpl::eval_if< is_const<Sequence> , add_const<typename Sequence::cdr_type> , mpl::identity<typename Sequence::cdr_type> >::type cdr_type;
typedef typename mpl::eval_if< mpl::bool_<N::value == 0> , mpl::identity<typename Sequence::car_type> , apply<cdr_type, mpl::int_<N::value-1> >
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ This instantiates the template on the cdr with N-1 iterations i.e., it's like advance(++x, n-1) You need ++advance(x, n-1) to avoid O(N^2)
> element;
-- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote: [snip]
This instantiates the template on the cdr with N-1 iterations i.e., it's like advance(++x, n-1) You need ++advance(x, n-1) to avoid O(N^2)
> element;
Nifty! I implemented this in fusion. Pretty straightforward (yeah, I'm using partial specialization): template <typename Cons> struct cons_deref { typedef typename Cons::car_type type; }; template <typename Cons, int I> struct cons_advance { typedef typename cons_advance<Cons, I-1>::type::cdr_type type; }; template <typename Cons> struct cons_advance<Cons, 0> { typedef Cons type; }; Then: template <> struct at_impl<cons_tag> { template <typename Sequence, typename N> struct apply { typedef detail::cons_deref< typename cons_advance<Sequence, N::value>::type> element; ... }; As an added bonus, I unrolled advance for up to N==5. Thanks for the tips, Dave, Steven! Regards, -- Joel de Guzman http://www.boostpro.com http://spirit.sf.net
AMDG Joel de Guzman wrote:
David Abrahams wrote:
[snip]
Nifty! I implemented this in fusion. Pretty straightforward.
Um. You changed the result type calculation, but there are still O(n^2) function template instantiations. (at_impl<cons_tag>::apply<Sequence, N>::call<Cons, N2>) (Unfortunately, I have no idea what the relative cost of function template instantiations vs. class template instantiations is.) In Christ, Steven Watanabe
participants (5)
-
Daniel Frey -
David Abrahams -
JOAQUIN M. LOPEZ MUÑOZ -
Joel de Guzman -
Steven Watanabe