代码之家 › 专栏 › 技术社区 › YuppieNetworking

排序指针列表

pointers stl sorting c++

YuppieNetworking · 技术社区 · 16 年前

再一次,我发现自己在C++中的一些简单的任务中失败了。有时我希望我能从Java中学习OO所知道的一切,因为我的问题通常是通过像Java一样思考的。

无论如何,我有一个 std::list<BaseObject*> 我想分类的。就这么说吧 BaseObject 是:

class BaseObject {
protected:
    int id;
public: 
    BaseObject(int i) : id(i) {};
    virtual ~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() {};
};

所以现在我想按照以下规则进行排序:

对于任何 Child 对象 c 和 基本对象 b , b<c
比较 基本对象 对象,使用其 id 和以前一样。
比较 孩子 对象,比较其 var s.如果它们相等,则返回规则2。
GrandChild 对象应回退到 孩子 行为(规则3)。

我最初以为我可以做一些演员 Comparator . 然而,这却抛弃了警察。我想我可以比较一下 typeid 但是一切看起来都很混乱,甚至都不正确。

我如何实现这种类型,仍然使用 list<BaseObject*>::sort ?

谢谢你

6 回复 | 直到 16 年前

sbi 16 年前

您将看到执行双重分派-即根据两个对象而不是一个对象的类型调用虚拟函数。看看这篇维基百科的文章 http://en.wikipedia.org/wiki/Double_dispatch . 我不得不说,每当我发现自己处于这种情况时,我都试图改变方向:—)

我可以对你的代码做一些观察吗?它完全没有问题,只是:

在C++中,STD::列表是最后一个容器——通常,您应该默认使用STD:vector;除非您特别需要只列出列表的特性:
受保护的数据总是个坏主意

Dan 16 年前

我可能在这个问题上遗漏了一些基本的东西,看起来你基本上是在尝试做一个2级分类:

第一,基于类/对象类型:B<C<G
第二,在类似的对象中,您希望使用id/var字段(孙子除外,孙子似乎没有这样的字段)。

如果是这样的话,有很多方法可以为猫剥皮,但是为什么不创建一个虚拟函数(例如 密钥() )所有类都覆盖?

密钥() 可以返回 STD::配对 ,第一个成员表示类顺序(可能是一个字符,如“b”、“c”和“g”,方便地已经按正确的顺序排列),第二个成员表示类中的排名/顺序(这将是类中的id/var数据成员)。 STD::配对 已经支持2级排序。

如果这是对问题的正确理解,可能是 this code sample 会为你工作吗?

digitalarbeiter 16 年前

让对象在虚拟方法中提供排序键,默认为ID:

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

比较器现在使用key()方法而不是直接访问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; }
};

现在,sort键取决于baseobject*指向的具体实例,而不是强制转换。

编辑:哎呀,我只是很好地理解了你的问题,认识到这并不能真正解决。看尼尔的答案。

Andrey 16 年前

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;

继续你自己:)

John Chenault 16 年前

我看到了两种方法——哪一种取决于你想如何思考这个问题(以及谁拥有两个对象中哪一个应该是第一个的概念)。

如果对象本身应该知道如何相互排序,并且您肯定不会用不同的规则派生更多的类,那么我可能会向名为“int primarysortkey()”和“int secondarysortkey”的基类添加一些虚拟函数。()我将在比较器函数中使用这些函数。

另一方面,如果对象不知道应该如何排序(比较器函数需要了解更多关于对象、它们的意义和结构的信息),我可能会找到在比较器中获取对象类的方法(通过reflecti或者通过引入一个类型的概念,在比较器中编写一些扭曲的逻辑,来弄清楚该怎么做。

Matthieu M. 16 年前

我只有一个问题:能够按这个特定的顺序对它们进行排序是很重要的吗,还是您可以按类型(按任何顺序)然后按类型中的键对它们进行排序?

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

唯一的问题,正如所提到的,是你不能控制哪一个类别是最低的。这需要一些模板魔术(例如),但这很重要吗?