Using priority_queue

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?

re: Using priority_queue

On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James
<jfa1@cec.NOBOTSwustl.edu> wrote:
[color=blue]
> Is there any way to use a priority_queue with pointers?[/color]

Yes
[color=blue]
> 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);?[/color]

No, you cannot overload operator for built in types. At least one of the
parameters must be a class.
[color=blue]
>
> 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?[/color]

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::priority_queue<Foo*, std::vector<Foo*>, CompareFooPtr>
MyQueue;

MyQueue a_queue;

john

re: Using priority_queue

On Fri, 16 Jul 2004 11:12:47 -0700, John Harrison wrote:
[color=blue]
> On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James[color=green]
>> (On a side note, how expensive is casting in C++? I know in Java
>> casting too often can really rape your application's performance.)[/color][/color]
[color=blue]
> 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.[/color]

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

re: Using priority_queue

On Fri, 16 Jul 2004 12:12:12 -0700, Ali Cehreli <acehreli@yahoo.com> wrote:
[color=blue]
> On Fri, 16 Jul 2004 11:12:47 -0700, John Harrison wrote:
>[color=green]
>> On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James[color=darkred]
>>> (On a side note, how expensive is casting in C++? I know in Java
>>> casting too often can really rape your application's performance.)[/color][/color]
>[color=green]
>> 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.[/color]
>
> 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[/color]

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

re: Using priority_queue

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:opsa8svlpw212331@andronicus...[color=blue]
> On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James
> <jfa1@cec.NOBOTSwustl.edu> wrote:
>
> [snip][/color]

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

re: Using priority_queue

On Fri, 16 Jul 2004 20:08:09 -0400, Aguilar, James
<jfa1@cec.NOBOTSwustl.edu> wrote:
[color=blue]
> "John Harrison" <john_andronicus@hotmail.com> wrote in message
> news:opsa8svlpw212331@andronicus...[color=green]
>> On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James
>> <jfa1@cec.NOBOTSwustl.edu> wrote:
>>
>> [snip][/color]
>
> So, last question, I think. In the example you provided, do I still
> have to
> cast away const?
>
>[/color]

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

john

re: Using priority_queue

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:opsa9qr3jt212331@andronicus...[color=blue]
> On Sat, 17 Jul 2004 02:16:06 -0400, Aguilar, James
> <jfa1@cec.NOBOTSwustl.edu> wrote:
>[color=green]
> > "John Harrison" <john_andronicus@hotmail.com> wrote in message
> > news:opsa9ks8fh212331@andronicus...[color=darkred]
> >> On Fri, 16 Jul 2004 20:08:09 -0400, Aguilar, James
> >> <jfa1@cec.NOBOTSwustl.edu> wrote:
> >>
> >> > "John Harrison" <john_andronicus@hotmail.com> wrote in message
> >> > news:opsa8svlpw212331@andronicus...
> >> >> On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James
> >> >> <jfa1@cec.NOBOTSwustl.edu> wrote:
> >> >>
> >> >> [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[/color][/color][/color]
away[color=blue][color=green][color=darkred]
> >> const? I don't see the need.
> >>
> >> john[/color]
> >
> > 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?
> >[/color]
>
> 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.[/color]

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?

re: Using priority_queue

On Sat, 17 Jul 2004 10:47:28 -0400, Aguilar, James
<jfa1@cec.NOBOTSwustl.edu> wrote:
[color=blue]
> "John Harrison" <john_andronicus@hotmail.com> wrote in message
> news:opsa9qr3jt212331@andronicus...[color=green]
>> On Sat, 17 Jul 2004 02:16:06 -0400, Aguilar, James
>> <jfa1@cec.NOBOTSwustl.edu> wrote:
>>[color=darkred]
>> > "John Harrison" <john_andronicus@hotmail.com> wrote in message
>> > news:opsa9ks8fh212331@andronicus...
>> >> On Fri, 16 Jul 2004 20:08:09 -0400, Aguilar, James
>> >> <jfa1@cec.NOBOTSwustl.edu> wrote:
>> >>
>> >> > "John Harrison" <john_andronicus@hotmail.com> wrote in message
>> >> > news:opsa8svlpw212331@andronicus...
>> >> >> On Fri, 16 Jul 2004 14:00:44 -0400, Aguilar, James
>> >> >> <jfa1@cec.NOBOTSwustl.edu> wrote:
>> >> >>
>> >> >> [snip]
>> >> >
>> >> > So, last question, I think. In the example you provided, do I[/color]
>> still[color=darkred]
>> >> > have to
>> >> > cast away const?
>> >> >
>> >> >
>> >>
>> >> Sorry I missed that. Why do you think you are going to have to cast[/color][/color]
> away[color=green][color=darkred]
>> >> 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?
>> >[/color]
>>
>> 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.[/color]
>
> 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?
>[/color]

You are confusing different levels of const. In this queue

std::priority_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::priority_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

re: Using priority_queue

"John Harrison" <john_andronicus@hotmail.com> wrote in message
news:opsbaetblz212331@andronicus...[color=blue]
>[snip][/color]

Fantastic. Thank you very much.

re: Using priority_queue

[...]
[color=blue]
> #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);[/color]

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?

[color=blue]
> B const & b1 = static_cast<B const &>(a);
>[/color]
[color=blue]
> B const & b2 = (B)a;[/color]
'(B)a' is essentially a C style cast?

Thanks for your time

re: Using priority_queue

On Sat, 17 Jul 2004 07:47:28 -0700, Aguilar, James wrote:
[color=blue]
> However, I need to delete this object when I'm done with it.[/color]
[...][color=blue]
> But, if the pointer is const,
> doesn't that mean that I can't edit what it points to?[/color]

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

re: Using priority_queue

On Sat, 17 Jul 2004 15:37:24 -0700, ma740988 wrote:
[color=blue]
> [...]
>[color=green]
>> #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);[/color]
>
> Could you shed light on how the
> abovementioned line results in a call to operator A()?[/color]

There is an explicit request for a type conversion from a 'B' to 'A
const &' and 'B::operator 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;
[color=blue]
> 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()).[/color]

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.
[color=blue]
> I need to revisit the four
> flavors of C++ casts, but for UDT's; isn't a reinterpret_cast preferred?[/color]

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.
[color=blue][color=green]
>> B const & b1 = static_cast<B const &>(a);
>>
>>
>> B const & b2 = (B)a;[/color]
> '(B)a' is essentially a C style cast?[/color]

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