c++ - 在 C++ 中使优先级队列限制其内存

Question

我priority_queue<unsigned long,vector<unsigned long>,greater<unsigned long> >在 C++ 中使用 a 并且我的内存限制为 16MB。我的程序只需要 10MB，但一旦达到 8653464 字节，它就会尝试将其容量翻倍并抛出bad_alloc.

有没有办法使用我当前的实现来阻止这种情况？priority_queue如果我切换到deque[from a vector] ，a还能有 log(n) 时间吗？

Answer 1

切换到deque是非常明智的方法。它按固定数量增长，而不是 x2 增长vector。并且复杂性应该保留O(log N)。

Answer 2

当然。 priority_queue是一个容器适配器，默认基于vector. 我认为解决您的问题的最简单方法是创建一个向量的子类，该子类拒绝变得太大并且在接近极限时不会加倍，而只是达到极限。您也可以使用常规向量类，但使用自定义分配器，但这可能需要更多工作。

Answer 3

vector提供比 更糟糕的复杂性deque，并且deque的增长更加可预测和可控。如果您不需要在上帝的绿色地球和几个蓝色地球上绝对最快的迭代（或对 C 阵列的兼容性），那么deque它是适用于所有用途的卓越容器。