Algoritmo di ricerca di grafici generici C ++ con tipi di dati generici

Question

Algoritmo di ricerca di grafici generici C ++ con tipi di dati generici

#1 da (4 voti)

3

Sto cercando di implementare un algoritmo di ricerca di grafi generici in C ++, come parte del compito all'università, e ho riscontrato problemi durante il tentativo di implementarlo, principalmente in difficoltà con i modelli. questo è l'UML di base di ciò che sto cercando di implementare

Attualmente ho implementato il bfs, ma il nostro istruttore ci ha detto che potrebbe essere richiesto di cambiare l'algoritmo, ho creato l'interfaccia GraphAlgorithm che avrà la funzione findPath, che restituisce il vettore di GraphNodes. Il problema è che, poiché GraphNode è una classe template, devo fornire il tipo di modello all'algoritmo, ma l'algoritmo non ha nulla a che fare con il tipo di dati, funziona con i nodi e non usa i dati in alcun modo. In seguito, però, ho bisogno di accedere ai dati all'interno di GraphNodes. Ritengo che questo sia un cattivo progetto, creando un'istanza dell'algoritmo e fornendogli il tipo di nodi su cui sta cercando.

Ho provato a cercare un contenitore di dati generico sicuro per il tipo in C ++ senza utilizzare quei dannati modelli e non ho trovato nulla.

C'è qualche alternativa per questa necessità? principalmente, GraphNode mantiene l'oggetto Point (non specificato in UML sopra), ma di nuovo, preferisco rendere generico GraphNode.

In che modo tu ragazzi lo implementerai?

c++ algorithms generics templates uml

posta David 16.12.2016 - 02:08

fonte

1 risposta

Leggi altre domande sui tag c++ algorithms generics templates uml

Trova k max interi di un array - Min Heap contro selezione Algo vs Selezione Ordina Le migliori pratiche per l'utilizzo del tempo

score 4 · Accepted Answer

Non devi direttamente fornire il tipo contenuto all'algoritmo.

Ci sono alcune scelte:

Modello algoritmo

L'algoritmo di ricerca deve solo sapere che funziona su qualche tipo di nodo, che ha vicini.

template<typename GraphNode>
class GraphSearchAlgorithm { 
    findPath(GraphNode * source, GraphNode * dest); 
    //... 
}

template<typename GraphNode>
GraphSearchAlgorithm::findPath(GraphNode * source, GraphNode * dest)
{
    // stuff
    vector<GraphNode *> neighbours = current->getNeighbours();
    // more stuff
}

Al momento dell'istanza di questo modello, il compilatore deve verificare che GraphNode :: getNeighbours si adatti al sito di chiamata lì

Cancella testo

Nascondi che GraphNode ha un parametro template dietro una classe base non basata su modelli, e usa quella base nell'algoritmo

class GraphNodeBase { 
    virtual std::vector<GraphNodeBase *> getNeighbours() = 0; 
}

template<typename T>
class GraphNode : public GraphNodeBase { /*...*/ }