Priority Queue mutable



  • Hallo,

    kennt jemand eine Priority Queue die mutable ist, also wo ich Werte random in der Queue aktualisieren kann?

    Die STL hat ja leider nix...



  • Nach einiger Überlegung bin ich dazu übergegangen, eine Priority Queue mittels std::set zu realisieren.

    Über pop() kann man dann direkt erase(iterator) bemühen. Außerdem kann man auch direkt die Sortierregel (std::greater) festlegen.

    Vorteil ist ganz klar, dass bei einer mutable Queue std::set eine hervorragende Performance erbringt, wenn man also gelegentlich Elemente verändert. Dazu muss man sie rauskopieren, ändern, neu einfügen und das alte Element löschen. Da man den Iterator ohnehin hat geht das sehr schnell.

    template<
            class V,
            class Container = std::set<V, std::greater<V>>>
            class PriorityQueue : public Container
        {
        public:
            void push(const V&);
            V top();
            void pop();
        };
    
        template<class V, class Container>
        void PriorityQueue<V, Container>::push(const V& x)
        {
            Container::insert(x);
        }
    
        template<class V, class Container>
        V PriorityQueue<V, Container>::top()
        {
            return *(begin());
        }
    
        template<class V, class Container>
        void PriorityQueue<V, Container>::pop()
        {
            Container::erase(begin());
        }
    

Log in to reply