如何预分配（预留）一个priority_queue<vector>？

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

另一个解决方案可能是使您自己的 class 从 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);

哪个对象可以在需要时被向上转换回基础class。

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

Answer 4

我没有足够的声誉来评论 Mike Seymour 的 post，但他省略了 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));

这确实很冗长，但确实有效。

如何预分配（预留）一个priority_queue<vector>？

How to preallocate(reserve) a priority_queue<vector>?

c++

vector

std

priority-queue

allocation