How can I use STL sort in c++ to sort some values in the class?

Question

I have a class named Graph, in this class I have a member named V, it is a vector. I have a struct named Edge, and a list of Edges. like below:

struct Edge{
 int u;
 int v;
 Edge(int u,int v){
   this->u=u;
   this->v=v;
 }
};
struct Vertex{
 int d;
 int f;
 .
 .
 .
}

class Graph{
  vector < Vertex > V;
  .
  .
  .
  int edgeCmp(Edge* x,Edge* y){
    return ( V[x->v].d < V[y->v].d )?1:0;
  }
  void someFunction(){
   list<Edge> backEdges;
   backEdges.sort(&Graph::edgeCmp);
  }
}

But it doesn't work!! may someone help me to do such a thing? I get this error:

Error 3 error C2064: term does not evaluate to a function taking 2 arguments c:\program files\microsoft visual studio 9.0\vc\include\xutility 346

It can't understand I'm calling the function which takes 2 arguments. I don't know why.

Answer 1

return (V[x->v].dv].d)?1:0;

This line has unbalanced brackets and is horrible to read (the former is a consequence of the latter I suspect). Without seeing your Vertex class it's hard to say what it is supposed to do - after fixing the brackets, maybe you should reformat for readability.

Answer 2

You can't use a member function as the comparator. A member function needs the this pointer which cannot be passed from sort.

Instead, you have to create a function object to include the extra info, like:

class Graph{
  vector < Vertex > V;

  struct EdgeComparer {
     const vector<Vertex>& V;
     EdgeComparer(const vector<Vertex>& vertices) : V(vertices) {}
     bool operator() (const Edge& a, const Edge& b) const {
        return V[a.v].d < V[b.v].d;
     }
  };

  ...

  EdgeComparer ec (V);
  backEdges.sort(ec);

Note that, since you have a list of Edge, not Edge*, the input arguments of the comparator should not be Edge*. I have changed those to const Edge&.