Re: [boost] MPL: clever way to remove *all* duplicates in a(nonintegral) sequence?

From: Brian Braatz (brianb_at_[hidden])
Date: 2005-06-17 09:06:13

GOT IT! 
see below:
> -----Original Message-----
> On Behalf Of Brian Braatz
> a(nonintegral) sequence?
> 
> > "Brian Braatz" <brianb_at_[hidden]> writes:
> > >
> > > I am looking for a way to basically do this:
> > >
> > > typedef vector<int,float,float,char,int,int,int,double> types;
> > > typedef vector<int,float,char, double> expected;
> > > typedef unique_all< types, is_same<_1,_2> >::type result;
> > >
> > > BOOST_MPL_ASSERT(( equal< result,expected > ));
> > >
> > >
> > > (note the examples I am using use integral types, in my situation
I
> am
> > > not using integral types)
> > >
> >
> [David Abrahams Writes:]
> > If you don't need to preserve order, just stick them in an
> > mpl::set<>.  In fact, you might be able to use a set<> to begin with
> > and just skip the vector<>.
> >
> > Otherwise, I would write a little algorithm based on the
> > implementation of remove_if (which you can find nicely described in
> > the online reference manual).  Instead of passing along a predicate
at
> > each stage of the fold<>, pass along a set<> that accumulates the
> > elements you've already seen.  When the next element is already in
the
> > set<>, skip it.
> >
> > Try working that out for yourself; it'll be good for you ;-)

[Brian Braatz Writes:] 
OK I finally figured this out, thanks in BIG PART to David sending me
down the right path of thinking.

I am also going to save this mail, and double back around at some point
and write this by hand. (I still a little shaky with the full bore
compile time recursion code- and (as David suggests) this would be an
excellent way to get better)

I have written a small sample and am including it in this mail. I am
doing this for the benefit of someone in the future searching the list
archives looking for a solution.

here is the working solution:

this sample takes a list of types in a sequence and removes the
duplicate types

struct A    {};
struct B    {};
struct C    {};
struct D    {};

void RemoveDupsFromSequence()
{
    // 10 elements in dups, but only 4 unique types
    typedef vector<B,D,A,B,C,B,D,B,C,C>::type dups;
    
    // copy it into a set<>, 
    // the insert<> applied to set<> will 
    // ensure the same type cannot be added twice
    typedef copy<
        dups
        , inserter< set< >, insert<_1,_2 > >
        >::type result;
    
    // Prints 10
    cout << "dups size " << mpl::size<dups>::value << endl;
    
    // Prints 4 - result is now something like set<A,B,C,D>
    // Note: actual order is unknown\indeterminate for result
    cout << "result size " << mpl::size<result>::value << endl;
}

BIG THANKS to David Abrahams :)

Brian