"Jaap Suter" <[EMAIL PROTECTED]> 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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
