Re: [Boost-bugs] [Boost C++ Libraries] #2130: De-pessimize compilation complexity for get<N> et. al.

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #2130: De-pessimize compilation complexity for get<N> et. al.
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-07-19 23:56:41

#2130: De-pessimize compilation complexity for get<N> et. al.
---------------------------+------------------------------------------------
  Reporter:  dave          |       Owner:  jefffaust
      Type:  Bugs          |      Status:  new      
 Milestone:  Boost 1.36.0  |   Component:  tuple    
   Version:  Boost 1.35.0  |    Severity:  Problem  
Resolution:                |    Keywords:           
---------------------------+------------------------------------------------
Description changed by dave:

Old description:

> With some hints from Stephen Watanabe, I came up with the following
> proof-of-concept, which avoids the O(N^2) instantiation behavior of
> {{{get<0>(t)}}}, {{{get<1>(t)}}}, ... {{{get<N>(t)}}}.
>
> Seems to me that Boost.Tuple code is pretty old and crufty, and we could
> improve it a lot even for broken compilers.  If we're going to "ship" a
> TR1, it ought to be best-of-breed, right?
>
> {{{
> #!cpp
> // Copyright David Abrahams 2008. Distributed under the Boost
> // Software License, Version 1.0. (See accompanying
> // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
>
> #include <cassert>
>
> 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 );
> }
>
> }}}

New description:

 With some hints from Stephen Watanabe, I came up with the following proof-
 of-concept, which avoids the O(N^2^) instantiation behavior of
 {{{get<0>(t)}}}, {{{get<1>(t)}}}, ... {{{get<N>(t)}}}.

 Seems to me that Boost.Tuple code is pretty old and crufty, and we could
 improve it a lot even for broken compilers.  If we're going to "ship" a
 TR1, it ought to be best-of-breed, right?

 {{{
 #!cpp
 // Copyright David Abrahams 2008. Distributed under the Boost
 // Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

 #include <cassert>

 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 );
 }

 }}}

--
-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/2130#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.