Re: [boost] [mpl] Copy of sequence into a set

From: Steven Watanabe (steven_at_[hidden])
Date: 2007-11-20 19:43:20

Sven Van Echelpoel <sven.vanechelpoel <at> telenet.be> writes:

> 
> Hi,
> 
> I have an mpl sequence of types and I want to ensure that each type
> occurs only once in that sequence (I do not control the initial
> sequence). The quickest way I could think of was copying that sequence
> into a set. Here's the utility I had in mind:
> 
> template<
>   typename T
> >
> struct as_set :
>   copy<
>     T
>   , inserter<
>       set<>
>     , insert< _1, _2 >
>     >
>   >
> {};
> 
> Using this on, say, a vector indeed produces a set with all the types
> copied from the vector, duplicates removed. However, when I use the
> resulting set in an algorithm that iterates over the elements (I need
> inherit_linearly) it no longer compiles. The compiler (VC 7.1) complains
> that next_ is not member of set<na,na,...>. It seems as if the next
> iterator of the last element isn't properly defined. This isn't a
> problem with a normally constructed set (set<int,char>). Here's a
> minimal program that demonstrates the issue:
> 
> 
> <snip>
> 
> I have been staring at this problem for quite a while now and am unable
> to figure out completely what's going wrong. Is the way I'm tackling the
> problem the right way to go or is there a simpler alternative? Am I
> doing something wrong or overlooking something obvious altogether? Any
> help would be appreciated.
> 

OK.  I've diagnosed the problem.  It's a bug in mpl::set.

What's happening is that mpl::set is using ::type for two
different purposes.  The first usage is simply a typedef for
the set itself

struct set<> {
    typedef set<> type;
};

The second usage is as a typedef for the item.

template<class T, class Base>
struct s_item : Base {
    typedef T type;
};

Let's use about the simplest possible example.
The call to insert<set<>, char>::type creates
s_item<char, set<> >.  The specialization of
mpl::next for s_iter looks like:

// boost/mpl/set/aux_/iterator.hpp line 50
template< typename Set, typename Tail > 
struct next< s_iter<Set,Tail> >
    : eval_if< 
          has_key< Set,typename Tail::next_::type >
        , identity< s_iter<Set,typename Tail::next_> >
        , next< s_iter<Set,typename Tail::next_> >
        >
{
};

This is basically testing whether the current element has
been erased and if so recursively invoking next. Note
the comparison.  It is assuming the second usage of ::type
described above.  Continuing the example I started above,
when Tail is s_item<char, set<> >, what happens?  Well, 
Tail::next_ is simply set<>.  Now we get the element at that
point, that's ::type right?  No. It is NOT ::type.  set<>::type is 
mpl::set0<>.  So mpl::next merrily proceeds to ask whether
s_item<char, set<> > (A set which only contains the type char)
contains set0<>.  Of course it doesn't, so it tries to
increment again by calling
mpl::next<s_iter<s_item<char, set<> >,set<> > >::type
There is a specialization for set0<> but not
for set<>, so the compiler then tries to increment
and end iterator normally and blows up.  Note that
while this particualar problem could be fixed by adding
a specialization of next<...>, if the base type that
you're inserting elements into is set1<> for instance
some of the elements of you're set will silently vanish.

In Christ,
Steven Watanabe