C++ Priority_queue底层向量容器容量调整大小

Question

我使用带有向量的priority_queue作为底层容器。但是我预计堆的大小会非常大。我知道动态矢量容量调整大小存在问题。因此，我正在寻找最初为priority_queue 中的底层向量分配足够空间的方法。有什么建议可以实现这一目标吗？

谢谢

Answer 1

stdlib 容器适配器提供了一个“后门”来访问底层容器：该容器是一个名为 c 的受保护成员。

因此，您可以从适配器继承来访问容器：

#include <queue>
#include <iostream>

template <class T>
class reservable_priority_queue: public std::priority_queue<T>
{
public:
    typedef typename std::priority_queue<T>::size_type size_type;
    reservable_priority_queue(size_type capacity = 0) { reserve(capacity); };
    void reserve(size_type capacity) { this->c.reserve(capacity); } 
    size_type capacity() const { return this->c.capacity(); } 
};

int main()
{
    reservable_priority_queue<int> q;
    q.reserve(10000);
    std::cout << q.capacity() << '\n';
}

如果您对从 stdlib 类继承感到不舒服，请使用私有继承并使用 using 使 priority_queue 的所有方法都可访问代码>声明。

Answer 2

您无法直接访问底层容器来修改容量。不过，您可以将内部使用的容器更改为 std::deque。 std::deque 容器可能比向量稍慢（不是用大 O 表示法），但增长速度要快得多，因为它不需要重新定位所有现有元素。

Answer 3

使用 reserve 函数：

std::vector<Type>::reserve(size_t size)

示例：

std::vector<int> vec;
vec.reserve(10000);
std::priority_queue<int> q (std::less<int>(), vec);

Answer 4

大卫在对阿列克谢的回答的评论中是正确的：矢量实现不太可能分配副本上保留的内容。因此，要么提供自己的容器来执行此操作，要么继承priority_queue并提供一些成员来使用底层容器。

Answer 5

正如 David 所建议的，使用 std::deque 可能是一个很好的解决方案。内存块足够小，通常允许您在队列增长时保留大部分内存。
然而，这只是一个更安全的解决方案，而不是一个安全的解决方案。

如果你不太关心效率，你可以使用 stlxxl ，它是标准模板库的实现对于超大数据集。这样，可分配的内存将是您的整个硬盘驱动器（该库还支持多个硬盘驱动器或网络驱动器）。