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

Subject: [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:55:47

#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  
 Keywords:                |  
--------------------------+-------------------------------------------------
 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>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.