Свести последовательность последовательностей (последовательностей)

Question

Я использую boost :: fusion.

Допустим, у меня есть что-то вроде следующего:

make_vector(1, make_vector('b', 3, make_vector(4, 5.5), "six"), 7, 8)

Я хочу создать функцию f такую, что

f(make_vector(1, make_vector('b', 3, make_vector(4, 5.5), "six"), 7, 8)) 
-> [1, 'b', 3, 4, 5.5, "six", 7, 8]

то есть упрощенная версия последовательности.

Я не против, если это представление исходной последовательности или фактического вектора.

Я не против решенияв C ++ 0x, если он может компилироваться в GCC 4.5.1.

Примечание:

Хотя я предпочел бы не ограничивать элементы данных, если это помогаетне стесняйтесь требовать, чтобы все элементы «data» происходили из общего базового класса.выясните, что это за элементы данных, используя "is_base_of".

Answer 1

Вот одно из возможных решений, которое использует join рекурсивно. По сути, он делает следующее (в псевдо-Хаскеле):

flatten []     = []
flatten x      = [x]
flatten (x:xs) = flatten x ++ flatten xs

Рекурсивно уплощенная голова соединяется со сплющенным хвостом.

Это решение, скорее всего, не самое эффективное, поскольку оно строит множество представлений даже для отдельных значений; лучшим подходом может быть передача результирующей последовательности в качестве параметра в рекурсивных вызовах и непосредственное добавление в нее отдельных элементов, возможно, с использованием fold.

Вот код (заявление об отказе: я написал это довольно быстро, чтобы код мог быть заполнен ошибками и / или неидиоматическими способами выполнения действий):

namespace result_of
{
    template < typename Begin, typename End, class Enable = void >
    struct flatten_impl
    {
        typedef boost::fusion::single_view< typename 
            boost::fusion::result_of::value_of< Begin >::type 
        > flattenedHeadSequence;

        typedef typename 
            flatten_impl< typename
                boost::fusion::result_of::next< Begin >::type,
                End
            >::type flattenedTailSequence;

        typedef typename boost::fusion::result_of::join< const flattenedHeadSequence, const flattenedTailSequence >::type type;
    };


    template < typename Begin, typename End >
    struct flatten_impl< 
        Begin, 
        End, typename
        boost::enable_if< 
            boost::fusion::traits::is_sequence< typename
                boost::fusion::result_of::value_of< Begin >::type
            >
        >::type 
    >
    {
        typedef typename boost::fusion::result_of::value_of< Begin >::type headSequence;
        typedef typename 
            flatten_impl< typename
                boost::fusion::result_of::begin< headSequence >::type, typename
                boost::fusion::result_of::end< headSequence >::type 
            >::type flattenedHeadSequence;

        typedef typename 
            flatten_impl< typename
                boost::fusion::result_of::next< Begin >::type,
                End
            >::type flattenedTailSequence;

        typedef typename boost::fusion::result_of::join< const flattenedHeadSequence, const flattenedTailSequence >::type type;
    };


    template < typename End, typename Enable >
    struct flatten_impl< End, End, Enable >
    {
        typedef boost::fusion::vector< > type;
    };


    template < typename Sequence >
    struct flatten
    {
        typedef typename 
            flatten_impl< typename 
                boost::fusion::result_of::begin< Sequence >::type, typename 
                boost::fusion::result_of::end< Sequence >::type 
            >::type type;
    };    
}


template < typename Begin, typename End >
typename result_of::flatten_impl< Begin, End >::type 
flatten_impl( 
    const Begin & begin, 
    const End & end, typename 
    boost::disable_if<
        boost::fusion::traits::is_sequence< typename
            boost::fusion::result_of::value_of< Begin >::type
        >
    >::type * dummy = 0 )
{
    typedef result_of::flatten_impl< Begin, End > traits;
    typedef typename traits::flattenedHeadSequence headSequence;
    typedef typename traits::flattenedTailSequence tailSequence;

    return boost::fusion::join( 
        headSequence( boost::fusion::deref( begin ) ),
        flatten_impl( boost::fusion::next( begin ), end ) );
}


template < typename Begin, typename End >
typename result_of::flatten_impl< Begin, End >::type 
flatten_impl( 
    const Begin & begin, 
    const End & end, typename 
    boost::enable_if<
        boost::fusion::traits::is_sequence< typename
            boost::fusion::result_of::value_of< Begin >::type
        >
    >::type * dummy = 0 )
{
    typedef result_of::flatten_impl< Begin, End > traits;
    typedef typename traits::flattenedHeadSequence headSequence;
    typedef typename traits::flattenedTailSequence tailSequence;

    typedef typename boost::fusion::result_of::value_of< Begin >::type headType;

    const headType & head = boost::fusion::deref( begin );

    return boost::fusion::join(
        flatten_impl( boost::fusion::begin( head ), boost::fusion::end( head ) ),
        flatten_impl( boost::fusion::next( begin ), end ) );
}


template < typename End >
typename result_of::flatten_impl< End, End >::type
flatten_impl( const End &, const End &)
{
    return boost::fusion::make_vector( );
}


template < typename Sequence >
typename result_of::flatten< Sequence >::type 
flatten( const Sequence & seq )
{
    return flatten_impl( boost::fusion::begin( seq ), boost::fusion::end( seq ) );
}