削除可能 priority queue
(data-structure/erasable-priority-queue.hpp)

• View this file on GitHub
• Last update: 2026-01-12 01:17:47+09:00
• Include: #include "data-structure/erasable-priority-queue.hpp"

priority_queue を 2 つ持ち、片方に削除待ちの要素を入れて削除を遅延評価することで実質的に削除も出来るようにした priority_queue。

queue に存在しない要素を削除しようとするとバグるので注意

• push(val)
  • 値 val を優先度付きキューに push する
• top()
  • キューの先頭の値を返す
• pop()
  • キューの先頭の値を pop する（削除する）
• erase(val)
  • 値 val を削除する
  • ただしキューの中に値 val が存在する場合のみ使える。キューの中に値 val が存在するかどうかのチェックはやっていないので注意
• empty()
  • キューが空かどうかの boolean を返す

Verified with

• test/mytest/data-structure/erasable-priority-queue.test.cpp

Code

#pragma once

#include <cassert>
#include <functional>
#include <type_traits>
#include <queue>
#include <vector>

template<class T, bool isAscending = true>
struct ErasablePriorityQueue {
    using PQ = std::conditional_t<
        isAscending,
        std::priority_queue<T, std::vector<T>, std::greater<T>>,
        std::priority_queue<T>
    >;
    PQ que, rm_que;

    ErasablePriorityQueue() = default;

    void push(const T& val) {
        que.emplace(val);
    }

    T top() {
        normalize();
        assert(!que.empty());
        return que.top();
    }

    void pop() {
        normalize();
        assert(!que.empty());
        que.pop();
    }

    void erase(const T& val) {
        rm_que.emplace(val);
    }

    bool empty() {
        return que.empty();
    }
private:
    void normalize() {
        while(!que.empty() and !rm_que.empty() and que.top() == rm_que.top()) {
            que.pop();
            rm_que.pop();
        }
    }
};

#line 2 "data-structure/erasable-priority-queue.hpp"

#include <cassert>
#include <functional>
#include <type_traits>
#include <queue>
#include <vector>

template<class T, bool isAscending = true>
struct ErasablePriorityQueue {
    using PQ = std::conditional_t<
        isAscending,
        std::priority_queue<T, std::vector<T>, std::greater<T>>,
        std::priority_queue<T>
    >;
    PQ que, rm_que;

    ErasablePriorityQueue() = default;

    void push(const T& val) {
        que.emplace(val);
    }

    T top() {
        normalize();
        assert(!que.empty());
        return que.top();
    }

    void pop() {
        normalize();
        assert(!que.empty());
        que.pop();
    }

    void erase(const T& val) {
        rm_que.emplace(val);
    }

    bool empty() {
        return que.empty();
    }
private:
    void normalize() {
        while(!que.empty() and !rm_que.empty() and que.top() == rm_que.top()) {
            que.pop();
            rm_que.pop();
        }
    }
};

Back to top page