Refactoring a comparison operator for std::set which is using dynamic cast

Question

I inherited a piece of code which is doing something like this below. What's the cleanest way to refactor this without using dynamic_cast to check the that type are the same ?

I could mark each children type with an enum value but surely there must be something better than this ?

// Example program
#include <iostream>
#include <string>
#include <set>

class A
{
public:
    virtual ~A() {}
    virtual std::string GetField() const = 0;
};

class B: public A
{
public:
    B(const std::string& i): m_field(i) {}
    virtual std::string GetField() const { return m_field; }
    std::string m_field;
};

class C: public A
{
public:
    C(const std::string& i): m_field(i) {}
    virtual std::string GetField() const { return m_field; }
    std::string m_field;
};

class LessCmp: public std::binary_function<A*, A*, bool>
{
public:
    bool operator()(A* a1, A* a2) const {
        B* b1 = dynamic_cast<B*>(a1);
        B* b2 = dynamic_cast<B*>(a2);
        if( b1 && b2 )
            return b1->GetField() < b2->GetField();
        C* c1 = dynamic_cast<C*>(a1);
        C* c2 = dynamic_cast<C*>(a2);
        if( c1 && c2 )
            return c1->GetField() < c2->GetField();
        return true;
    }
};


int main()
{
  std::set<A*, LessCmp> myset;
  myset.insert(new B("TOTO"));
  myset.insert(new B("TITI"));
  myset.insert(new B("TOTO"));
  std::cout << myset.size() << "!\n";

  myset.insert(new C("TOTO"));
  std::cout << myset.size() << "!\n";  
}
// this outputs 2 then 3
// it basically checks the GetField() order only when the types are identical

I guess you're looking for [multiple dispatch](https://stackoverflow.com/questions/1749534/multiple-dispatch-in-c)? I guess the enum-approach you've mentioned is best, possibly there are other hacks using [`typeid`](https://stackoverflow.com/questions/9704893/c-dynamic-cast-vs-typeid-for-class-comparison) — pasbi, Jan 16 '20 at 12:09
The whole function does not conform to the [Compare requirement](https://en.cppreference.com/w/cpp/named_req/Compare) that is needed for the comparison function of set, since for `b` and `c` of different types, we have `LessCmp(b, c)` and `LessCmp(c, b)` both evaluate to `true`. — n314159, Jan 16 '20 at 12:26
What should happen for hypothetical `B1` inheriting from `B`. How `B1 b1{/*..*/};` compare to `B b{/*..*/};`? — Jarod42, Jan 16 '20 at 13:40
@Jarod42 That's a very good point! Both answers given so far (n314159's and mine – well, they're based on the same idea) would fail to handle that B1 as a B (bug or feature???). — Aconcagua, Jan 16 '20 at 14:05

score 3 · Accepted Answer · edited Jan 16 '20 at 13:08

The following does exactly the same as you tried with your casts:

return typeid(*a1) == typeid(*a2) && a1->GetField() < a2->GetField();

but would cover a possibly yet existing further derivate D of A as well.

But as n314159 denoted in the comments, we have yet some trouble:

A* a1 = new B("ad");
A* a2 = new C("ad");

Now both

LessCmp()(a1, a2)
LessCmp()(a2, a1)

Would yield false. Thus the set would interpret them equivalent! We can fix that, though:

std::type_index ti1(typeid(*a1));
std::type_index ti2(typeid(*a2));
return ti1 < ti2 || ti1 == ti2 && a1->GetField() < a2->GetField();

I have quite some doubts of that design, though.

At first, you have a memory leak: What happens to the second B("TOTO") instance after not being insert? (OK, your original code might be different, but as in question, there is the leak...).

Then what makes a B("TOTO") different from a C("TOTO"), but not from another B("TOTO")? I cannot really judge, as I don't know the concrete use case, but it leaves a bad feeling in the stomach...

A lookup would take an object as argument, so of course the lookup would also compare by type. — n314159, Jan 16 '20 at 12:32
yes I will fix the memory leak as well, this code is a bit broken. — BlueTrin, Jan 16 '20 at 13:07
@Aconcagua I absolutely agree. I would say this code should be refactored on a much more fundamental level. — n314159, Jan 16 '20 at 13:13

n314159 · Answer 2 · 2020-01-16T12:41:07.377

3

As said in my comment above, I think you invoke UB since the comparator is not irreflexive (has inputs s.t. both a<b and b<a). You can work around this by doing a lexicographic comparison on both typeid and GetField:

return std::tie(std::type_index(typeid(*a1)), a1->GetField) < std::tie(std::type_indey(typeid(*a2)), a2->GetField());

edited Jan 16 '20 at 12:41

answered Jan 16 '20 at 12:36

n314159

4,990
1
5
20

Refactoring a comparison operator for std::set which is using dynamic cast

2 Answers2