我正在创建一个简单的游戏，用于向小队std::priority_queue发出命令 （每个小队都有一个）。priority_queue<command>
机器人每 20 秒分析一次情况并向priority_queue.
如何使priority_queue固定大小，例如，将大小设置为 10？期望的效果是，当达到最大值时，如果我将 2 个新命令添加到队列中，则会自动删除 2 个具有最低优先级的现有命令。
问问题
15285 次
6 回答
8
将它包装在另一个将为您执行此操作的类中。该标准本身不提供此类功能。
于 2012-07-21T08:20:43.080 回答
6
Aryabhatta 对另一个问题的回答适用于这个问题。
您使用最大堆。
假设您有一个 N 元素堆（实现为数组），其中包含迄今为止看到的 N 个最小元素。
当一个元素进入时，您检查最大（O（1）时间），如果它更大，则拒绝。
前面几个评论提到的迭代是不必要的。
于 2017-06-28T04:58:10.783 回答
5
这是偷偷摸摸的，但你应该能够覆盖的功能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()？ - 可能还有很多其他的东西，所以我欢迎读者的所有建设性反馈和编辑:)
希望这是有用的，如果不是至少有趣的话。
于 2012-07-21T14:37:29.320 回答
1
一种想法是创建一个最小优先级队列并使用 size() 方法仅将优先级队列填充到所需的级别。像这样的东西：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Compare {
// priority queue is max heap by default, use compare
// to make it minheap
bool operator() (const int& a, const int& b) {
return a>b;
}
};
typedef priority_queue<int, vector<int>, Compare> pqSize;
void priorityQueueFixedSize(pqSize& pq, int size, vector<int>& vec) {
for (int i=0;i<vec.size();i++) {
if (pq.size() < size) {
pq.push(vec[i]);
} else {
if (vec[i] > pq.top()) {
pq.pop();
pq.push(vec[i]);
}
}
}
}
void printPQ(pqSize& pq) {
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
int main() {
vector<int> vec(20,0);
for (int i=0;i<vec.size();i++) {
vec[i] = i;
}
pqSize pq;
priorityQueueFixedSize(pq,10, vec);
printPQ(pq);
}
这样，优先级队列中只会保留最多 10 个元素。
于 2018-10-05T21:41:56.397 回答
1
该标准提供了一组原始堆操作：
make_heap
sort_heap
push_heap
pop_heap
我们可以将它包装在一个简单的类中，该类具有Command[10]orstd::array<Command, 10>作为其数据成员，或者以较低级别的方式简单地使用上面的四个函数。
我个人建议不要将它包装在一个函数中，因为您可能希望采用 ECS 模式并对您的命令应用更多可能的操作，而不仅仅是作为优先级队列。众所周知，如果您使用优先级队列，则可能会有不必要的复制或移动。
于 2020-10-18T05:22:39.180 回答
0
有点棘手的解决方案是不使用 std::priotity_queue，而是使用大小为 N+1 的 std::array，其中只有前 N 个元素是真正的队列。而不是替换具有最低优先级的元素，而是用queue.back()新命令覆盖。然后pop_queue(q.begin(), q.end())将新命令添加到队列中。
这是我的代码，它有效：
int main() {
std::array<int, 10> queue;
queue.fill(500);
for(int i = 0; i < 1000; i++)
{
queue.back() = rand() % 1000;
pop_heap(queue.begin(), queue.end(), std::greater<int>());
//print_queue(queue);
assert(is_heap(queue.begin(), queue.end()-1, std::greater<int>()));
}
}
另一件事是，您的规范是否是您真正想要的。不要忘记将年龄添加到优先级中。如果你不这样做，那么在一百万次迭代之后，你将拥有 10 个元素，具有最高优先级。何时将它们添加到队列中无关紧要。
于 2021-01-04T08:40:13.833 回答