samedi 20 août 2016

How to compare two set of object pointer?

Background

I'm using a std::unordered_set, I believe it is also valid for those using std::set.

The cointainer holds the pointer of a Vertex (i.e. std::unordered_set<Vertex*>)

Here's a simple Graph & Vertex data structure which keep track of its neighbour:

struct Vertex {
    std::unordered_set<Vertex*> adjacencies;
}

struct Graph {
    std::vector<Vertex> vertices;
}

Problem

I need to perform the std::set_difference.

std::unordered_set<Vertex*> special_vertices;
std::set_difference(
    vertex_set_A.begin(), vertex_set_A.end(),
    vertex_set_B.begin(), vertex_set_B.end(),
    special_vertices)

The snippet above does not work, because the set difference is performing on a pointer of an object, which is not clearly defined how these pointer are equal or not.

I have seen many simple examples which should work on int type as its comparison is pretty straight forward.

Attempt

To perform this pointer comparison, i believed I need to further defined the comparison function as mentioned in the API reference, however I failed to achieve the working solution...

bool equiv(const Vertex *&u, const Vertex *&v){
    return u == v;
}

std::set_difference(
    vertex_set_A.begin(), vertex_set_A.end(),
    vertex_set_B.begin(), vertex_set_B.end(),
    special_vertices, equiv)

Hint: (from API reference)

It is also mentioned in the API reference that the comparison function should have the following signature:

bool cmp(const Type1 &a, const Type2 &b);

Aucun commentaire:

Enregistrer un commentaire