Huge Queue

[mohsaied]

Hi All,

I'm doing priority graph traversal using a loop and a priority queue. When using large test cases the queue becomes HUGE and the program terminates with a memory error bad_alloc().

What would be an alternative to the priority queue or how to manage it so that the memory doesn't explode like that?

Thanks

[helios]

std::priority_queue uses an std::vector by default. The problem with vector is that as you resize it, it tends to keep moving higher and higher up the address space until it eventually runs out and allocation fails. Maybe you could try with a list? Although I don't know what effect it'll have on performance.

[mohsaied]

Maybe you could try with a list? Although I don't know what effect it'll have on performance.

a list would hit my performance hard. But I have a question: how can a list save space over a queue?

[helios]

A list never performs reallocations to append or insert elements. A vector, on the other hand, typically allocates a new internal array that is new_capacity=k*current_capacity (where usually 1<k<=2) when you try to append an element and the capacity is full. Plus, a vector never tries to shrink the array when elements are removed.

[mohsaied]

A list never performs reallocations to append or insert elements. A vector, on the other hand, typically allocates a new internal array that is new_capacity=k*current_capacity (where usually 1<k<=2) when you try to append an element and the capacity is full. Plus, a vector never tries to shrink the array when elements are removed.

At the risk of sounding like an idiot: but how do I re-implement std::priority_queue using a list? or do I have to implement a priority queue myself from scratch?

[Albatross]

template < class T, class Container = vector<T> > class priority_queue;
I didn't include the whole template declaration, but luckily for you an std::priority_queue is a container adapter, which takes a container and adapts it for a different purpose.

If you change the second parameter of the template to something else, you can change the container it uses to that something else. As you can see here and as helios mentioned, it uses a vector by default, but you can change it to any container that supports the front(), push_back(), and pop_back() functions, including an std::list. :)

I might have recommended an std::deque.

-Albatross

[mohsaied]

template < class T, class Container = vector<T> > class priority_queue;
I didn't include the whole template declaration, but luckily for you an std::priority_queue is a container adapter, which takes a container and adapts it for a different purpose.

If you change the second parameter of the template to something else, you can change the container it uses to that something else. As you can see here and as helios mentioned, it uses a vector by default, but you can change it to any container that supports the front(), push_back(), and pop_back() functions, including an std::list. :)

Awesome, thanks Albatross!

so to instantiate a priority queue using a list and for an object called node, what will it look like?

this one gives a bizarre error:

priority_queue<Node, list<Node> > q;

[Albatross]

Something along the lines of:
std::priority_queue< node,std::list<node> >

Do you have the < operator defined for your class? If not, you may need to either implement it or write a function that takes two parameters and give it to the template like so:
std::priority_queue< node,std::list<node>,comparison_function >

The last time I checked, anyway.

-Albatross

[mohsaied]

I guess list isnt supperted because the queue needs a direct access data structure.

so I just used a deque: although it didnt make much difference to my problem either.

ow I'm reweriting the implementation using recursion instead :D