Implementazione di una coda di priorità che può essere ripetuta in C++

Question

È necessario implementare una coda di priorità per un progetto, ma il numero priority_queue dell'STL non è indicato poiché è necessario iterare su tutti gli elementi e rimuoverli casualmente.

Stiamo pensando di utilizzare l'STL set per questo, inserendolo in una classe per renderlo un ADT.

C'è una soluzione più intelligente per questo?

Come possiamo rendere alcune delle funzioni di membro pubblico di set possono essere utilizzate pubblicamente? Siamo interessati a iteratori, ecc

A quanto pare derivare lo STL è sconsigliabile a causa della mancanza di distruttori virtuali:/

---

Nuovo codice:

#ifndef PRIORITYQUEUE_H_ 
#define PRIORITYQUEUE_H_ 

#include <set> 

template<typename T, template<typename X> class impl_type = std::set> 
class PriorityQueue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
public: 
    void push(const T& x) { 
     insert(x); 

    } 

    void pop() { 
     erase(begin()); 
    } 

    const T& top() const { 
     return *begin(); 
    } 
}; 

#endif /* PRIORITYQUEUE_H_ */ 

Quindi, attualmente abbiamo Questo. Il compilatore non si lamenta di inserimento, ma non si lamenta erase(begin()) e return *begin():

there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available

Perché è questo?

Answer 1

Si dovrebbe essere in grado di implementare la propria coda di priorità utilizzando std::vector, std::make_heap, std::push_heap e std::pop_heap. Non è così che viene implementato std::priority_queue? Dovrai semplicemente chiamare lo std::make_heap di nuovo per correggere la struttura dei dati quando rimuovi un elemento casuale.

Avete bisogno di iterare sugli elementi in ordine? C'è un algoritmo std::sort_heap per ordinare il sottostante std::vector.

Answer 2

Hai davvero bisogno di una coda di priorità?

È necessario iterare su tutti gli articoli e rimuovere in modo casuale -> Elenco

legato Se è necessario mantenere l'elenco ordinato, ordinare è all'inizio e poi, quando si inserisce il nuovo articolo, l'uso insertion sort (inserire una nuova voce nel posto giusto).

Answer 3

Il set di STL dovrebbe essere utilizzabile per creare ciò che desideri, anche se devo notare che l'elenco dei requisiti sembra un po 'strano. Potresti semplicemente definire un nuovo tipo.

template<typename T, template<typename X> class impl_type = std::set> class prio_queue { 
    typedef impl_type<T> set_type; 
    typedef typename set_type::iterator iterator; 
    // etc 
public: 
    // Forward the set's members 
    T& top() { 
     return *begin(); 
    } 
    // etc 
}; 

Answer 4

avrei seguito l'esempio alcune delle altre schede contenitore nella composizione uso libreria standard e rendere il tipo di contenitore sottostante un parametro di modello. Anche se è un progetto scolastico che potrebbe essere troppo flessibile. Si potrebbe iniziare usando la composizione con uno dei contenitori esistenti e costruendoli da lì se necessario.