Re: [boost] Re: Re: Re: Re: Boost MPL problem

From: David Abrahams (dave_at_[hidden])
Date: 2003-03-23 15:43:03

"Jaap Suter" <J.Suter_at_[hidden]> writes:

> One could implement a set that does not 'duplicate' values, but the
> following is harder because insertion order matters:
>
>     typedef mpl::set< float, int, bool > set_0;
>     typedef mpl::set< bool, int, float, > set_1;
>
>     mpl::is_equal< set_0, set_1 >::type // Mmmmm, hard.

I think a set would have to be based on something like this:

struct set_base
{
   typedef void_ type;
   template <class T> struct apply : false_ {};
};

template <class T, class B = set_base>
struct set_node : B
{
    typedef T type;
    template <class U> struct apply : B::template apply<U> {};
};

// specialization for T
template <class T, class B>
struct set_node<T,B>::apply<T> : true_ {};

Now any set

   set_node<A, set_node<B, set_node<C> > >

is a metafunction class which you can use to test membership.

   s::apply<int>::type

And set equality can be tested in O(N) by iterating the first sequence
of nodes and asking whether each one's ::type is a member of the
other one.

**Note that determining that it's O(N) is an inexact science.  It may
  be strictly speaking O(N^2) but since the process of testing set
  membership happens entirely within the compiler without causing new
  instantiations, the constant is presumably tiny and we normally
  treat that operation as O(1).

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com