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

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

Depends on

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

Code

#include "erasable-priority-queue.hpp"
template<typename T, typename Comp = less<T>>
struct ErasablePriorityQueueWithContains{
    ErasablePriorityQueue<T, Comp> data;
    multiset<T> contained;

    ErasablePriorityQueueWithContains(){}

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

    void erase(T x){
      contained.erase(contained.find(x));
      data.erase(x);
    }

    bool contains(T x){
      return contained.find(x) != contained.end();
    }

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

    void pop(){
      contained.erase(contained.find(data.top()));
      data.pop();
    }

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

    int size(){
      return contained.size();
    }

    void clear(){
      data = ErasablePriorityQueue<T, Comp>();
      contained.clear();
    }

    void swap(ErasablePriorityQueueWithContains<T, Comp> &other){
      data.swap(other.data);
      contained.swap(other.contained);
    }
};

#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();
    }
};
#line 2 "data-structure/erasable-priority-queue-with-contains.hpp"
template<typename T, typename Comp = less<T>>
struct ErasablePriorityQueueWithContains{
    ErasablePriorityQueue<T, Comp> data;
    multiset<T> contained;

    ErasablePriorityQueueWithContains(){}

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

    void erase(T x){
      contained.erase(contained.find(x));
      data.erase(x);
    }

    bool contains(T x){
      return contained.find(x) != contained.end();
    }

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

    void pop(){
      contained.erase(contained.find(data.top()));
      data.pop();
    }

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

    int size(){
      return contained.size();
    }

    void clear(){
      data = ErasablePriorityQueue<T, Comp>();
      contained.clear();
    }

    void swap(ErasablePriorityQueueWithContains<T, Comp> &other){
      data.swap(other.data);
      contained.swap(other.contained);
    }
};

Back to top page