对指针列表进行排序

Question

我再次发现自己在C++中执行一些非常简单的任务时失败了。有时候我希望我能从Java中的OO中了解我所知道的所有知识，因为我的问题通常从思考Java开始。我想要排序的std::list<BaseObject*>。比方说，BaseObject是：

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

我可以用一个比较结构指针列表排序，以BaseObject：

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 

直到这里，一切都是好的。不过，我介绍了一些派生类：

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

所以现在我想整理下以下规则：

1. 对于任何Child对象c和BaseObjectb，b<c
2. 比较BaseObject对象，像以前一样使用其id s。
3. 要比较Child的对象，请比较它的var s。如果它们相同，则回退到规则2.
4. GrandChild对象应回退到Child行为（规则3）。

我最初认为我可以在Comparator中做一些演员。然而，这抛弃了常量。然后，我想我可能会比较typeid，但随后一切都显得杂乱无章，甚至不正确。

我该如何执行这种操作，仍然使用list<BaseObject*>::sort？

谢谢

Answer 1

您正在寻找在做双重分派 - 正在调用取决于类型的两个对象，而不是一个虚函数。看看这篇维基百科文章，了解单挑http://en.wikipedia.org/wiki/Double_dispatch。我不得不说，每当我发现自己处于这种情况下，我会尝试改变方向:-)

我可以对你的代码做几点观察。没有什么恰恰错了，但：

• 在C++

  ，在std ::列表是不得已而为之的容器 - 你通常应该默认使用一个std：;矢量，除非特别需要一种功能，只列出规定：

• 保护的数据始终是一个糟糕的主意

Answer 2

具有对象提供一个虚拟的方法排序键，默认为ID：

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

比较现在使用的密钥（）方法，而不是直接访问ID：

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

那么孩子的类可以覆盖此行为并替换var作为排序关键字：

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

现在排序键取决于BaseObject *指向的具体实例，而不是强制转换。

编辑：哎呀，我只是了解你的问题，足以认识到这实际上并没有解决。见尼尔的答案。

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自己:)

Answer 4

我看到两种方法 - 哪一个取决于你想如何看待这个问题（和谁拥有这个想法这两个对象应该是第一个）。

如果对象本身应该知道如何相互排名，并且您确定不会用不同的规则导出更多的类，那么我可能会添加一些虚函数给基类名为'int primarySortKey（）'和'int secondarySortKey（）'。我会在比较器功能中使用它们。

如果另一方面，对象应该不知道它们应该如何排序（比较函数然后需要更多地了解对象，它们的含义和结构），我可能会找到一些方法来在比较器中获取对象的类（通过反射，或者通过引入类型的思想，并在比较器中编写一些扭曲的逻辑来确定要做什么）。

Answer 5

我只有一个问题：是吗？重要的是能够以这种特定的顺序对它们进行分类，或者你会按照类型（以任何顺序）对它们进行分类，然后通过类型内的键进行分类？

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

而且Comparator类

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

不，你不能居然把之前...的BaseObject，但您可以按类别划分。

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

唯一的问题，正如所提到的，是你不控制哪个类别是最低的。这需要一些模板魔法（例如），但这很重要吗？

Answer 6

我可能会丢失一些基本的问题，好像你基本上试图做一个2级排序：

• 月1日，基于类/对象：B型<Ç<摹

• 2日，除类似的对象，你要使用的ID/VAR场（除外孙这似乎并不具有这样的领域。）

如果是这种情况，有许多方法可以为猫蒙皮，但为什么不创建虚拟功能（例如， Key（））所有类都重写？

键（）可以返回一个的std ::对，所述第一构件的东西指示类顺序（也许一个char如“B”，“C”和“G”，方便地已经在正确的顺序），第二个成员指示类中的排名/顺序（这将是类中的id/var数据成员）。 std :: pair已经支持2级排序。

如果这是对问题的正确理解，也许像this code sample这样的东西会为你工作？