Boost logo

Boost :

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.


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at