Sort a list of pointers.

Question

Hello all,

Once again I find myself failing at some really simple task in C++. Sometimes I wish I could de-learn all I know from OO in java, since my problems usually start by thinking like Java.

Anyways, I have a std::list<BaseObject*> that I want to sort. Let's say that BaseObject is:

class BaseObject {
protected:
    int id;
public: 
    BaseObject(int i) : id(i) {};
    virtual ~BaseObject() {};
};

I can sort the list of pointer to BaseObject with a comparator struct:

struct Comparator {
    bool operator()(const BaseObject* o1, const BaseObject* o2) const {
        return o1->id < o2->id;
    }
};

And it would look like this:

std::list<BaseObject*> mylist;
mylist.push_back(new BaseObject(1));
mylist.push_back(new BaseObject(2));
// ...

mylist.sort(Comparator()); 

// intentionally omitted deletes and exception handling

Until here, everything is a-ok. However, I introduced some derived classes:

class Child : public BaseObject {
    protected:
    int var;
    public: 
    Child(int id1, int n) : BaseObject(id1), var(n) {};
    virtual ~Child() {};
};

class GrandChild : public Child {
    public:
    GrandChild(int id1, int n) : Child(id1,n) {};
    virtual ~GrandChild() {};
};

So now I would like to sort following the following rules:

1. For any Child object c and BaseObject b, b<c
2. To compare BaseObject objects, use its ids, as before.
3. To compare Child objects, compare its vars. If they are equal, fallback to rule 2.
4. GrandChild objects should fallback to the Child behavior (rule 3).

I initially thought that I could probably do some casts in Comparator. However, this casts away constness. Then I thought that probably I could compare typeids, but then everything looked messy and it is not even correct.

How could I implement this sort, still using list<BaseObject*>::sort ?

Thank you

Answer 1

You are looking at doing double dispatch - that is calling a virtual function depending on the types of two objects rather than one. Take a look at this wikipedia article for a heads-up http://en.wikipedia.org/wiki/Double_dispatch. I have to say that whenever I find myself in this situation, I try to change direction :-)

And can I make a couple of observations about your code. There is nothing precisely wrong with it but:

• in C++, the std::list is the container of last resort - you should normally default to using a std:;vector, unless you specifically need a feature that only list provides:

• protected data is always a bad idea

Answer 2

Have the object provide the sort key in a virtual method, defaulting to the id:

class BaseObject {
protected:
    int id;
public: 
    BaseObject(int i) : id(i) {};
    virtual ~BaseObject() {};
    virtual int key() const { return id; }
};

The comparator now uses the key() method instead of directly accessing the id:

struct Comparator {
    bool operator()(const BaseObject* o1, const BaseObject* o2) const {
        return o1->key() < o2->key();
    }
};

Then the Child class can override this behaviour and substitute var as sort key:

class Child : public BaseObject {
protected:
    int var;
public: 
    Child(int id1, int n) : BaseObject(id1), var(n) {};
    virtual ~Child() {};
    int key() const { return var; }
};

Now the sort key depends on the concrete instance that the BaseObject* point to, without casts.

EDIT: Oops, I just understood your problem well enough to realize that this doesn't actually solve. See Neil's answer.

Answer 3

if (typeid(o1) == typeid(Child) && typeid(o2) == typeid(BaseObject))
   return true;
if (typeid(o2) == typeid(Child) && typeid(o1) == typeid(BaseObject))
   return false;
if (typeid(o1) == typeid(BaseObject) && typeid(o2) == typeid(BaseObject))
   return o1-> id < o2->id;

continute yourself :)

Answer 4

I see two approaches - Which one depends on how you want to think about the issue ( and who owns the idea of which of two objects should be first).

If the objects themselves should have an idea of how to rank with each other, and you are pretty sure that you are not going to be deriving more classes with different rules, I would probably add a couple of virtual functions to the base class named 'int primarySortKey()' and 'int secondarySortKey()'. I would use these in the comparator function.

If on the other hand the objects should not have an idea of how they should be sorted ( and the comparator function then needs to know a lot more about the objects, their meaning and structure) I would probably find some way to get the class of the object in the comparator ( either through reflection, or by introducing the idea of a type' and write some twisted logic in the comparator to figure out what to do.

Answer 5

I only have one question: is it important to be able to sort them in this particular order, or would you be fine with sorting them by type (in any order) and then by key within the type ?

class BaseObject
{
public:
  static void* Category() { return typeid(BaseObject).name(); }
  virtual void* category() const { return Category(); }
  virtual int key() const { return mId; }

private:
  int mId; // would prefer a stronger type than int...
};

bool operator<(const BaseObject& lhs, const BaseObject& rhs)
{
  return lhs.category() <  rhs.category()
     || (lhs.category() == rhs.category() && lhs.key() < rhs.key());
}

class ChildObject: public BaseObject
{
public:
  static void* Category() { return typeid(ChildObject).name(); }
  virtual void* category() const { return Category(); }
  virtual int key() const { return mId; }
private:
  int mVar;
};

class GrandChildObject: public ChildObject
{
};

And the Comparator class

struct Comparator
{
  bool operator<(const BaseObject* lhs, const BaseObject* rhs) const
  {
    // We would not want to dereference a null pointer by mistake now would we ?
    // Let's consider than a null pointer is < to a real object then :)
    return lhs ? ( rhs ? *lhs < *rhs : false ) : ( rhs ? true : false );
  }
};

No you can't actually put the BaseObject before... but you can partition by category.

class HasCategory: public std::unary_function<const BaseObject*,bool>
{
public:
  explicit HasCategory(void* c): mCategory(c) {}
  bool operator()(const BaseObject* b) const { return b.category() == mCategory;}
private:
  void* mCategory;
};

int main(int argc, char* argv[])
{
  std::vector<const BaseObject*> vec = /* */;

  std::vector<const BaseObject*>::iterator it =
    std::partition(vec.begin(), vec.end(), HasCategory(ChildObject::Category()));

  // Now
  // [ vec.begin(), it [ contains only object of category ChildObject::Category()
  // [ it, vec.end() [ contains the others (whatever)
}

The only issue, as mentionned, is that you do not control which category will be the lowest. That would require some template magic (for example) but is it that important ?

Answer 6

I might be missing something basic in the question, it seems like you're basically trying to do a 2-level sort:

• 1st, based on class / object type: B < C < G

• 2nd, amongst similar objects, you want to use the id / var field (except for GrandChild, which doesn't seem to have such a field.)

If that's the case, there are many ways to skin the cat, but why not create a virtual function (e.g. Key()) that all classes override?

Key() could return a std::pair, the first member is something indicating the class order (maybe a char such as 'b', 'c' and 'g', conveniently already in the right order), the second member indicating the rank/order within the class (this would be the id/var data member within the class). std::pair already supports the 2-level sort.

If that's a correct understanding of the problem, maybe something like this code sample would work for you?