CODEWITHSUNDEEP
c++priority-queue
Peter Smit
Peter Smit

Reputation: 28716

How to implement sorting method for a c++ priority_queue with pointers

My priority queue declared as:

std::priority_queue<*MyClass> queue;

class MyClass {
    bool operator<( const MyClass* m ) const;
}

is not sorting the items in the queue.

What is wrong? I would not like to implement a different (Compare) class.

Answer summary:

The problem is, the pointer addresses are sorted. The only way to avoid this is a class that 'compares the pointers'.

Now implemented as:

std::priority_queue<*MyClass, vector<*MyClass>, MyClass::CompStr > queue;

class MyClass {
    struct CompStr {
        bool operator()(MyClass* m1, MyClass* m2);
    }
}

Upvotes: 10

Views: 25937

Answers (4)

markh44
markh44

Reputation: 6080

Not sure about the priority queue stuff because I've never used it but to do a straight sort, you can do this:

class A
{
    friend struct ComparePtrToA;
public:
    A( int v=0 ):a(v){}
private:
    int a;
};

struct ComparePtrToA
{
    bool operator()(A* a1, A* a2) {return a1->a < a2->a;}
};

#include <vector>
#include <algorithm>
int _tmain(int argc, _TCHAR* argv[])
{
    vector<A*> someAs;
    someAs.push_back(new A(1));
    someAs.push_back(new A(3));
    someAs.push_back(new A(2));
    sort( someAs.begin(), someAs.end(), ComparePtrToA() );
}

Note the memory leaks, this is only an example...

Further note: This is not intended to be an implementation of priority queue! The vector is simply an example of using the functor I created to compare two objects via their pointers. Although I'm aware of what a priority queue is and roughly how it works, I have never used the STL features that implement them.

Update: I think TimW makes some valid points. I don't know why he was downvoted so much. I think my answer can be improved as follows:

class A
{
public:
    A( int v=0 ):a(v){}
    bool operator<( const A& rhs ) { return a < rhs.a; }
private:
    int a;
};

struct ComparePtrToA
{
    bool operator()(A* a1, A* a2) {return *a1 < *a2;}
};

which is cleaner (especially if you consider having a container of values rather than pointers - no further work would be necessary).

Upvotes: 3

TimW
TimW

Reputation: 8447

Give the que the Compare functor ptr_less.

If you want the ptr_less to be compatible with the rest of the std library (binders, composers, ... ):

template<class T>
struct ptr_less
    : public binary_function<T, T, bool> {  
        bool operator()(const T& left, const T& right) const{
            return ((*left) <( *right));
        }
};

std::priority_queue<MyClass*, vector<MyClass*>, ptr_less<MyClass*> > que;

Otherwise you can get away with the simplified version:

struct ptr_less {
    template<class T>
    bool operator()(const T& left, const T& right) const {
        return ((*left) <( *right));
    }
};

std::priority_queue<MyClass*, vector<MyClass*>, ptr_less > que;

Upvotes: 12

1800 INFORMATION
1800 INFORMATION

Reputation: 135265

Since your priority_queue contains only pointer values, it will use the default comparison operator for the pointers - this will sort them by address which is obviously not what you want. If you change the priority_queue to store the class instances by value, it will use the operator you defined. Or, you will have to provide a comparison function.

Upvotes: 5

anon
anon

Reputation:

The operator <() you have provided will compare a MyClass object with a pointer to a MyClass object. But your queue contains only pointers (I think). You need a comparison function that takes two pointers as parameters.

All this is based on some suppositions - please post your actual code, using copy and paste.

Upvotes: 4

Related Questions