priority queue
Rex Zhang
I have a question with priority queue, here are some code:
======================================
//File: tpriorityqueue.cpp
#include <stdlib.h>
#include <time.h>
#include <queue>
#include <vector>
#include <iostream>
struct TestData
{
TestData(int p = 0, int s = 0): priority(p), sequence(s){}
int priority;
int sequence;
};
class HighPriority
{
public:
bool operator()(TestData* left, TestData* right)
{
return (left->priority < right->priority);
}
};
int
main(int, char**)
{
srand(time(0));
std::priority_queue<TestData*, vector<TestData*>, HighPriority> testQueue;
std::cout << "Test Case 1:\n";
for (unsigned int loopInt = 0; loopInt < 10; loopInt++)
{
testQueue.push(new TestData(rand() % 10, loopInt));
}
while ( !testQueue.empty())
{
std::cout << "Priority: " << testQueue.top()->priority;
std::cout << " Sequence: " << testQueue.top()->sequence;
std::cout << endl;
testQueue.pop();
}
std::cout << "Test Case 2:\n";
for (unsigned int loopInt = 0; loopInt < 10; loopInt++)
{
testQueue.push(new TestData(3, loopInt));
}
while ( !testQueue.empty())
{
std::cout << "Priority: " << testQueue.top()->priority;
std::cout << " Sequence: " << testQueue.top()->sequence;
std::cout << endl;
testQueue.pop();
}
}
==================================
The output like this:
==================================
Test Case 1:
Priority: 9 Sequence: 2
Priority: 8 Sequence: 9
Priority: 6 Sequence: 7
Priority: 6 Sequence: 8
Priority: 5 Sequence: 0
Priority: 5 Sequence: 5
Priority: 5 Sequence: 1
Priority: 4 Sequence: 3
Priority: 1 Sequence: 4
Priority: 1 Sequence: 6
Test Case 2:
Priority: 3 Sequence: 0
Priority: 3 Sequence: 2
Priority: 3 Sequence: 6
Priority: 3 Sequence: 9
Priority: 3 Sequence: 8
Priority: 3 Sequence: 5
Priority: 3 Sequence: 7
Priority: 3 Sequence: 4
Priority: 3 Sequence: 1
Priority: 3 Sequence: 3
====================================
My understanding about priority queue is
* The element with highest priority should be popped out first.
* For elements with same priority, they should be popped out chronologically.
According to the output, the first rule is OK. But how about second rule?
Thanks,
Rex Zhang
John Harrison
"Rex Zhang" <qi...@zhang.net> wrote in message
news:e5622a7e.01071...@posting.google.com...
> Hi, everyone:
>
> I have a question with priority queue, here are some code:
>
[code snipped]
> My understanding about priority queue is
> * The element with highest priority should be popped out first.
> * For elements with same priority, they should be popped out
chronologically.
> According to the output, the first rule is OK. But how about second
rule?
>
> Thanks,
> Rex Zhang
I've never heard of the second rule and the standard doesn't seem to
mention it, where are you getting your information?
john
Nithyanandham
John Harrison wrote:
> > I have a question with priority queue, here are some code:
> > My understanding about priority queue is
> > * The element with highest priority should be popped out first.
> > * For elements with same priority, they should be popped out
> chronologically.
> > According to the output, the first rule is OK. But how about second
> rule?
>
> I've never heard of the second rule and the standard doesn't seem to
> mention it, where are you getting your information?
It seems that he is not the only person which had the same idea. You
don't believe it, if i say that Bjarne also had the same . Actually in
4-th printing , bjarne said that 'Elements with equal priority come to
the head of the queue in the order in which they were inserted. That is,
for elements of equal priority, a priority_queue is simply a queue.'
But then there was an errata regarding that mistake. The corrected one
was 'The order in which elements with equal priority come to the head of
the queue is not defined.'
Check out : http://www.research.att.com/~bs/3rd_printing5.html for
conformation.
--
Nithyanand.
elizun...@gmail.com
the .h file is
///////////////////////////////////////////////////////////////////////////
#ifndef DUTY_H
#define DUTY_H
class duty
{
public:
duty();
virtual ~duty();
double costo_reducido;
double costo_real;
unsigned id;
bool operator ==( const duty &d2) ;
bool operator <( const duty &d2) ;
bool operator >( const duty &d2) ;
};
#endif //
////////////////////////////////////////////////////////////////////////////
the .cpp file is
//////////////////////////////////////////////////////////////////////////
#include "duty.h"
duty::duty()
{
id=0.1;
costo_reducido=0;
costo_real=0;
}
duty::~duty()
{
//dtor
}
bool duty::operator == (const duty &d1)
{
return this->costo_reducido == d1.costo_reducido;
}
bool duty::operator < (const duty &d1)
{
return this->costo_reducido < d1.costo_reducido;
}
bool duty::operator > (const duty &d1)
{
return this->costo_reducido > d1.costo_reducido;
}
////////////////////////////////////////////////////////////////////
and the main.cpp file is
#include <iostream>
#include <queue>
#include "duty.h"
using namespace std;
int main()
{
priority_queue <duty> my;
duty a;
a.costo_real=4;
a.costo_reducido=10;
a.id=0;
duty b;
b.costo_real=5;
b.costo_reducido=8;
b.id=1;
duty c;
c.costo_real=6;
c.costo_reducido=100;
c.id=2;
duty d;
d.costo_real=7;
d.costo_reducido=9;
d.id=3;
my.push(a);
my.push(b);
my.push(c);
my.push(d);
//ordena de mayor a menor
while (!my.empty())
{
duty o;
o=my.top();
my.pop();
std::cout << ' ' << o.id<<endl;
}
return 0;
}
I dont know what i am doing bad. Can anyone help me??
Barry Schwarz
wrote:
>Hi, i have a problem with my priority queue i am trying to create a priority queue of a class called duty with three elements but it produces an error. the sentence is :
>the .h file is
>///////////////////////////////////////////////////////////////////////////
>#ifndef DUTY_H
>#define DUTY_H
>
>
>class duty
>{
> public:
> duty();
> virtual ~duty();
>
>double costo_reducido;
>double costo_real;
>unsigned id;
> bool operator ==( const duty &d2) ;
> bool operator <( const duty &d2) ;
> bool operator >( const duty &d2) ;
>};
>duty::duty()
>{
> id=0.1;
Since id is an unsigned int, why are you assigning it a double?
> costo_reducido=0;
> costo_real=0;
>}
Here is a hint: none of the overloaded operators you define modify
either operand.
--
Remove del for email
elizun...@gmail.com
"instantiated from here" where i declared my priority queue.
The question is how can a create a priority queue of a class because it seems what i do doesnt work.
Vincenzo Mercuri
...
> I dont know what i am doing bad. Can anyone help me??
>
in std::priority_queue are stored as const, and you can't call
a non-const member function on a const object.
--
Vincenzo Mercuri
Mr Flibble
/Flibble
Martijn Lievaart
M4
Bix
I think that the point is that they must be const and
operators are declared non const so I guess this is one of the problem.
If you think about it the priority_queue is defined by
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
So it's going to use the operator< but because it's declared as non
const calling the operator< potentially change the ordering :)
cheers
f.
Mr Flibble
not const objects like the OP claimed.
/Flibble
Barry Schwarz
wrote:
>Yeah you are right , but the id is not the problem the message is
>
>"instantiated from here" where i declared my priority queue.
>The question is how can a create a priority queue of a class because it seems what i do doesnt work.
how to define the class properly so a priority queue can be
implemented.
You need to provide the complete error message and identify the line
of code the compiler is referring to.
Go back and look at the hint I gave you in my last message.
Vincenzo Mercuri
--
Vincenzo Mercuri
Mr Flibble
const int i = 42; /* (1) a const object */
int j = 43; /* (2) a non-const object */
const int& r = j; /* (3) a reference-to-const to a non-const object */
We are talking about case (3) here: the underlying container of
priority_queue is std::vector by default and it is not possible to store
const objects in a std::vector.
Theoretically you can use const_cast<> on the priority_queue top()
element to "remove const" and modify it and you should not run into any
problems as long as that change doesn't affect ordering.
/Flibble
Vincenzo Mercuri
that they can only be accessed by means of reference-to-const, also
because it wouldn't make much sense to "store const objects", for the
same reason why a "vector<const int>" is meaningless. In our case,
std::priority_queue uses std::less<> by default (as its Compare type),
which provides a std::less::operator() declared as:
bool operator()( const T& lhs, const T& rhs ) const;
that in turn requires T (OP's "duty"..) to define operator< which *must*
be const because it's called by a const member function. [If the OP
had to define his/her type for a container like vector, operator<
wouldn't be required to be const anymore].
>
> Theoretically you can use const_cast<> on the priority_queue top()
> element to "remove const" and modify it and you should not run into any
> problems as long as that change doesn't affect ordering.
is a reference-to-non-const via const_cast<> as much as an int is
a double via static_cast<>.
--
Vincenzo Mercuri
Mr Flibble
[snip]
> I understand that but that was not my point: a reference-to-const
> is a reference-to-non-const via const_cast<> as much as an int is
> a double via static_cast<>.
static_cast<> whilst the result of the const_cast<> returns the *same*
object.
/Flibble
blackball
Öö Tiib
> In our case,
> std::priority_queue uses std::less<> by default (as its Compare type),
> which provides a std::less::operator() declared as:
>
> bool operator()( const T& lhs, const T& rhs ) const;
>
> that in turn requires T (OP's "duty"..) to define operator< which *must*
> be const because it's called by a const member function.
you have yourself specialized it as stateful.
All comparators take the arguments that are compared as immutable (or
by value) because comparison that mutates its arguments is unexpected
and confusing even to its author.
Vincenzo Mercuri
> On Friday, 28 November 2014 04:24:09 UTC+2, Vincenzo Mercuri wrote:
> you have yourself specialized it as stateful.
>
I'm not sure why I pointed out the 'constness' of member operator().
That is actually irrelevant. I apologize, you are right.
--
Vincenzo Mercuri
Vincenzo Mercuri
>
> The double would be a different object to the int when using
> static_cast<> whilst the result of the const_cast<> returns the *same*
> object.
the same thing. Forcing something to be something else is another story.
--
Vincenzo Mercuri
Mr Flibble
non-const it is perfectly valid to cast away const from the reference.
This is totally different to your static_cast example.
/Flibble