如何在STL priority_queue中进行有效的优先级更新？ [英] How to do an efficient priority update in STL priority_queue?

问题描述

我有一个对象的priority_queue：

I have a priority_queue of some object:

typedef priority_queue<Object> Queue;
Queue queue;

有时，其中一个对象的优先级可能会更改 - 我需要能够以有效的方式更新队列中该对象的优先级。目前我使用这种方法，但工作效率似乎低下：

From time to time, the priority of one of the objects may change - I need to be able to update the priority of that object in the queue in an efficient way. Currently I am using this method which works but seems inefficient:

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

我以这种方式实现，因为我在当时很匆忙，这是我能做的最快的事情，我可以确定它会工作确定。有一个比这更好的方法。真的我想要的是一种方式：

I implemented it this way because I was in kind of a hurry at the time and this was the quickest thing I could do that I could be sure it would work ok. There has to be a better way than this though. Really what I want is a way to either:

• 提取具有更改的优先级的实例，并插入一个新的优先级值


• 更新已更改优先级的实例，然后更新队列，以便正确排序
。

这是最好的方法是什么？

What is the best way to do this?

推荐答案

我认为你不幸运与标准的优先级队列，因为你可以't得到底层deque / vector / list或任何。你需要实现自己的 - 不是那么难。

I think you are out of luck with standard priority queue because you can't get at the underlying deque/vector/list or whatever. You need to implement your own - it's not that hard.

这篇关于如何在STL priority_queue中进行有效的优先级更新？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！