priority_queue<> comparison for pointers?

Question

Hello, So I'm using the STL priority_queue<> with pointers... I don't want to use value types because it will be incredibly wasteful to create a bunch of new objects just for use in the priority queue. So... I'm trying to do this:

class Int {
public:
    Int(int val) : m_val(val) {}
    int getVal() { return m_val; }
private:
    int m_val;
}


priority_queue<Int*> myQ;

myQ.push(new Int(5));
myQ.push(new Int(6));
myQ.push(new Int(3));

Now how can I write a comparison function to get those to be ordered correctly in the Q? Or, can someone suggest an alternate strategy? I really need the priority_queue interface and would like to not use copy constructors (because of massive amounts of data). Thanks

EDIT: Int is just a placeholder/example... I know I can just use int in C/C++ lol...

Answer 1

An integer is the same size as a pointer on 32 bit systems. On 64 bit systems, a pointer will be twice as big. Therefore, it is simpler/faster/better to use regular integers.

Answer 2

One option that will surely work is to replace Int* with share_ptr<Int> and then implement operator< for share_ptr<Int>

bool operator<(const share_ptr<Int> a, const share_ptr<Int> b)
{
    return a->getVal() < b->getVal();
}

Answer 3

You can explicitly specify which comparator your queue should use.

#include <iostream>
#include <sstream>
#include <functional>
#include <vector>
#include <queue>

class Int {
public:
    Int(int val) : m_val(val) {}
    int getVal() { return m_val; }
    bool operator<(const Int &other) const { return m_val < other.m_val; }
private:
    int m_val;
};

template<typename Type, typename Compare = std::less<Type> >
struct pless : public std::binary_function<Type *, Type *, bool> {
    bool operator()(const Type *x, const Type *y) const
        { return Compare()(*x, *y); }
};

int main(int argc, char *argv[]) {
    std::priority_queue<Int*, std::vector<Int*>, pless<Int> > myQ;

    for (int i = 1; i < argc; i++) {
        std::stringstream ss(argv[i]);
        int x;
        ss >> x;
        myQ.push(new Int(x));
    }

    for (; !myQ.empty(); delete myQ.top(), myQ.pop())
        std::cout << myQ.top()->getVal() << std::endl;

    return 0;
}