Flatten a sequence of sequences (of sequences)
I'm using boost::fusion.
Lets say I have something like the following:
开发者_Python百科make_vector(1, make_vector('b', 3, make_vector(4, 5.5), "six"), 7, 8)
I want to produce an function f such that
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]
i.e. a flattened version of the sequence.
I don't mind if this is a view of the original sequence or an actual vector.
I don't mind a solution in C++0x if it can compile on GCC 4.5.1.
Note:
Whilst I'd prefer not to restrict the data elements, if it helps, feel free to require that the "data" elements all derive from a common base class.
i.e.
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); }
Then
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)
)
I figure then you can work out what the data elements are by using "is_base_of".
Here is one possible solution, that uses join
recursively. Basically, it does the following (in pseudo-Haskell):
flatten [] = []
flatten x = [x]
flatten (x:xs) = flatten x ++ flatten xs
Recursively, the flattened head is concatenated to the flattened tail.
This solution is very likely not the most efficient one since it constructs many views, even for single values; a better approach could be passing the resulting sequence as a parameter in recursive calls and directly add the individual elements in it, perhaps using fold
.
Here is the code (disclaimer: I wrote this quite quickly, so the code could be filled with bugs and/or non-idiomatic ways of doing things):
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 ) );
}
精彩评论