Using priority_queue

[Aguilar, James]

Is there any way to use a priority_queue with pointers? The reason why I
ask is that I want a data structure that contains pointers to objects, not
copies of objects. Also, I want them to be sorted by priority. On the same
note, then, is there a way to write an operator:

bool operator <(Foo* foo1, Foo* foo2);?

Inside the operator, the pointers would be dereferenced then compared. Is
it not possible to do this? If not, my solution would be to simply
dereference any pointers I had before comparing them. I also want to not
have to cast away const every time I pop something from my priority queue.
(On a side note, how expensive is casting in C++? I know in Java casting
too often can really rape your application's performance.) If I want
functionality like this, am I going to be required to make my own data
structure?

 

[John Harrison]

Is there any way to use a priority_queue with pointers?
Yes

The reason why I
ask is that I want a data structure that contains pointers to objects,
not
copies of objects. Also, I want them to be sorted by priority. On the
same
note, then, is there a way to write an operator:

bool operator <(Foo* foo1, Foo* foo2);?

No, you cannot overload operator for built in types. At least one of the
parameters must be a class.

Inside the operator, the pointers would be dereferenced then compared.
Is
it not possible to do this? If not, my solution would be to simply
dereference any pointers I had before comparing them. I also want to not
have to cast away const every time I pop something from my priority
queue.
(On a side note, how expensive is casting in C++? I know in Java casting
too often can really rape your application's performance.) If I want
functionality like this, am I going to be required to make my own data
structure?

Apart from dynamic_cast casting is very efficient in C++, most of the time
its a no-op, but even if the compiler has to apply some offset that is
worked out at compile time. I guess dynamic_cast is similar to Java, in
any case its a runtime computation.

Some priority_queue code (not tested, just to give you the idea)

#include <queue>
#include <functional>

struct CompareFooPtr : public std::binary_function<Foo*, Foo*, bool>
{
bool operator()(Foo* x, Foo* y) const
{
return *x < *y;
}
};

typedef std:riority_queue<Foo*, std::vector<Foo*>, CompareFooPtr>
MyQueue;

MyQueue a_queue;

john

 

[Ali Cehreli]

Apart from dynamic_cast casting is very efficient in C++, most of the
time its a no-op, but even if the compiler has to apply some offset that
is worked out at compile time.

Some casts do require code to be executed in order to complete the
conversion. The following program has three casts. It makes three
calls to three constructors for the conversions. (Compiled with the
infamous g++ 2.96.)

#include <iostream>

class A
{
public:
A() { std::cout << "A\n"; }

void foo() const {}
};

class B
{
public:

B() { std::cout << "B default\n"; }
B(A const &) { std::cout << "B(A)\n"; }

operator A() const
{
return A();
}

void foo() const {}
};

int main()
{
B b0;
A const & a = static_cast<A const &>(b0);

B const & b1 = static_cast<B const &>(a);

B const & b2 = (B)a;
}

Ali

 

[John Harrison]

Some casts do require code to be executed in order to complete the
conversion. The following program has three casts. It makes three
calls to three constructors for the conversions. (Compiled with the
infamous g++ 2.96.)

#include <iostream>

class A
{
public:
A() { std::cout << "A\n"; }

void foo() const {}
};

class B
{
public:

B() { std::cout << "B default\n"; }
B(A const &) { std::cout << "B(A)\n"; }
operator A() const
{
return A();
}

void foo() const {}
};

int main()
{
B b0;
A const & a = static_cast<A const &>(b0);
B const & b1 = static_cast<B const &>(a);

B const & b2 = (B)a;
}

Ali

OK good point. And as well there are casts from double to int etc. etc.
which also cause some code to be executed.

I was actually thinking only of casts from a pointer to one type to a
pointer to another releated type since that was the most similar to what
happens in Java, but I should have made that clear.

john

 

[Aguilar, James]

On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James

[snip]

So, last question, I think. In the example you provided, do I still have to
cast away const?

 

[John Harrison]

On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James

[snip]

So, last question, I think. In the example you provided, do I still
have to
cast away const?

Sorry I missed that. Why do you think you are going to have to cast away
const? I don't see the need.

john

 

[Aguilar, James]

On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James

[snip]

So, last question, I think. In the example you provided, do I still
have to
cast away const?

Sorry I missed that. Why do you think you are going to have to cast away
const? I don't see the need.

john

Because after I get the object and run its activate method, I want to delete
it. But, I might be confused. What would be considered const, the pointer,
or the thing it was pointing to? How can I tell?

 

[John Harrison]

On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James

[snip]

So, last question, I think. In the example you provided, do I still
have to
cast away const?

Sorry I missed that. Why do you think you are going to have to cast away
const? I don't see the need.

john

Because after I get the object and run its activate method, I want to
delete
it. But, I might be confused. What would be considered const, the
pointer,
or the thing it was pointing to? How can I tell?

Well in the code I wrote nothing is const, so you shouldn't have any
problem deleting pointers extracted from the queue.

I still don't really see why you think const is an issue at all.

john

 

[Aguilar, James]

On Fri, 16 Jul 2004 20:08:09 -0400, Aguilar, James

On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James

[snip]

So, last question, I think. In the example you provided, do I still
have to
cast away const?



Sorry I missed that. Why do you think you are going to have to cast away
const? I don't see the need.

john

Because after I get the object and run its activate method, I want to
delete
it. But, I might be confused. What would be considered const, the
pointer,
or the thing it was pointing to? How can I tell?

Well in the code I wrote nothing is const, so you shouldn't have any
problem deleting pointers extracted from the queue.

I still don't really see why you think const is an issue at all.

Earlier, when I was passing in objects, I was using this to get them out of
the queue:

Event* retEvnt = &(evntQ->top());
evntQ->pop();
return retEvnt;

However, it kept giving me errors to the effect of not being able to convert
from const Event to Event*. Hence, I assumed that the method top() returned
const T where T is the class in the queue. Looking at the queue header
confirms this:

/**
* Returns a read-only (constant) reference to the data at the first
* element of the %queue.
*/
const_reference
top() const { return c.front(); }

However, I need to delete this object when I'm done with it. I guess this
is not an issue since the object in the data structure is not the same as
the original object anyway. But, if the pointer is const, doesn't that mean
that I can't edit what it points to?

 

[John Harrison]

On Fri, 16 Jul 2004 20:08:09 -0400, Aguilar, James

On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James

[snip]

So, last question, I think. In the example you provided, do I still
have to
cast away const?



Sorry I missed that. Why do you think you are going to have to cast away
const? I don't see the need.

john

Because after I get the object and run its activate method, I want to
delete
it. But, I might be confused. What would be considered const, the
pointer,
or the thing it was pointing to? How can I tell?

Well in the code I wrote nothing is const, so you shouldn't have any
problem deleting pointers extracted from the queue.

I still don't really see why you think const is an issue at all.

Earlier, when I was passing in objects, I was using this to get them out
of
the queue:

Event* retEvnt = &(evntQ->top());
evntQ->pop();
return retEvnt;

However, it kept giving me errors to the effect of not being able to
convert
from const Event to Event*. Hence, I assumed that the method top()
returned
const T where T is the class in the queue. Looking at the queue header
confirms this:

/**
* Returns a read-only (constant) reference to the data at the first
* element of the %queue.
*/
const_reference
top() const { return c.front(); }

However, I need to delete this object when I'm done with it. I guess
this
is not an issue since the object in the data structure is not the same as
the original object anyway. But, if the pointer is const, doesn't that
mean
that I can't edit what it points to?

You are confusing different levels of const. In this queue

std:riority_queue<Foo>

it is true that top() return Foo const& (or, same thing, const Foo&) and
therefore you cannot use top() to modify the Foo object in the queue. But
in this queue

std:riority_queue<Foo*>

top() now returns Foo* const&. That is a const reference to the pointer,
but the Foo object itself is not const. In other words since your queue is
now storing pointers you cannot use top() to modify the pointer itself but
there is nothing stopping you modifying what the pointer is pointing at
(or deleting the pointer).

Basically the elements of a priority_queue are non modifyable while they
are in the queue, but if the elements are pointers, then it is the
pointers themselves that are const, not what they are pointing to.

john

 

[Aguilar, James]

[snip]

Fantastic. Thank you very much.

 

[ma740988]

[...]

#include <iostream>

class A
{
public:
A() { std::cout << "A\n"; }

void foo() const {}
};

class B
{
public:

B() { std::cout << "B default\n"; }
B(A const &) { std::cout << "B(A)\n"; }

operator A() const
{
return A();
}

void foo() const {}
};

int main()
{
B b0;
A const & a = static_cast<A const &>(b0);

For the uninitiated, yours truly. Could you shed light on how the
abovementioned line results in a call to operator A()? I've perused
function objects in Josuttis and have dealt with them on a relatively
minor scale so I'm 'acclimated' with the concept.
I'm not grasping how the cast of b0 to an A const reference results in
the call to operator A(). (ie. A const& a = operator A()).
I need to revisit the four flavors of C++ casts, but for UDT's; isn't
a reinterpret_cast preferred?

B const & b1 = static_cast<B const &>(a);

B const & b2 = (B)a;

'(B)a' is essentially a C style cast?

Thanks for your time

 

[Ali Cehreli]

However, I need to delete this object when I'm done with it. [...]
But, if the pointer is const,
doesn't that mean that I can't edit what it points to?

If the pointer is const, you can not change *the pointer*.

Still, you can delete the object that the pointer points to:

int const * p = new int(42);
delete p;

int * const q = new int(42);
delete q;

int const * const r = new int(42);
delete r;

They all have different constness, but we can delete the objects they
point to.

Ali

 

[Ali Cehreli]

[...]

#include <iostream>

class A
{
public:
A() { std::cout << "A\n"; }

void foo() const {}
};

class B
{
public:

B() { std::cout << "B default\n"; }
B(A const &) { std::cout << "B(A)\n"; }

operator A() const
{
return A();
}

void foo() const {}
};

int main()
{
B b0;
A const & a = static_cast<A const &>(b0);

Could you shed light on how the
abovementioned line results in a call to operator A()?

There is an explicit request for a type conversion from a 'B' to 'A
const &' and 'B:perator A()' fits the bill.

Actually, the cast is not needed at all in this case. The following
produces the same result:

A const & a = b0;

I've perused
function objects in Josuttis and have dealt with them on a relatively
minor scale so I'm 'acclimated' with the concept. I'm not grasping how
the cast of b0 to an A const reference results in the call to operator
A(). (ie. A const& a = operator A()).

B defines a 'operator A()' function that is supposed to be called in
any place where a B is used as an A. It is a conversion from a B to an
A.

I need to revisit the four
flavors of C++ casts, but for UDT's; isn't a reinterpret_cast preferred?

No, reinterpret_cast is platform dependent. It is the closest thing to
a C style cast but better; because it at least performs some tests at
compile time.

For many UDT conversions, no cast is needed. When the type is know at
compile time, a static_cast would be better.

'(B)a' is essentially a C style cast?

Yes. There is a temporary B created as a result of that cast; but
don't ask me whether that temporary is an rvalue or an lvalue.

Ali