J'ai suivi du code:
#include <iostream>
#include <map>
#include <list>
#include <queue>
#include <memory>
enum class CommandType : uint8_t {
Comm1,
Comm2,
Comm3,
Comm4,
Comm5
};
enum class Priority {
HIGH,
MEDIUM,
LOW
};
std::map<CommandType, Priority> priorities = {
{ CommandType::Comm1, Priority::LOW },
{ CommandType::Comm2, Priority::LOW },
{ CommandType::Comm3, Priority::LOW },
{ CommandType::Comm4, Priority::LOW },
{ CommandType::Comm5, Priority::LOW }
};
class QueueEntry
{
public:
QueueEntry(CommandType type)
: type_(type) {}
CommandType getType() { return type_; }
private:
CommandType type_;
};
struct QueueEntryPriorityComparator {
bool operator()(std::unique_ptr<QueueEntry>& entry1, std::unique_ptr<QueueEntry>& entry2) const
{
auto p1 = priorities.at(entry1->getType());
auto p2 = priorities.at(entry2->getType());
return p1 < p2;
}
};
std::priority_queue<std::unique_ptr<QueueEntry>, std::deque<std::unique_ptr<QueueEntry>>, QueueEntryPriorityComparator> q;
void print()
{
decltype(q) queueCopy;
queueCopy.swap(q);
while (!queueCopy.empty()) {
auto& top = queueCopy.top();
std::cout << "Command type: " << static_cast<uint32_t>(top->getType()) << std::endl;;
q.emplace(std::make_unique<QueueEntry>(top->getType()));
queueCopy.pop();
}
}
int main()
{
q.emplace(std::make_unique<QueueEntry>(CommandType::Comm1));
q.emplace(std::make_unique<QueueEntry>(CommandType::Comm2));
q.emplace(std::make_unique<QueueEntry>(CommandType::Comm3));
q.emplace(std::make_unique<QueueEntry>(CommandType::Comm4));
q.emplace(std::make_unique<QueueEntry>(CommandType::Comm5));
print();
std::cout << std::endl;
print();
std::cout << std::endl;
print();
return 0;
}
4 Réponses :
Si vous en avez besoin pour rester dans la commande entrée, une chose que vous pouvez faire est d'écrire votre propre objet qui utilise std :: priority_queue est implémenté à l'aide de STD :: make_heap , std :: push_heap et std :: pop_heap sur le conteneur sous-jacent. Ces opérations ne sont pas stables, vous n'avez donc aucune garantie que les éléments resteront dans la commande entrée.
STD :: Stable_sort sur le conteneur sous-jacent lors de l'ajout d'éléments dedans.
Si vous voulez une file d'attente prioritaire garantissant que les éléments comparatifs égaux préservent l'ordre d'insertion, vous devez l'écrire vous-même.
Certainement STD :: Priority_Queue fait ne garantit pas cet ordonnance d'insertion (et s'il est mis en œuvre en tant que tas, cela ne le garantit pas non plus).
Le moyen le plus simple d'écrire quelque chose correct est probablement avec carte stable_sort Un conteneur a pire complexité algorithmique, mais fonctionne probablement mieux dans la plupart des situations du monde réel malgré cela.
La question est de savoir comment ces éléments sont placés en priority_queue? p>
Dans une ordonnance qui répond à la propriété du tas. Qui pour les éléments égaux est tout ordre em>. P>
C'est importé pour moi que, si un nouvel élément vient à priority_queue doit être placé après le dernier élément avec la même priorité. P> blockquote>
Vous pouvez y parvenir en faisant partie de la commande de la priorité. Mais pour faire partie de la priorté, vous devez d'abord faire une partie de la commande de l'élément. Vous pouvez utiliser un compteur de course: P>
struct OrderedQueueEntry { QueueEntry entry; int index; }; struct OrderedQueueEntryPriorityComparator { bool operator()(std::unique_ptr<OrderedQueueEntry>& left, std::unique_ptr<OrderedQueueEntry>& right) const { auto pl = priorities.at(left->entry.getType()); auto pr = priorities.at(right->entry.getType()); return pl == pr ? left->index < right->index; : pl < pr; } }; int i = 0; q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm1, i++})); q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm2, i++})); q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm3, i++})); q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm4, i++})); q.emplace(std::make_unique<OrderedQueueEntry>({CommandType::Comm5, i++}));
std :: multiset ou std :: multimap
Il suffit d'utiliser std :: multiset ou std :: multimap (à partir de votre cas, le multimap ressemble au bon choix).
https://en.cppreference.com/w/cpp/container/Multimap
Les deux sont staples et ne changent pas l'ordre d'insertion (puisque C ++ 11 ).
Rien dans la spécification de priority_queue indique comment les éléments de la même priorité sont triés. Vous devez ajouter des informations sur vos données et définir une nouvelle commande pour prendre en compte la commande d'insertion.
Si vous souhaitez que de nouveaux éléments de la même priorité aient une priorité inférieure, ils n'ont pas vraiment la même priorité, n'est-ce pas?