18

How can I preallocate a std::priority_queue with a container of type std::vector? 

std::priority_queue<unsigned char, std::vector<unsigned char>> pq;
pq.c.reserve(1024);

Does not compile because the underlying vector is a protected member. Is it possible to use the constructor of the priority_queue to wrap it around a pre-reserved vector?

Boyko Perfanov
  • 3,007
  • 18
  • 34

4 Answers4

21

Yes, there's a constructor for that. It's slightly tedious that you also have to specify a comparator:

std::vector<unsigned char> container;
container.reserve(1024);
std::priority_queue<unsigned char, std::vector<unsigned char>> pq (
    std::less<unsigned char>(), std::move(container));

You can also use evil shenanigans to access the protected member, but I wouldn't recommend it.

Community
  • 1
  • 1
Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • Doesn't work for `vector> container2; container2.reserve(1024); priority_queue, vector>> minheap (greater>(), move(container2));`? – Hu Xixi Apr 02 '20 at 07:56
  • @HuXixi you have to specify the comparator type in the template arguments: `vector> container2; container2.reserve(1024); priority_queue, vector>, greater>> minheap (greater>(), move(container2));` – neckutrek May 09 '21 at 10:49
6

Another solution might be to make your own class derived from std::priority_queue, such as:

class MyPQueue : public std::priority_queue<unsigned char, std::vector<unsigned char>>
{
public:
    MyPQueue(size_t reserve_size)
    {
        this->c.reserve(reserve_size);
    }
};

then, in the code, create a MyPQueue object in this way:

MyPQueue mpq(1024);

which object can be upcasted back to the base class whenether needed.

std::priority_queue<unsigned char, std::vector<unsigned char>>& pq = mpq;
shrike
  • 4,449
  • 2
  • 22
  • 38
3

With C++14, we can write

#include <vector>
#include <queue>
#include <iostream>
#include <utility>
#include <functional>

template <class T>
auto make_reserved(const std::size_t n)
{
  std::vector<T> v;
  v.reserve(n);
  return v;
}

template <class T>
auto make_queue(const std::size_t n)
{
    return std::priority_queue<T>(std::less<T>(), make_reserved<T>(n));
}

int main()
{
  auto q = make_queue<int>(100);
  q.push(1);
  q.push(2);
  std::cout << q.size() << std::endl;
}
Lin
  • 1,547
  • 2
  • 12
  • 26
1

I don't have enough reputation to comment on Mike Seymour's post, but he ommited the third template argument of std::priority_queue :

std::vector<unsigned char> container;
container.reserve(1024);
std::priority_queue<unsigned char, std::vector<unsigned char>, std::less<unsigned char>> pq(std::less<unsigned char>(), std::move(container));

It is quite verbose for sure, but it does the work.

Arthur R.
  • 323
  • 2
  • 7