Ordene una lista de punteros

Question

Una vez más me encuentro fallando en una tarea realmente simple en C++. A veces me gustaría poder aprender todo lo que sé de OO en Java, ya que mis problemas generalmente comienzan por pensar como Java. De todos modos, tengo un std::list<BaseObject*> que quiero ordenar. Digamos que BaseObject es:

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

puedo ordenar la lista de puntero a BaseObject con una estructura comparador:

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

Y se vería así:

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 

Hasta aquí , todo está bien. Sin embargo, introduje algunas clases derivadas:

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

Así que ahora me gustaría ordenar siguiendo las siguientes reglas:

1. Para cualquier Child objeto c y BaseObjectb, b<c
2. Para comparar BaseObject objetos , use su id s, como antes. Para comparar Child objetos, comparar var s. Si son iguales, retroceda a la regla 2.
3. GrandChild los objetos deben recurrir al comportamiento Child (regla 3).

Inicialmente pensé que probablemente podría hacer algunos moldes en Comparator. Sin embargo, esto desecha la constness. Entonces pensé que probablemente podría comparar typeid s, pero luego todo parecía desordenado y ni siquiera es correcto.

¿Cómo podría implementar este tipo, aún usando list<BaseObject*>::sort?

Gracias

Answer 1

Usted está mirando que hace el doble de despacho - que está llamando a una función virtual en función de los tipos de objetos de dos en lugar de uno. Echa un vistazo a este artículo de Wikipedia para obtener un aviso directo http://en.wikipedia.org/wiki/Double_dispatch. Tengo que decir que cada vez que me encuentro en esta situación, trato de cambiar de dirección :-)

Y puedo hacer un par de observaciones sobre su código.No hay nada, precisamente, de malo, pero:

• en C++, el std :: lista es el contenedor de último recurso - usted debe normalmente por defecto a utilizar un std:; vectorial, a menos que necesite específicamente una característica que sólo se ofrece la lista:

• datos protegidos es siempre una mala idea

Answer 2

tienen por objeto proporcionar la clave de ordenación en un método virtual, el impago a la ID:

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

El comparador ahora utiliza el método de llave() en lugar de acceder directamente a la ID:

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

Entonces la clase niño puede anular este comportamiento y sustituir var como clave de ordenación:

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

Ahora la clave de clasificación depende de la instancia concreta a la que apunta BaseObject *, sin moldes.

EDITAR: Vaya, acabo de entender su problema lo suficientemente bien como para darme cuenta de que esto en realidad no lo resuelve. Ver la respuesta de Neil.

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 mismo :)

Answer 4

veo dos enfoques - que uno depende de cómo se quiere pensar en el tema (y que es dueño de la idea de cuál de los dos objetos debe ser en primer lugar).

Si los objetos mismos deben tener una idea de cómo clasificarse entre sí, y está seguro de que no va a derivar más clases con reglas diferentes, probablemente agregaría un par de funciones virtuales a la clase base llamada 'int primarySortKey()' y 'int secondarySortKey()'. Yo los usaría en la función de comparación.

Si, por otro lado, los objetos no deberían tener una idea de cómo deben clasificarse (y la función del comparador necesita saber mucho más sobre los objetos, su significado y estructura), probablemente encuentre algún modo de obtener la clase del objeto en el comparador (ya sea mediante reflexión o introduciendo la idea de un tipo 'y escribir alguna lógica retorcida en el comparador para averiguar qué hacer.

Answer 5

Solo tengo una pregunta: ¿es importante para poder clasificarlos en este orden particular, o ¿estaría bien con ordenarlos por tipo (en cualquier orden) y luego por clave dentro del tipo?

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

Y la clase 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); 
    } 
}; 

Sin realidad no se puede poner el BaseObject antes ... pero que puede particionar por categoría.

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

El único problema, como se mencionó, es que no se controla qué categoría será la más baja. Eso requeriría un poco de magia de plantilla (por ejemplo) pero, ¿es tan importante?

Answer 6

puede ser que falte algo básico en la pregunta, parece que básicamente está tratando de hacer una especie de 2 niveles:

• primera, basada en la clase/tipo de objeto: B C < < G

• segundo, entre objetos similares, que desea utilizar el campo id/var (excepto para el nieto, que no parecen tener un campo de este tipo.)

Si ese es el caso, hay muchas maneras de despellejar al gato, pero ¿por qué no crear una función virtual (p. Key()) que todas las clases anulan?

Key() podría devolver un std :: pair, el primer miembro se ha algo que indica el orden de clase (tal vez un char tales como 'b', 'c' y 'g', convenientemente ya en el orden correcto), el segundo miembro indica el rango/orden dentro de la clase (este sería el miembro de datos id/var dentro de la clase). std :: pair ya admite el tipo de 2 niveles.

Si eso es una correcta comprensión del problema, tal vez algo como this code sample funcionaría para usted?