C++ templating question regarding comparators

Question

Probably a very newb C++ question. Say I have a class, vertex, with several properties and methods. I want to stuff a bunch of vertices into a queue, and have them ordered by a special property on the vertex class (doing a basic Dijkstra graph algo for school yes).

I'm having some problems penetrating the C++ syntax however. Here is my code (vertex is not shown, but it's pretty simple).

typedef std::priority_queue<benchmark::vertex*, 
                    std::vector<benchmark::vertex*>, 
                    std::less<benchmark::vertex*> > q_type;
q_type* q = new q_type();
benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1);
v1->cost = 4;
benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1);
v2->cost = 8;
benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1);
v3->cost = 6;
benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1);
v4->cost = 10;
benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1);
v5->cost = 2;
q->push(v1);
q->push(v2);
q->push(v3);
q->push(v4);
q->push(v5);
while (!q->empty()) {
    std::cout << (*(q->top())).cost << std::endl;
    q->pop();
}

This outputs 2, 10, 6, 8, 4 on my local machine. I'm testing this on a Linux box with GCC (gcc version 4.3.3 (Ubuntu 4.3.3-5ubuntu4)). Obviously, I want it to spit the numbers out in order.

How do I make the comparator, so that it looks and compares vertex.cost, when doing comparisons?

Answer 1

replace std::less<benchmark::vertex*> with any function or functor that takes two vertex pointers as parameters and returns true iff the first parameter belongs before the second.

std::less<benchmark::vertex*> is going to compare the two pointers, so the result you have seen shows their order in memory.

Answer 2

std::less<benchmark::vertex*> compares the addresses rather than vertices

// Functor
struct VertexLess
{
   bool operator (const benchmark::vertex* left, const benchmark::vertex* right) const {
      return left->id < right->id;
   }
};

typedef std::priority_queue<benchmark::vertex*,     
                    std::vector<benchmark::vertex*>,
                    VertexLess > q_type;

Answer 3

Bonus extra-templatey version of Alexey Malistov's answer:

template <class T, class M, const M T::*member>
struct MemberGenericDereferenceLess
{
    bool operator()(const T* lhs, const T* rhs) const
    {
        return ((*lhs).*member < (*rhs).*member);
    }
};

typedef std::priority_queue<benchmark::vertex*,
                            std::vector<benchmark::vertex*>,
                            MemberGenericDereferenceLess<benchmark::vertex,
                                                         int,
                                                         &benchmark::vertex::cost> > q_type;

I had figured that you'd only need the first and third template parameters, but I couldn't get it to infer class M with a few minutes of hacking. (exercise for the readers)

The benefit of this is you can quickly change which member you sort on. Assuming your vertex looks something like...

namespace benchmark
{
    struct vertex
    {
        vertex(double a_, double b_) : a(a_), b(b_) {}

        double a;
        double b;

        int cost;
    };
}

You could have your typedef sort on a or b:

typedef std::priority_queue<benchmark::vertex*,
                            std::vector<benchmark::vertex*>,
                            MemberGenericDereferenceLess<benchmark::vertex,
                                                   double,
                                                   &benchmark::vertex::a> > q_type;

typedef std::priority_queue<benchmark::vertex*,
                            std::vector<benchmark::vertex*>,
                            MemberGenericDereferenceLess<benchmark::vertex,
                                                   double,
                                                   &benchmark::vertex::b> > q_type;

Here's a little driver program to play with:

#include <iostream>
#include <queue>
#include <vector>

namespace benchmark
{
    struct vertex
    {
        vertex(double a_, double b_) : a(a_), b(b_) {}

        double a;
        double b;

        int cost;
    };
}

template <class T, class M, const M T::*member>
struct MemberGenericDereferenceLess
{
    bool operator()(const T* lhs, const T* rhs) const
    {
        return ((*lhs).*member < (*rhs).*member);
    }
};

int main(int argc, char** argv)
{
    typedef std::priority_queue<benchmark::vertex*,
                                std::vector<benchmark::vertex*>,
                                MemberGenericDereferenceLess<benchmark::vertex,
                                                       int,
                                                       &benchmark::vertex::cost> > q_type;
    q_type q;

    benchmark::vertex* v1 = new benchmark::vertex(0.1,0.1);
    v1->cost = 4;
    benchmark::vertex* v2 = new benchmark::vertex(0.1,0.1);
    v2->cost = 8;
    benchmark::vertex* v3 = new benchmark::vertex(0.1,0.1);
    v3->cost = 6;
    benchmark::vertex* v4 = new benchmark::vertex(0.1,0.1);
    v4->cost = 10;
    benchmark::vertex* v5 = new benchmark::vertex(0.1,0.1);
    v5->cost = 2;
    q.push(v1);
    q.push(v2);
    q.push(v3);
    q.push(v4);
    q.push(v5);
    while(q.empty() == false)
    {
        std::cout << q.top()->cost << std::endl;
        q.pop();
    }

    // Clean up all of those new()s
    delete v1;
    delete v2;
    delete v3;
    delete v4;
    delete v5;

    std::cin.get();

    return 0;
}