priority_queue holding pointers, how do I compare objects?

priority_queue holding pointers, how do I compare objects?

Post by p. albert » Wed, 19 Jul 2000 04:00:00



I have a class ProblemSpace with an operator<() I'd like to organise
problem spaces in a priority queue:

priority_queue<ProblemSpace> aQueue;

Now, performance is an issue and copying problem spaces takes time. So
I'd rather like to hold pointers in the queue (yes, I know this is
dangerous):

priority_queue<ProblemSpace*> aQueue;

But now the queue will sort for pointer addresses instead of using the
operator<(). So Stroustrup suggests using function object in section
17.3.3 of his book. I tried:

struct better {
  public:
  bool  operator() ( ProblemSpace* pSpace1,
                     ProblemSpace* pSpace2 ) const {
    return (*pSpace1) < (*pSpace2);
  };

Quote:};

priority_queue<ProblemSpace*,better> aQueue;

The compiler really hates that:

no type named `value_type' in `struct BranchAndBound::better'
branch-and-bound.h:115: template argument 1 is invalid
branch-and-bound.h:115: template argument 3 is invalid
branch-and-bound.h:115: warning: ANSI C++ forbids declaration `aQueue'
with no type

So I'm kind of stuck here. Any idea what I'm missing?

Thanks,
patrick!

Sent via Deja.com http://www.deja.com/
Before you buy.

 
 
 

priority_queue holding pointers, how do I compare objects?

Post by Dietmar Kueh » Wed, 19 Jul 2000 04:00:00


Hi,


Quote:> Now, performance is an issue and copying problem spaces takes time. So
> I'd rather like to hold pointers in the queue (yes, I know this is
> dangerous):

Why would that be dangerous? As long as you do not [re]move the objects
pointed to I can't see a problem with this...

Quote:> priority_queue<ProblemSpace*,better> aQueue;

The comparator type is the third template argument. The second is the
underlying container type. What you want to use is this:

  std::priority_queue<ProblemSpace*, std::vector<ProblemSpace*>,
                      better> aQueue;
--

<http://www.dietmar-kuehl.de/>

Sent via Deja.com http://www.deja.com/
Before you buy.

 
 
 

priority_queue holding pointers, how do I compare objects?

Post by p. albert » Wed, 19 Jul 2000 04:00:00




Quote:> The comparator type is the third template argument. The second is the
> underlying container type. What you want to use is this:

>   std::priority_queue<ProblemSpace*, std::vector<ProblemSpace*>,
>                       better> aQueue;

Thanks, that's working now. I became a victim of an error in the fifth
printing of Stroustrup's book. In the seventh printing he states
correctly for section 17.3.3:

typedef priority_queue< string, vector< string>, String_cmp> Pqueue;

void g(Pqueue& pq)  // pq uses String_cmp() for comparisons
{
        Pqueue pq2(String_cmp(nocase));
        pq = pq2;       // ok: pq and pq2 are of the same type, pq now
also uses String_cmp(nocase)

Quote:}

pat!

Sent via Deja.com http://www.deja.com/
Before you buy.

 
 
 

1. Question about specifying a compare function for priority_queue

I have a couple of priority queues made up of objects of a type Process
which is a class I defined.

class Process
{
public:
    int time;
    int id;
    bool operator>(const Process& RHS) const;
//rest of class definition

//I have this in a main file:

priority_queue<Process,vector<Process> ,greater<Process> > Q1;
priority_queue<Process,vector<Process>, ??????????????? > Q2;

For Q1 I want it to be sorted by Process.time, with the object with the
smallest times going to the top. So I specified greater<Process> as the
arguement and defined operator> in the Process class that compares the time:

bool Process::operator>(const Process& RHS) const
{
 return (time > RHS.time);
 That works fine. However for Q2 I want it to sort by id number with the
smallest id number going to the top. I'm having trouble figuring out how to
specify the function for the priority_queue to use to compare. I want to
create a member function in Process called sortbyid() which acts like the
operator> above but does the comparison: id > RHS.id. Would the code just
look like operator> but replace operator> with sortbyid? How would I specify
sortbypid() to the priority_queue definition above? Thanks for any help!

2. HiQ A500 or A2000?

3. comparing pointer to objects in STL containers

4. home wiring

5. Dynamic Allocation of pointer-objects with pointer-objects as members

6. NEC 4X CDROM on an Indy? Can it be done?

7. How to pass the object pointer and/or member function pointer to member object?

8. Skweezer competition at Geekzone

9. Holding a pointer to a base class in classes of another hierarchy

10. template <class Compare> void sort(Compare comp)?

11. Office 2000 Premium compared to Multilanguage Edition compared to XP?

12. Long hold time COM object problems

13. Where do I get hold of lcid parameter for MS Office COM objects