Q: STL priority_queue with boost shared_ptr

[zl2k]

hi, all
Here is what I want to do: to wrap my self defined class in a
shared_ptr and then insert it into the priority_queue. The
priority_queue should pump the least element of the self defined class
first. To make it simple, here is the toy code.

myClass.h
------------------------------------------
#ifndef MYCLASS_H
#define MYCLASS_H

class myClass {
public:
double a;
myClass(double a) {
this->a = a;
}

bool operator<(const myClass & right) const { //the comparison is
"reversed" in order to pop smallest first
return a > right.a;
};
bool operator>(const myClass & right) const {
return a < right.a;
}
bool operator<=(const myClass & right) const {
return a >= right.a;
}
bool operator>=(const myClass & right) const {
return a <= right.a;
}
};
#endif
---------------------------------------------------//over

Foo.cpp
-------------------------------------------------
#include <vector>
#include <queue>
#include <deque>
#include <boost/shared_ptr.hpp>
#include "myClass.h"
#include <iostream>

using namespace boost;
using namespace std;

int main(){
priority_queue<shared_ptr<myClass> > pq;
shared_ptr<myClass> temp(new myClass(1));
pq.push(temp);
temp.reset(new myClass(2));
pq.push(temp);
temp.reset(new myClass(3));
pq.push(temp);
while (!pq.empty()){
temp = pq.top();
cout<<temp->a<<endl;
pq.pop();
}
}
----------------------------------------------------//over

I was expecting the priority_queue to pop 1 first and 3 last. However,
it pops 3 first and 1 last. (If I input 3,2,1 in a sequence, then the
output will be 1,2,3. So it seems that there is no sorting at all) My
real program is more complex than this and I have the reason to use the
shared_ptr. So, directly insert the numbers into the priority_queue is
not a solution. Can someone help me to fix the problem? Thanks ahead.

zl2k

 

[Alan Johnson]

hi, all
Here is what I want to do: to wrap my self defined class in a
shared_ptr and then insert it into the priority_queue. The
priority_queue should pump the least element of the self defined class
first. To make it simple, here is the toy code.

bool operator<(const myClass & right) const { //the comparison is
"reversed" in order to pop smallest first
return a > right.a;
};

Okay, look's fine.

priority_queue<shared_ptr<myClass> > pq;

Oops. You are using shared_ptr's operator<, not the one in myClass.

I was expecting the priority_queue to pop 1 first and 3 last. However,
it pops 3 first and 1 last.

You need to define a function object that does the comparison you want
when given two shared_ptr's. Example:

struct ptr_less
{
bool operator()(const shared_ptr<myClass> & lhs,
const shared_ptr<myClass> & rhs)
{
return *lhs < *rhs ;
}
} ;

Or, if you want to be a bit more reusable, you could generalize this to
any type that can be dereferenced into a type that defines operator<.

Defining your priority_queue gets considerably more fun now. The second
template parameter is the container type. By default this is vector<T>,
so unless you have a reason just stick with that:

priority_queue<shared_ptr<myClass>,vector< shared_ptr<myClass> >,
ptr_less< shared_ptr<myClass> > > pq;

You might consider some typedefs to make that more readable.

 

[Alan Johnson]

Okay, look's fine.


Oops. You are using shared_ptr's operator<, not the one in myClass.


You need to define a function object that does the comparison you want
when given two shared_ptr's. Example:

struct ptr_less
{
bool operator()(const shared_ptr<myClass> & lhs,
const shared_ptr<myClass> & rhs)
{
return *lhs < *rhs ;
}
} ;

Or, if you want to be a bit more reusable, you could generalize this to
any type that can be dereferenced into a type that defines operator<.

Defining your priority_queue gets considerably more fun now. The second
template parameter is the container type. By default this is vector<T>,
so unless you have a reason just stick with that:

priority_queue<shared_ptr<myClass>,vector< shared_ptr<myClass> >,
ptr_less< shared_ptr<myClass> > > pq;

You might consider some typedefs to make that more readable.

Er. I left out the templated version of ptr_less, but the last line
there assumes that you are using it, so here it is:

template <typename Pointer>
struct ptr_less
{
bool operator()(const Pointer & lhs,
const Pointer & rhs)
{
return *lhs < *rhs ;
}
} ;

 

[zl2k]

Er. I left out the templated version of ptr_less, but the last line
there assumes that you are using it, so here it is:

template <typename Pointer>
struct ptr_less
{
bool operator()(const Pointer & lhs,
const Pointer & rhs)
{
return *lhs < *rhs ;
}
} ;

It works great as you said, thanks Alan.

zl2k