De-pessimize compilation complexity for get<N> et. al.

[Dave Abrahams]

With some hints from Stephen Watanabe, I came up with the following proof-of-concept, which avoids the O(N²) 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?

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