|
Boost : |
From: David Abrahams (dave_at_[hidden])
Date: 2002-11-25 09:15:22
"vladimir josef sykora" <vladimir.sykora_at_[hidden]> writes:
> Hello,
> Is there a way to apply a binary operation over two sequences?
> For example, I have two sequences: LHSseq and RHSseq. I want now to
> construct the return type, which is a sequence that cointains the result
> types of applying a binary operation for every member of the sequences.
> Something like:
>
> template<
> typename BOOST_MPL_AUX_VOID_SPEC_PARAM(LhsSequence)
> , typename BOOST_MPL_AUX_VOID_SPEC_PARAM(RhsSequence)
> , typename BOOST_MPL_AUX_VOID_SPEC_PARAM(BinaryOperation)
> >
> struct transform{..};
>
> usage:
> typedef transform<LHSseq,RHSseq,someBinOp>::type result_type;
>
> Guarantees complexity O(n)?
Consider applying the fold algorithm to the first sequence, using an
adapted binary operation, something like:
// ***** Untested! ********
// A dummy iterator that prevents us running off the end of the RHS sequence
template <class T>
struct prefix_iter
{
typedef T next;
};
template <class binop, class accum = mpl::push_back<mpl::_,mpl::_> >
struct zip_op
{
template <class L, class ResultIterPair>
struct apply
{
// pre-increment the rhs iterator
typedef typename ResultIterPair::second_type::next rhs_iter;
// Dereference the rhs iterator to get the rhs value
typedef typename rhs_iter::type rhs;
// x = binop(L,rhs)
typedef typename mpl::apply2<binop,L,rhs>::type x;
// Get the result of the previous step
typedef typename ResultIterPair::first_type prev_result;
// accumulate x with that result.
typedef typename mpl::apply2<accum,prev_result,x>::type result;
// Finally, the return type
typedef std::pair<rhs_iter,result> type;
};
};
typedef mpl::fold<LhsSequence, zip_op<BinaryOperation>
, std::pair<mpl::begin<RhsSequence>::type,mpl::vector<>
>::type::second_type answer;
...
Well I hope that was all instructive, but it was probably way more
complicated than neccessary. I think it would actually be far superior
to build a solution around an mpl iterator adaptor like this one:
template <class IteratorSeq> struct zip_iterator
{
typedef typename mpl::transform<
IteratorSeq,mpl::apply0<mpl::_1>
>::type type;
typedef zip_iterator<
typename mpl::transform<
IteratorSeq,mpl::next<mpl::_1>
>::type
> next;
};
and an operator adaptor like this one (don't know how to generalize
this one to N arguments yet):
template <class Op, class Seq>
struct binop_adaptor
: mpl::apply2<
Op
, typename mpl::begin<Seq>::type
, typename mpl::next<mpl::begin<Seq>::type>::type
>
{
};
How about that?
-- David Abrahams dave_at_[hidden] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk