Comment faire une efficace mise à jour prioritaire dans la STL priority_queue?

J'ai un priority_queue de certains objets:

typedef priority_queue<Object> Queue;
Queue queue;

De temps en temps, la priorité de l'un des objets peut changer - j'ai besoin d'être en mesure de mettre à jour la priorité de l'objet dans la file d'attente de manière efficace. Actuellement, je suis en utilisant cette méthode qui fonctionne, mais semble inefficace:

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

J'ai mis en place cette façon parce que j'étais dans une sorte de hâte à l'époque et c'était la chose la plus rapide que je pouvais faire ce que je pouvais être sûr qu'il allait travailler sur ok. Il y a une meilleure façon de faire que cela. Vraiment ce que je veux, c'est un moyen de soit:

  • extrait de l'instance avec le changement de priorité et insérez-en une nouvelle avec la nouvelle valeur de priorité
  • mise à jour de l'instance avec le changement de priorité et ensuite mettre à jour la file d'attente afin qu'il soit correctement triés

Quelle est la meilleure façon de le faire?