data_structure/removable_priority_queue.hpp

• View this file on GitHub
• Last update: 2024-02-24 22:02:04+09:00
• Include: #include "data_structure/removable_priority_queue.hpp"

Code

#pragma once
#include <cassert>
#include <queue>
template <typename T, typename Comp = std::less<T>>
class RemovablePriorityQueue {
    std::priority_queue<T, std::vector<T>, Comp> pq, rem;
    void remove_() {
        while (!pq.empty() && !rem.empty() && pq.top() == rem.top()) {
            pq.pop();
            rem.pop();
        }
    }
public:
    RemovablePriorityQueue(Comp comp = Comp()) : pq(comp), rem(comp) {}
    void push(T x) {
        pq.push(x);
    }
    void remove(T x) {
        rem.push(x);
    }
    T pop() {
        remove_();
        assert(!pq.empty());
        T ret = pq.top();
        pq.pop();
        return ret;
    }
    T top() {
        remove_();
        assert(!pq.empty());
        return pq.top();
    }
    int size() const {
        return (int)pq.size() - (int)rem.size();
    }
    bool empty() const {
        return size() == 0;
    }
};

#line 2 "data_structure/removable_priority_queue.hpp"
#include <cassert>
#include <queue>
template <typename T, typename Comp = std::less<T>>
class RemovablePriorityQueue {
    std::priority_queue<T, std::vector<T>, Comp> pq, rem;
    void remove_() {
        while (!pq.empty() && !rem.empty() && pq.top() == rem.top()) {
            pq.pop();
            rem.pop();
        }
    }
public:
    RemovablePriorityQueue(Comp comp = Comp()) : pq(comp), rem(comp) {}
    void push(T x) {
        pq.push(x);
    }
    void remove(T x) {
        rem.push(x);
    }
    T pop() {
        remove_();
        assert(!pq.empty());
        T ret = pq.top();
        pq.pop();
        return ret;
    }
    T top() {
        remove_();
        assert(!pq.empty());
        return pq.top();
    }
    int size() const {
        return (int)pq.size() - (int)rem.size();
    }
    bool empty() const {
        return size() == 0;
    }
};

Back to top page