排序指针列表 [英] Sort a list of pointers

问题描述

再一次，我发现自己在C ++中的某些非常简单的任务上失败了.有时，我希望我可以从Java的OO中学到的所有知识，因为我的问题通常始于Java之类的想法.

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.

无论如何，我有一个要排序的std::list<BaseObject*>.假设BaseObject是:

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() {};
};

我可以使用比较器结构对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;
    }
};

它看起来像这样:

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. 对于任何Child对象c和BaseObject b，b<c
2. 要比较BaseObject个对象，请像以前一样使用其id个对象.
3. 要比较Child个对象，请比较其var个.如果它们相等，则退回到规则2.
4. GrandChild对象应回退到Child行为(规则3).

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).

我最初以为我可以在Comparator中进行一些转换.但是，这会消除常量性.然后我以为我可以比较typeid，但是随后一切看起来都很混乱，甚至不正确.

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.

如何仍然使用list<BaseObject*>::sort来实现这种排序?

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

谢谢

推荐答案

您正在查看进行双重调度-根据两个对象而不是一个对象的类型调用虚函数.请单看此维基百科文章 http://en.wikipedia.org/wiki/Double_dispatch .我不得不说，每当我发现自己处于这种情况时，我都会尝试改变方向:-)

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:

• 在C ++中，std :: list是不得已的容器-除非您特别需要仅列表提供的功能，否则通常应默认使用std:; vector.

• 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

这篇关于排序指针列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！