如何使STL的priority_queue固定大小

问题描述：

我创建一个简单的游戏，我用std::priority_queue给了命令到队（每队有一个priority_queue<command>）。如何使STL的priority_queue固定大小

每20秒一个机器人分析的情况，将命令发送到priority_queue。

我怎样才能让priority_queue固定大小的，例如，将大小设置为10？预期的效果是，当达到最大值时，如果向队列添加2个新命令，则会自动删除2个具有最低优先级的现有命令。

这是一个新的。幸运的是，我从来没有这样做过。我怀疑@DeadMG有唯一明显的解决方案 - 你将不得不编写一些代码来做到这一点，锁定队列并迭代它:( – 2012-07-21 08:41:15

[Here]（http://stackoverflow.com/a/3034221/204847））是访问'priority_queue'的底层容器的肮脏破解（该示例使用'stack'，但原理是相同的），但可能有更好的解决方案 – 2012-07-21 11:07:47

'priority_queue'实现一个二进制排序的堆在底层容器中，它不是被设计为迭代的 - 但是顶层元素是最大的，并且在日志时间内具有“push”和“pop”的性能 – Aesthete 2012-07-21 15:39:40

答

敷在，会为你执行此操作的类。该标准本身不提供这样的功能。

答

这是偷偷摸摸的，但你应该能够覆盖的std::priority_queue功能，你需要什么。这似乎在我做的一些测试中有效：

template<typename T> 
class fixed_priority_queue : public std::priority_queue<T> 
{ 
    public: 
    fixed_priority_queue(unsigned int size) : fixed_size(size) {} 
    void push(const T& x) 
    { 
     // If we've reached capacity, find the FIRST smallest object and replace 
     // it if 'x' is larger 
     if(this->size() == fixed_size) 
     { 
     // 'c' is the container used by priority_queue and is a protected member. 
     auto beg = c.begin(); auto end = c.end(); 
     auto min = std::min_element(beg, end); 
     if(x > *min) 
     { 
      *min = x; 
      // Re-make the heap, since we may have just invalidated it. 
      std::make_heap(beg, end); 
     } 
     } 
     // Otherwise just push the new item. 
     else   
     { 
     priority_queue::push(x); 
     } 
    } 
    private: 
    fixed_priority_queue() {} // Construct with size only. 
    const unsigned int fixed_size; 
    // Prevent heap allocation 
    void * operator new (size_t); 
    void * operator new[] (size_t); 
    void operator delete (void *); 
    void operator delete[] (void*); 
};

这里发生了什么？

扩展std::priority_queue类
重写priority_queue::push()方法，用新项目互换最低项目
默认的构造函数是私有的，没有大小没有建设
堆上限制分配，STL容器没有虚拟析构函数。

要使用：

const unsigned int LIMIT = 20; 
fixed_priority_queue<int> fooQueue(LIMIT); 

// Testing. 
for(int i=0; i<40; i++) 
    fooQueue.push(rand()); 
for(int i=0; i<LIMIT; i++) 
{ 
    printf("%i\n", fooQueue.top()); 
    fooQueue.pop(); 
}

有什么不好的吗？

那么你不能安全地在堆上创建这些队列，所以大队列可能是不可能的。 20左右，正如你所提到的，无论如何都应该在堆栈上很好（取决于对象）。我可能会避免大排队，因为...
我不确定在这里的表现命中。 priority_queue在底层容器上调用make_heap（默认情况下为std :: vector）。我不确定多久调用通常是，但我们经常在队列已满时调用它。我认为它也可以在priority_queue::push()之内调用？
大概的其他东西堆，所以我欢迎读者:)

希望所有建设性的反馈和修改，这是有用的，如果没有至少有趣。

我认为你应该在这里使用私有继承 – SPMP 2016-05-10 19:39:15

你知道你的'fixed_priority_queue'不是'std :: priority_queue'？所以，使用私有继承或组合。 – Deduplicator 2017-06-14 22:22:06

答

Aryabhatta's answer of another question适用于此问题。

您使用最大堆。

假设有N元素堆（作为阵列实现的），其包含迄今所看到的N个最小的元素。

当一个元素进来时，检查最大（O（1）时间），并且如果它更大则拒绝。

以前几个评论中提到的迭代是不必要的。

如何使STL的priority_queue固定大小

相关推荐