16

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

谢谢

4

5 回答 5

26

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 类继承感到难过，请使用私有继承并priority_queue通过声明使所有可访问的方法using。

于 2010-09-08T10:53:38.783 回答
3

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

于 2010-09-08T10:58:44.983 回答
0

使用reserve功能：

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

样本：

std::vector<int> vec;
vec.reserve(10000);
std::priority_queue<int> q (std::less<int>(), vec);
于 2010-09-08T09:46:19.267 回答
0

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

于 2010-09-08T10:56:31.793 回答
0

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

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

于 2010-09-08T12:17:13.010 回答