
Boost : 
From: David Abrahams (dave_at_[hidden])
Date: 20030323 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.boostconsulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk