Frage Reduziere eine Sequenz von Sequenzen (von Sequenzen)


Ich benutze boost :: fusion.

Sagen wir, ich habe etwas wie das Folgende:

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

Ich möchte eine Funktion f so erzeugen, 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]

d.h. eine abgeflachte Version der Sequenz.

Es macht mir nichts aus, wenn dies eine Ansicht der ursprünglichen Sequenz oder eines tatsächlichen Vektors ist.

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

Hinweis:

Obwohl ich es vorziehen würde, die Datenelemente nicht einzuschränken, wenn es hilft, können Sie freilich verlangen, dass die "Daten" -Elemente alle von einer gemeinsamen Basisklasse abstammen.

d.h.

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 denke, dann können Sie herausfinden, was die Datenelemente sind, indem Sie "is_base_of" verwenden.


8
2017-12-07 08:50


Ursprung


Antworten:


Hier ist eine mögliche Lösung, die verwendet join rekursiv. Grundsätzlich macht es folgendes (in Pseudo-Haskell):

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

Rekursiv ist der abgeflachte Kopf mit dem abgeflachten Schwanz verkettet.

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

Hier ist der Code (Disclaimer: Ich habe das ziemlich schnell geschrieben, also könnte der Code mit Bugs und / oder nicht-idiomatischen Methoden 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 ) );
}

8
2017-12-07 11:59