Implementieren einer Prioritätswarteschlange, die in C++ übersprungen werden kann

Question

Ich muss eine Prioritätswarteschlange für ein Projekt implementieren, aber die STL priority_queue wird nicht angezeigt, da wir über alle Elemente iterieren und sie zufällig entfernen müssen.

Wir denken über die Verwendung der STL set dafür, um es in eine Klasse zu wickeln, um es zu einem ADT zu machen.

Gibt es dafür eine intelligentere Lösung?

Wie können wir es so machen, dass einige der öffentlichen Mitgliederfunktionen von set öffentlich genutzt werden können? Wir interessieren uns für Iteratoren usw.

Offenbar die STL Ableitung wegen des Fehlens von virtuellen Destruktoren unklug ist:/

---

Neuer Code:

#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_ */ 

Also, wir haben derzeit Dies. Der Compiler beschwert sich nicht über Einsatz, aber es beschwert sich über erase(begin()) und return *begin():

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

Warum ist das?

Answer 1

Sie sollten in der Lage sein, eine eigene Prioritätswarteschlange mit std::vector, std::make_heap, std::push_heap und std::pop_heap zu implementieren. Ist das nicht std::priority_queue implementiert? Sie müssen nur noch std::make_heap aufrufen, um die Datenstruktur zu reparieren, wenn Sie ein zufälliges Element entfernen.

Müssen Sie die Elemente der Reihe nach durchlaufen? Es gibt einen std::sort_heap Algorithmus, um den zugrunde liegenden std::vector zu bestellen.

Answer 2

Benötigen Sie wirklich eine Prioritätswarteschlange?

Sie müssen alle Elemente iterieren und entfernen Sie zufällig -> verkettete Liste

Wenn Sie die Liste sortiert halten müssen, sortieren sie am Anfang und dann, wenn neue Artikel eingefügt, Verwendung Insertionsort (neues Element einfügen an der richtigen Stelle).

Answer 3

STL-Set sollte verwendbar sein, um zu machen, was Sie wollen, obwohl ich beachten muss, dass die Liste der Anforderungen ein wenig seltsam aussieht. Sie könnten einfach einen neuen Typ definieren.

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

würde ich das Beispiel von einigen der anderen Container-Adapter in der Standardbibliothek Verwendung Zusammensetzung und machen die Art des zugrundeliegenden Container ein Template-Parameter eingestellt folgen. Obwohl es ein Schulprojekt ist, könnte das zu viel Flexibilität sein. Sie können damit beginnen, die Komposition mit einem der vorhandenen Container zu verwenden und von dort aus zu erstellen.