开发者

How to sort a Vector of type <class*>? [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

C++ how to sort vector<class *> with operator <

Hello everyone!

Please i am trying to sort a vector of type "class" based on one of its data members. As follows:

The Header File: (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

The Implementation File: (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 si开发者_Python百科ze)
{
    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();
}

Now in the above code, after creating several nodes and edges, i need to sort the edges of this graph based on their weight. I am studying a way to implement Kruskal algorithm so i though of sorting the edges first based on their weight.

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

obviously does not work! since the vector edges_List is of type "Edge". Assuming that (myGraph is an object of the class).

I was wondering if there is any good technique to do that?

Thanks in advance for your help! Any suggestions or ideas are greatly appreciated!


By default, std::sort uses using operator<, but you can also supply a comparison function object.

So:

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


Another way is usage std::set container for storing your objects. And you always will have sorted container. All you need is define operator < for stored classes.

Usage vector with push_back is not effective way in terms of time. It cause unnecessary memory rellocations.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜