Boost logo

Boost :

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

Sven Van Echelpoel <sven.vanechelpoel <at>> 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

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