", ma lo STL :: priority_queue non funziona per me, perché ho bisogno di trovare se un elemento (un oggetto Node) è in priority_queue o meno, di accedere ai suoi dati e di modificarlo se necessario."
si può ben fare questo per qualsiasi tipo di classe di fornire un parametro Compare classe appropriata.
std::priority_queue<T> richiede che il sottostante Container rispetti il concetto di SequenceContainer.
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
si può prendere l'indirizzo di riferimento std::priority_queue<T>::front(), e scorrere la coda, per trovare alcuni casi.
Se davvero bisogno di avere le istanze in modo univoco esistenti di oggetti, che devono essere gestiti in aggiunta da qualche algoritmo di priorità, potrebbe essere una buona idea per memorizzare i puntatori intelligenti (ad esempio std::shared_ptr<T>), piuttosto che i valori o puntatori prime . La classe Compare deve essere adattata in modo appropriato, naturalmente.
struct CompareNodes {
bool operator
(const std::shared_ptr<Node>& lhs
, const std::shared_ptr<Node>& rhs
) {
// Provide some operation to compare lhs < rhs (less) results in true
// This function is meant to determine the actual priority of your Node
// instances, when referenced in the priority_queue<> in question.
}
};
std::priority_queue
< std::shared_ptr<Node>
, std::vector<std::shared_ptr<Node>>
, CompareNodes
> myQueue;
"per accedere ai suoi dati e per modificare, se necessario."
Utilizzando la coda di priorità con std::shared_ptr come mostrato nell'esempio di cui sopra, può anche rilasciare da nemmeno bisogno di trovare casi in coda, e sincronizzare modifiche ai dati dall'istanza originale.
Non è possibile utilizzare front() e iterare attraverso di esso? – 2501
che dire di boost :: bimap? –
Si noti che i contenitori di libreria standard di solito evitano di fornire operazioni quando sarebbero inefficienti. Nella consueta implementazione della coda di priorità (usando un heap), i test di ricerca e di appartenenza hanno complessità O (N), che è probabilmente il motivo per cui questa operazione non viene fornita incorporata. Questo potrebbe o non potrebbe essere un problema per la tua applicazione. Basta prestare attenzione a quanto spesso è necessario testare l'appartenenza. –