data-structure/erasable-priority-queue.hpp

• View this file on GitHub
• Last update: 2023-08-08 00:16:33+09:00
• Include: #include "data-structure/erasable-priority-queue.hpp"

Required by

• data-structure/erasable-priority-queue-with-contains.hpp

Code

template<typename T, typename Comp = less<T>>
struct ErasablePriorityQueue{
    priority_queue<T, vector<T>, Comp> data, erased;
    
    ErasablePriorityQueue(){}

    void push(T x){
      data.push(x);
    }

    void erase(T x){
      erased.push(x);
    }

    void modify(){
      while(!data.empty() && !erased.empty() && data.top() == erased.top()){
        data.pop();
        erased.pop();
      }
      if(data.empty()){
        erased.clear();
      }
    }

    T top(){
      modify();
      return data.top();
    }

    void pop(){
      modify();
      data.pop();
    }

    bool empty(){
      modify();
      return data.empty();
    }
};

#line 1 "data-structure/erasable-priority-queue.hpp"
template<typename T, typename Comp = less<T>>
struct ErasablePriorityQueue{
    priority_queue<T, vector<T>, Comp> data, erased;
    
    ErasablePriorityQueue(){}

    void push(T x){
      data.push(x);
    }

    void erase(T x){
      erased.push(x);
    }

    void modify(){
      while(!data.empty() && !erased.empty() && data.top() == erased.top()){
        data.pop();
        erased.pop();
      }
      if(data.empty()){
        erased.clear();
      }
    }

    T top(){
      modify();
      return data.top();
    }

    void pop(){
      modify();
      data.pop();
    }

    bool empty(){
      modify();
      return data.empty();
    }
};

Back to top page