如何整理<class*>類型的向量？

Question

可能重複：
C++ how to sort vector<class *> with operator <

大家好！

請我試着根據它的一個數據成員對「class」類型的向量進行排序。如下：

頭文件

：（Undirected_Graph.h）

#ifndef UNDIRECTED_GRAPH_H 
#define UNDIRECTED_GRAPH_H 

#include <vector> 
using std::vector; 

#include <climits> 

class Edge; 

class Node 
{ 
    public: 

     Node(int);     //The constructor. 

     int id;     //For the id of the node. 
     bool visited;    //For checking visited nodes. 
     int distance; 

     vector <Edge*> adj;  //The adjacent nodes. 
}; 

class Edge 
{ 
    public: 

     Edge(Node*, Node*, int); //The constructor. 

     Node* start_Node;   //The start_Node start of the edge. 
     Node* end_Node;   //The end of the edge. 
     int w;      //The weight of the edge. 

     bool isConnected(Node* node1, Node* node2) //Checks if the nodes are connected. 
     { 
      return((node1 == this->start_Node && node2 == this->end_Node) || 
        (node1 == this->end_Node && node2 == this->start_Node)); 
     } 
}; 

class Graph 
{ 
    public: 

     Graph(int);     //The Constructor. 

     int max_Nodes;     //Maximum Number of allowed Nodes. 

     vector <Edge*> edges_List;  //For storing the edges of the graph. 
     vector <Node*> nodes_List;  //For storing the nodes of the graph. 

     void insertEdge(int, int, int); 

     int getNumNodes(); 
     int getNumEdges(); 
}; 

#endif 

實現文件：（Undirected_Graph.cpp）

#include "Undirected_Graph.h" 

Node::Node(int id_Num) 
{ 
    id = id_Num; 
    visited = 0; 
    distance = INT_MAX; 
} 

Edge::Edge(Node* a, Node* b, int weight) 
{ 
    start_Node = a; 
    end_Node = b; 
    w = weight; 
} 

Graph::Graph(int size) 
{ 
    max_Nodes = size; 

    for (int i = 1; i <= max_Nodes; ++i) 
    { 
     Node* temp = new Node(i); 

     nodes_List.push_back(temp); 
    } 
} 

void Graph::insertEdge(int x, int y, int w) 
{ 
    Node* a = nodes_List[x-1]; 
    Node* b = nodes_List[y-1]; 

    Edge* edge1 = new Edge(a, b, w); 
    Edge* edge2 = new Edge(b, a, w); 

    edges_List.push_back(edge1); 

    a->adj.push_back(edge1); 
    b->adj.push_back(edge2); 
} 

int Graph::getNumNodes() 
{ 
    return max_Nodes; 
} 

int Graph::getNumEdges() 
{ 
    return edges_List.size(); 
} 

現在，在上述代碼中，後創建幾個節點和邊，我需要根據它們的重量對此圖的邊進行排序。我正在研究一種實現Kruskal算法的方法，所以我儘管根據它們的重量對邊進行了排序。

sort (myGraph.edges_List[index].begin(), myGraph.edges_List[index].end()); 

顯然不起作用！因爲矢量edges_List的類型是「Edge」。 假設（myGraph是類的一個對象）。

我想知道是否有任何好的技術來做到這一點？

在此先感謝您的幫助！任何建議或想法非常感謝！

Answer 1

默認情況下，std::sort使用operator<，但您也可以提供比較函數對象。

所以：

bool your_comparer(const Edge * left, const Edge * right) 
{ 
    // return true if left should come before right, false otherwise 
} 

// ... 

sort (myGraph.edges_List.begin(), myGraph.edges_List.end(), your_comparer); 

Answer 2

另一種方式是用於存儲對象使用的std ::設置容器。你總是會有排序的容器。所有你需要的是爲存儲的類定義operator <。

帶有push_back的使用向量在時間上並不是有效的方式。它會導致不必要的內存重新分配。