Eine Folge von Sequenzen (von Sequenzen) abflachen

Question

Ich benutze boost :: fusion.

Lets sagen, ich habe so etwas wie die folgenden:

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

Ich möchte eine Funktion f erzeugen, so dass

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] 

das heißt eine abgeflachte Version der Sequenz.

Ich habe nichts dagegen, wenn dies eine Ansicht der ursprünglichen Sequenz oder eines tatsächlichen Vektors ist.

Ich habe keine Lösung in C++ 0x, wenn es auf GCC 4.5.1 kompilieren kann.

Hinweis:

Während ich nicht lieber die Datenelemente beschränken, wenn es hilft, können Sie zu verlangen, dass die „Daten“ alle Elemente von einer gemeinsamen Basisklasse ableiten.

heißt

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

Dann

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

ich meine, dann können Sie herausfinden, was die Datenelemente unter Verwendung von "is_base_of" sind.

Answer 1

Hier ist eine mögliche Lösung, die join rekursiv verwendet. Grundsätzlich geschieht Folgendes (in pseudo-Haskell):

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

Recursively, der abgeflachte Kopf zum Schwanz abgeflachten konkateniert wird.

Diese Lösung ist höchstwahrscheinlich nicht die effizienteste, da sie viele Ansichten selbst für einzelne Werte erstellt. Ein besserer Ansatz könnte sein, die resultierende Sequenz als Parameter in rekursiven Aufrufen zu übergeben und direkt die einzelnen Elemente darin hinzuzufügen, möglicherweise unter Verwendung von fold. Hier

ist der Code (Disclaimer: Ich schreibe dies recht schnell, so könnte der Code mit Bugs und/oder nicht-idiomatischen Möglichkeiten, Dinge zu tun, gefüllt werden):

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