如何预分配（保留）priority_queue ？

Question

如何使用std::priority_queue类型的容器预先分配std::vector？

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

不编译，因为底层向量是受保护的成员。是否可以使用priority_queue的构造函数将其包装在预先保留的向量周围？

Answer 1

是的，那里有一个constructor。你还必须指定一个比较器，这有点单调乏味：

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));

您也可以使用evil shenanigans访问受保护的成员，但我不推荐它。

Answer 2

另一种解决方案可能是使您自己的类派生自std :: priority_queue，例如：

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

然后，在代码中，以这种方式创建一个MyPQueue对象：

MyPQueue mpq(1024);

哪个对象可以追溯到需要的基类。

std::priority_queue<unsigned char, std::vector<unsigned char>>& pq = mpq;

Answer 3

通常使用C++11，您可以编写如下的make_reserved函数。

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

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

int main()
{
  using Q = std::priority_queue<int, std::vector<int>>;
  auto q = Q(std::less<int>(), make_reserved<int>(100));
  std::cout << q.size() << std::endl;
}