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

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.

Примечание:

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

т.е.

class DataBase {} 

template <class T> 
class Data : public DataBase 
{ 
public: 
    Data(const T& x) : m_x(x) 
    T m_x; 
} 

template <class T> 
T make_data(const T& x) { return Data<T>(x); } 

Тогда

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

Я полагаю, то вы можете работать, какие элементы данных с помощью "is_base_of".

Answer 1

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

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