Prioritäts-Warteschlange mit wahlfreiem Zugriff

Question

Weiterführend Liste zur Prioritätswarteschlange

Ich implementiere eine verbesserte priority_queue mit wahlfreiem Zugriff.

template <class T, class Container = std::vector<T> >
class Heap {
public:
    Heap() {}

    Heap(const Container& container) {
        container_ = container;
        std::make_heap(container_.begin(), container_.end());
    }

    Heap<T, Container>& operator=(const Heap<T, Container>& heap) {
        if (this != &heap)
            container_ = heap.container_;

        return *this;
    }

    void push(const T& x) {
        container_.push_back(x);
        std::push_heap(container_.begin(), container_.end());
    }

    void pop() {
        std::pop_heap(container_.begin(), container_.end());
        container_.pop_back();
    }

    const T& top() {
        return container_.front();
    }

    const Container& getContainer() const {
        return container_;
    }

    T& operator[](size_t n) {
        return container_[n];
    }

    typename Container::const_iterator begin() const {
        return container_.begin();
    }

    typename Container::const_iterator end() const {
        return container_.end();
    }

    size_t size() const {
        return container_.size();
    }

    T& base() {
        return container_.back();
    }

    Container::iterator erase(Container::iterator position) {
        return container_.erase(position);
    }

private:
    Container container_;
};

Bin ich auf dem richtigen Weg?

• Der unäre Konstruktor wurde korrigiert.
• Verbesserter Code.

Answer 1

Sieht für mich nicht so toll aus:

• Der unäre Konstruktor sollte Argumente per const-Referenz annehmen.
• Der Zuweisungsoperator prüft nicht auf Selbstzuweisung.
• En getContainer() Methode zeigt einen Mangel an Klarheit in der Schnittstelle - warum sollten Sie das Implementierungsdetail einfach so offenlegen?
• Das Wichtigste: Warum wollen Sie eine "Warteschlange mit wahlfreiem Zugriff"?

Answer 2

Ihre pop()-Methode kann die Heap-Ordnung verletzen. Verwenden Sie pop_heap() anstelle von pop_back(). Ich kann im Moment keinen anderen Fehler finden.

Sie können eine solche Implementierung leicht testen, indem Sie eine zufällige ganze Zahl einschieben und eine nach der anderen mit pop() löschen. Sie sollten sie in sortierter Reihenfolge zurückbekommen. Dies ist als Heap-Sortierung bekannt.

Vorschläge:

• Anstatt einen Verweis auf den Container zurückzugeben, könnten Sie einen konstanten Iterator für diese Klasse implementieren.

• Beachten Sie, dass Sie den Schlüssel des Elements, auf das zufällig zugegriffen wird, nicht ändern sollten, da dies die Heap-Struktur zerstören könnte. Wenn Sie eine solche Funktionalität benötigen, sollten Sie eine change_key-Funktion implementieren, die den Schlüssel sicher ändert und die Heap-Reihenfolge beibehält.