CODEWITHSUNDEEP
c++stlpriority-queuestdvector
aaazalea
aaazalea

Reputation: 7920

Make a priority queue limit its memory in C++

I am using a priority_queue<unsigned long,vector<unsigned long>,greater<unsigned long> > in C++ and I have a memory limit of 16MB. My program only needs 10MB, but as soon as it gets to 8653464 Bytes it tries to double its capacity and throws a bad_alloc.

Is there a way to stop this using my current implementation? Can a priority_queue have log(n) time still if I switch to a deque [from a vector]?

Upvotes: 2

Views: 583

Answers (3)

Puppy
Puppy

Reputation: 146930

vector offers worse complexities than deque, and deque's growth is much more predictable and controllable. If you don't need the absolutely fastest iteration on God's green earth and a couple of blue Earths too (or compatibility for a C array), then deque is the superior container for all uses.

Upvotes: 1

Leonid Volnitsky
Leonid Volnitsky

Reputation: 9144

Switching to deque is very sensible approach. It grow by fixed number, not by x2 as vector. And complexity should stay O(log N).

Upvotes: 5

John Zwinck
John Zwinck

Reputation: 249153

Sure. priority_queue is a container adaptor, and by default it is based on vector. I think the easiest way to solve your problem would be to make a subclass of vector which refuses to grow too large and doesn't double when it gets close to the limit, but rather just goes to the limit. You could also use the regular vector class but with a custom allocator instead, but that's probably more work.

Upvotes: 1

Related Questions