Programando un gráfico orientado a objetos simple en C++

Question

Estoy tratando de ser un programador mejor y hacer un código más modular y organizado.

Como un ejercicio, estaba tratando de hacer una clase muy simple Graph en C++ con STL. En el siguiente código, mi objeto Node no compila because the commented line results in a reference to a reference in STL.

#include <set> 

class KeyComparable 
{ 
public: 
    int key; 
}; 

bool operator <(const KeyComparable & lhs, const KeyComparable & rhs) 
{ 
    return lhs.key < rhs.key; 
} 

class Node : public KeyComparable 
{ 
public: 
    // the following line prevents compilation 
    // std::set<Node &> adjacent; 
}; 

me gustaría almacenar los bordes en una set (por key), ya que permite la eliminación rápida de los bordes con llave. Si tuviera que almacenar list<Node*>, eso funcionaría bien, pero no permitiría la eliminación rápida por key.

Si uso std::set<Node>, los cambios realizados a través de un borde solo cambiarán la copia local (no la adyacente Node). Si uso std::set<Node*>, no creo que el operador < funcionará porque funcionará en los punteros y no en la memoria que indexan.

Consideré envolver referencias o punteros en otra clase, posiblemente mi clase KeyComparable (según la página vinculada, así es como lo maneja boost).

Como alternativa, podría almacenar std::list<Node*> y std::map<int, iterator>' of locations in the std :: list`. No estoy seguro de si los iteradores serán válidos cuando cambie la lista.

Hace mucho tiempo, todo aquí solo serían indicadores y manejaría todas las estructuras de datos manualmente. Pero realmente me gustaría dejar de programar el estilo C en todos los idiomas que uso, y de hecho convertirme en un buen programador.

¿Cuál cree que es la mejor forma para manejar este problema? Muchas gracias.

Answer 1

Como ha deducido, no puede almacenar referencias en contenedores STL porque uno de los requisitos de los elementos almacenados es que sean asignables. Es la misma razón por la que no puede almacenar matrices en contenedores STL. Tampoco puede sobrecargar operadores sin que al menos uno sea del tipo definido por el usuario, lo que hace parecer que no puede hacer comparaciones personalizadas si almacena punteros en una clase STL ...

Sin embargo, aún puede std::set utilizar con punteros si se le da un comparador set funtor personalizado:

struct NodePtrCompare { 
    bool operator()(const Node* left, const Node* right) const { 
     return left->key < right->key; 
    } 
}; 

std::set<Node*, NodePtrCompare> adjacent; 

Y usted todavía consigue el traslado rápido de key como usted desee.