Sort a list of pointers

Question

Once again, I find myself unsuccessful in some really simple C ++ task. Sometimes I would like to know everything that I know from OO in java, since my problems usually start with thinking like Java.

Anyway, I have std::list<BaseObject*> that I want to sort. Say BaseObject :

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

I can sort the list of pointers to BaseObject with a comparator structure:

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

And it will 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 

So far, everything is in order. 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 the following rules:

• For any Child c object and BaseObject b , b<c
• To compare BaseObject , use its id s, as before.
• To compare Child objects, compare it to var s. If they are equal, return to rule 2.
• GrandChild objects must depart from Child behavior (rule 3).

At first I thought that maybe I could make some throws in Comparator . However, this discards constancy. Then I thought that maybe I could compare typeid s, but then everything looked messy, and that wasn't even right.

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

thanks

Answer 1

You are looking at double dispatch - this is a call to a virtual function depending on the type of two objects, not one. Take a look at this wikipedia article for the head-up http://en.wikipedia.org/wiki/Double_dispatch . I have to say that whenever I am in this situation, I try to change direction :-)

And I can make a couple of comments about your code. There is nothing wrong with this, but:

• in C ++, std :: list is the container of last resort - usually you should use the standard vector std :; if you don’t need a specific function that provides only a list:

• secure data is always bad ideas

Answer 2

I could be missing something basic in the question, it looks like you are basically trying to make a 2-level view:

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

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

If in this case there are many ways to throw off a cat, but why not create a virtual function (for example, Key () ), which all classes redefine?

Key () can return std :: pair , the first member is something that indicates the order of the class (perhaps char, for example, 'b', 'c' and 'g', is convenient in the correct order), the second element indicates rank / order inside the class (this will be the id / var data element in the class). std :: pair already supports two-level sorting.

If this is the correct understanding of the problem, maybe something like this code example will work for you?

Answer 3

Provide the object with a sort key in a virtual method, by default id:

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

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

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

Then, the Child class can override this behavior and replace var as the 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 specific instance to which the BaseObject * object points, without translation.

EDIT: Oh, I just understood your problem well enough to realize that it really doesn't solve it. See Neil's Answer.

Answer 4

 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; 

continue :)

Answer 5

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

If the objects themselves must have an idea of ​​how to rank with each other, and you are sure that you are not going to display more classes with different rules, I will probably add a couple of virtual functions to the base class called 'int primarySortKey ()' and ' int secondarySortKey () '. I would use them as a comparator function.

If, on the other hand, the objects should not have an idea of ​​how to sort them (and then the comparator function should know much more about the objects, their value and structure), I will probably find a way to get the class of the object in the comparator (or by reflection, or by introducing an idea like, "and write some twisted logic in the comparator to figure out what to do.

Answer 6

I have only one question: is it important to be able to sort them in this particular order, or would it be nice to sort them by type (in any order) and then by key inside 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 consider than a null pointer is < to a real object then :) return lhs ? ( rhs ? *lhs < *rhs : false ) : ( rhs ? true : false ); } }; 

No, you cannot actually put BaseObject before ... but you can categorize it.

 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 problem that was mentioned is that you do not control which category will be the lowest. This will require some template magic (for example), but is it important?