erase() woes on std::multiset with custom Compare

[newbarker]

Hello all,

I had a container of pointers to base. They were in a std::set<Base*>.
N.B. set was preferred over vector so iterators were not invalidated
when iterating.

Now I've been asked to order some of them by their runtime type.
Pointers to derived StyleLine should appear first. I tried std::set
with a comparison object but that only allows one object of each type
to be added (even though the pointer values are distinct). So, here I
am with std::multiset<Base*>. Seems to be going ok, but if I erase an
object of a particular type, all objects of that type are removed!
That was unexpected.

Here's an stripped down working example:

#include <iostream>
#include <set>

struct Base
{
virtual ~Base() {}
};

struct StyleLine : public Base
{
};

struct Piece : public Base
{
};

struct StyleLineFirstOrderer
{
bool operator()(const Base* a,const Base* b) const
{
const type_info& typeA = typeid(*a);
const type_info& typeB = typeid(*b);
if(typeA == typeB)
return false;
else
return typeA == typeid(StyleLine) != 0;
}
};

int main()
{
typedef std::multiset<Base*,StyleLineFirstOrderer> ContainerType;
ContainerType objects;
objects.insert(new Piece());
objects.insert(new Piece());
objects.insert(new Piece());
objects.insert(new Piece());
objects.insert(new Piece());
objects.insert(new Piece());
objects.insert(new StyleLine());
objects.insert(new StyleLine());
objects.insert(new StyleLine());
objects.insert(new StyleLine());
objects.insert(new StyleLine());
objects.insert(new StyleLine());
objects.erase(new Piece());
for(ContainerType::iterator it = objects.begin(); it !=
objects.end(); ++it)
std::cout << typeid(**it).name() << std::endl;
}

As you see, I try to erase a pointer to a piece at the end and it will
remove ALL the piece objects which is not what I want. I just want
erase to work on the value of the pointer.

Can someone give me some suggestions?

Thanks,

Pete

 

[acehreli]

I had a container of pointers to base. They were in a std::set<Base*>.

Now I've been asked to order some of them by their runtime type.
Pointers to derived StyleLine should appear first. I tried std::set
with a comparison object but that only allows one object of each type
to be added (even though the pointer values are distinct).

You need to find a secondary criterion to order the objects of same
derived type.

struct StyleLine : public Base
{

};

struct Piece : public Base
{

};

struct StyleLineFirstOrderer
{
bool operator()(const Base* a,const Base* b) const
{
const type_info& typeA = typeid(*a);
const type_info& typeB = typeid(*b);
if(typeA == typeB)

Here, you still need to order the two objects. If you don't have any
members, maybe the addresses will do:

return a < b;

but that would be undefined behavior, because it is undefined to
compare the addresses of objects that are not members of the same
array. (I think equality comparison would work but not the ordering
comparison e.g. with operator<.)

You may want to cast the addresses to comparable entities first. This
may work:

return reinterpret_cast<unsigned long>(a)
< reinterpret_cast<unsigned long>(b);

Ali

 

[Jerry Coffin]

[ ... ]

Here, you still need to order the two objects. If you don't have any
members, maybe the addresses will do:

return a < b;

but that would be undefined behavior, because it is undefined to
compare the addresses of objects that are not members of the same
array. (I think equality comparison would work but not the ordering
comparison e.g. with operator<.)

Sort of true. A least IIRC, doing the comparison only gives unspecified
results rather than being undefined behavior. More importantly, even
though the result from using operator< to compare such addresses isn't
specified, the result from using std::less _is_, at least to some
extent. Specifically, even though there's no attempt to specify what the
ordering of unrelated objects will be, the result of such a comparison
will be repeatable and have the transitive property (e.g. if a<b and b
<c, then a<c).

 

[newbarker]

Thanks both,

The secondary comparison of addresses and reverting to a std::set will
do the trick thanks.

I certainly don't want to invoke undefined behaviour. Surely it's fine
as I'm comparing pointers to the same base?

Regards,

Pete

[ ... ]

Here, you still need to order the two objects. If you don't have any
members, maybe the addresses will do:

     return a < b;

but that would be undefined behavior, because it is undefined to
compare the addresses of objects that are not members of the same
array. (I think equality comparison would work but not the ordering
comparison e.g. with operator<.)

Sort of true. A least IIRC, doing the comparison only gives unspecified
results rather than being undefined behavior. More importantly, even
though the result from using operator< to compare such addresses isn't
specified, the result from using std::less _is_, at least to some
extent. Specifically, even though there's no attempt to specify what the
ordering of unrelated objects will be, the result of such a comparison
will be repeatable and have the transitive property (e.g. if a<b and b
<c, then a<c).

--
    Later,
    Jerry.

The universe is a figment of its own imagination.

 

[James Kanze]

The secondary comparison of addresses and reverting to a
std::set will do the trick thanks.

I certainly don't want to invoke undefined behaviour. Surely
it's fine as I'm comparing pointers to the same base?

As Jerry pointed out, it's not undefined, just unspecified. To
the point where (theoretically), given two pointers a and b, a<b
might be true one time, and false the next time you try it. In
practice, of course, there are (or at least have been) a lot of
cases where !(a < b) && !(b < a), even though a and b point to
different objects (and a != b); such an ordering will NOT work
with std::set.

As Jerry also pointed out, the standard requires std::less to
work. Use it instead.