Still priority queues and STL ...

[Der Andere]

I posted this reaction in a thread quite far below so I fear people won't
read it. I got stuck now for quite a while and just don't know what to try
else.
Thanks,
Matthias

Are priority queues implemented in the STL in Visual Studio 6? If no, which

is the easiest way to simulate them? Multisets?
BTW: The container contains pointers to instances of a class. The ordering of the elements must follow the value of the class-instances not the value of the pointers. Furthermore, elements are inserted throughout execution

of

the program so I need a insert function which keeps the elements sorted; a sort function which sorts the whole container after every insertion is not sufficient (and surely not efficient).

See template class priority_queue in the header <queue>. You'll
have to supply an ordering predicate that takes two pointers
and returns true when one of the designated objects is ordered
before the other, but that shouldn't be hard.

The following sample program does not compile but I have no idea what to do
about it. Might be a beginner's fault. If I substitute pv(comp()) with
pv(std::less<Vertex*>()) the compiler gives no error, but I strongly suppose
less() would order the elements according to the address value of the
pointer.

#include <queue>

struct Vertex
{
int a;
};

bool comp (Vertex* v1, Vertex* v2)
{
return v1->a < v2->a;
}

int main()
{
std::priority_queue<Vertex*> pv(comp());
return 0;
}

Regards,
Matthias

the pointers in a random-access container, which it maintains
as a heap. Pushing new items on the heap and popping the highest
priority items off the heap each take log(N) percolations, where
N is the total size of the heap (queue). Hard to do better.

[David Harmon]

On Fri, 4 Jun 2004 18:09:39 +0200 in comp.lang.c++, "Der Andere"
<ma**************@gmx.net> wrote,

The following sample program does not compile but I have no idea what to do
about it. Might be a beginner's fault. If I substitute pv(comp()) with
pv(std::less<Vertex*>()) the compiler gives no error, std::priority_queue<Vertex*> pv(comp());

1. You do not want to pass to the constructor the result of calling
comp() but rather the address of the function &comp.

2. The type of the comparator is a template parameter of
priority_queue, so if you want to use something other than the default
std::less you must spell it all out.

std::priority_queue<Vertex*, std::vector<Vertex *>,
bool(*)(Vertex *, Vertex *) > pv(&comp);