Utiliser ou ne pas utiliser de nouveau pour la création d'une classe dans un autre

Question

J'ai résolu une question, l'algorithme de Dijkstra, en C++. Je l'ai implémenté en utilisant la liste d'adjacence. J'ai donc une classe pour node, une classe pour minHeap et une classe pour Graph.

class node 
{ 
    int vertex,weight; 
    node *next; 
    friend class Graph; 
    friend class minHeap; 
public: 
    node(); 
    node(int,int); 
}; 
node::node(){ 
    vertex=weight=0; 
    next=0; 
} 
node::node(int v,int wt){ 
    vertex=v; 
    weight=wt; 
    next=0; 
} 

Ai-je définir la classe minHeap de cette façon (sans fonction d'ami) et créer un objet dans la fonction getDijkSP() normalement, ce qui me permet d'utiliser l'objet que dans cette fonction?

class minHeap 
{ 
    node *heap; 
    int heapSize,capacity,*pos; 
public: 
    minHeap(int); 
    void addElement(node); 
    node extractMin(); 
    void minHeapify(int); 
    void decreaseKey(int,int); 
}; 
minHeap::minHeap(int cap){ 
    heap=new node[capacity=cap]; 
    heapSize=-1; 
    pos=new int[cap](); 
}          //eliminating other methods 

class Graph 
{ 
    node **adjList; 
    int v; 
    bool *visited; 
public: 
    Graph(int); 
    void addEdge(int,int,int); 
    void removeEdge(int,int); 
    bool existsEdge(int,int); 
    void getDijkSP(); 
}; 
Graph::Graph(int vertices){ 
    adjList=new node*[v=vertices]; 
    for(int i=0;i<v;i++) 
     adjList[i]=NULL; 
} 
void Graph::getDijkSP(){ 
    minHeap hp(v);       //here 
    hp.addElement(node(0,0)); 
    for(int i=1;i<v;i++) 
     hp.addElement(node(i,INT_MAX)); 
    while(!hp.isempty()){ 
     node temp=hp.extractMin(); 
     cout<<temp.vertex<<" "<<temp.weight<<endl; 
     for(node *current=adjList[temp.vertex];current;current=current->next) 
      hp.decreaseKey(current->vertex,current->weight+temp.weight); 
    } 
} 

(OR) Est-ce que je définir la classe minHeap avec une fonction ami, afin que je puisse créer un objet de la classe minHeap en utilisant le nouveau mot clé? (Et cela me permet de définir l'objet minHeap dans le cadre de la classe Graph, pour que je puisse l'utiliser dans toutes ses fonctions pour d'autres capacités aussi bien.)

class minHeap 
{ 
    node *heap; 
    int heapSize,capacity,*pos; 
    friend class Graph;    //say like this 
public: 
    minHeap(int); 
    void addElement(node); 
    node extractMin(); 
    void minHeapify(int); 
    void decreaseKey(int,int); 
}; 
minHeap::minHeap(int cap){ 
    heap=new node[capacity=cap](); 
    heapSize=-1; 
    pos=new int[cap](); 
} 

class Graph 
{ 
    node **adjList; 
    int v; 
    bool *visited; 
    minHeap *hp;        //and do this 
public: 
    Graph(int); 
    void addEdge(int,int,int); 
    void removeEdge(int,int); 
    bool existsEdge(int,int); 
    void getDijkSP(); 
}; 
Graph::Graph(int vertices){ 
    adjList=new node*[v=vertices]; 
    for(int i=0;i<v;i++) 
     adjList[i]=NULL; 
    hp=new minHeap(v);      //dynamic allocation 
} 
void Graph::getDijkSP(){ 
    hp->addElement(node(0,0)); 
    for(int i=1;i<v;i++) 
     hp->addElement(node(i,INT_MAX)); 
    while(!hp->isempty()){ 
     node temp=hp->extractMin(); 
     cout<<temp.vertex<<" "<<temp.weight<<endl; 
     for(node *current=adjList[temp.vertex];current;current=current->next) 
      hp->decreaseKey(current->vertex,current->weight+temp.weight); 
    } 
} 

J'ai lu this et quelques autres articles, mais veulent en particulier connaître les avantages, les inconvénients et la pertinence des deux méthodes pour des types de questions similaires.

J'ai fourni les constructeurs pour les classes pour une meilleure clarté.

Answer 1

La réponse courte serait NON. Je vous suggère de lire sur smart pointers et réécrire tout ce gâchis. En C++, il n'y a pas vraiment de raison d'utiliser l'allocation manuelle dans un projet aussi simple que cela. En outre, au lieu d'assigner 0 ou NULL à un pointeur, utilisez nullptr, qui est un symbole C++ uniquement pour les pointeurs Null contrairement aux valeurs C précédentes qui ne sont en réalité qu'un int 0, ce qui peut causer des erreurs involontaires.

Modifier en réponse à votre commentaire:

J'ai donc décidé de réécrire votre code en C++ moderne réelle au lieu de ce code C avec des classes simples. Dans l'ensemble de votre exemple, il n'y a presque pas de pointeurs ou d'allocations dynamiques nécessaires. Je ne savais pas exactement qui devrait posséder les nœuds réels, donc de l'exemple que j'ai supposé que le MinHeap devrait. De plus, je n'ai pas obtenu le point de MinHeap :: pos et Graph :: visited de ce que j'ai pu voir. Je peux expliquer une partie de ce code plus en détail, il suffit de demander lequel.

Voici le code:

class Node { 
    // Only friend class required if you insist on keeping members of Node private. 
    // If they aren't meant to change, consider declaring them as public and const. 
    template <unsigned Size> friend class Graph; 
public: 
    Node(int v, int wt) : vertex(v), weight(wt) {} 

private: 
    // Default values written in here right after declarations 
    // There is no need for a default constructor. You never call it anyway. 
    int vertex; 
    int weight; 
    Node* next = nullptr; 
}; 

// Template parameter because of internal use of std::array. 
// If the capacity shouldn't be constant, use std::vector and remove template. 
template <unsigned Capacity> 
class MinHeap { 
public: 
    // No constructor needed 
    // --------------------- 

    // One small tip: write parameter names in function declarations 
    // even if they aren't needed there for better readability of your code. 
    void addElement(Node n) { /* impl */ } 
    Node extractMin() { /* impl */ } 

    unsigned capacity() { return Capacity; } 
    bool isEmpty() { return heap.isEmpty(); } 

private: 
    // Default values written in here right after declarations 
    int heapSize = -1; 
    std::array<Node, Capacity> heap; 
}; 

// Template parameter because of internal use of std::array. 
// If the vertex count shouldn't be constant, use std::vector and remove template. 
template <unsigned Vertices> 
class Graph { 
public: 
    // No constructor needed 
    // --------------------- 

    void getDjikSP() { 
     hp.addElement({0, 0}); 
     for (unsigned i = 1; i < hp.capacity(); ++i) 
      hp.addElement({0, INT_MAX}); 

     while (!hp.isEmpty()) { 
      Node tmp = hp.extractMin(); 
      std::cout << tmp.vertex << " " << tmp.weight << std::endl; 

      for (Node* current = adjList[tmp.vertex]; current != nullptr; current = current->next) 
       hp.decreaseKey(current->vertex, current->weight + tmp.weight); 
     } 
    } 

private: 
    // Default values written in here right after declarations 
    std::array<Node*, Vertices> adjList; 
    MinHeap<Vertices> hp; 
}; 

Il y a encore beaucoup d'espace pour l'amélioration de ce code, par exemple le MinHeaP :: extractMin doit retourner peut-être Node & & si elle est retirée du tas ou const Node & s'il doit renvoyer une référence vers le haut, etc. Pour résoudre tous les problèmes et les inefficacités que cela peut encore avoir, j'aurais besoin de voir le code complet avec toutes les fonctions.