Allanar una secuencia de secuencias (de secuencias)

Question

Estoy usando boost :: fusion.

Digamos que tengo algo como el siguiente:

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

quiero producir una función f tal que

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] 

es decir, una versión aplanada de la secuencia.

No me importa si esta es una vista de la secuencia original o un vector real.

No me importa una solución en C++ 0x si se puede compilar en GCC 4.5.1.

Nota:

Mientras que prefiero no para restringir los elementos de datos, si ayuda, no dude en requerir que los "datos" elementos todos se derivan de una clase base común.

decir

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

Entonces

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

que la figura a continuación, se puede trabajar con lo que los elementos de datos son mediante el uso de "is_base_of".

Answer 1

Aquí hay una posible solución, que usa join recursivamente. Básicamente, se hace lo siguiente (en pseudo-Haskell):

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

de forma recursiva, la cabeza aplanada se concatena con la cola aplanada.

Esta solución es muy probable que no sea la más eficiente ya que construye muchas vistas, incluso para valores individuales; un mejor enfoque podría estar pasando la secuencia resultante como un parámetro en las llamadas recursivas y agregar directamente los elementos individuales en él, tal vez usando fold.

Aquí está el código (disclaimer: Escribí esto con bastante rapidez, por lo que el código podría ser llenado con los insectos y/o formas no idiomáticas de hacer las cosas):

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