Index Set
(marathon/index_set.cpp)

• View this file on GitHub
• Last update: 2025-03-01 10:35:11+09:00

• $\left[ 0, n \right)$ の整数の集合を扱うデータ構造
• 値の追加・削除・存在確認について、最悪時間計算量 $O(1)$、空間計算量 $O(N)$

参考: https://topcoder-tomerun.hatenablog.jp/entry/2021/06/12/134643

Code

class IndexSet {
public:
    IndexSet(int n) : pos_(n, -1) {}

    void insert(int x) {
        if (contains(x)) return;
        que_.push_back(x);
        pos_[x] = que_.size() - 1;
    }

    void erase(int x) {
        if (!contains(x)) return;
        int idx = pos_[x];
        if (idx == -1) return;
        int last = que_.back();
        que_[idx] = last;
        pos_[last] = idx;
        que_.pop_back();
        pos_[x] = -1;
    }

    int size() const {
        return que_.size();
    }

    bool contains(int x) const {
        return pos_[x] != -1;
    }

    int operator[](int idx) const {
        return que_[idx];
    }

    const vector<int>& get_elements() const {
        return que_;
    }

private:
    vector<int> que_;
    vector<int> pos_;
};

#line 1 "marathon/index_set.cpp"
class IndexSet {
public:
    IndexSet(int n) : pos_(n, -1) {}

    void insert(int x) {
        if (contains(x)) return;
        que_.push_back(x);
        pos_[x] = que_.size() - 1;
    }

    void erase(int x) {
        if (!contains(x)) return;
        int idx = pos_[x];
        if (idx == -1) return;
        int last = que_.back();
        que_[idx] = last;
        pos_[last] = idx;
        que_.pop_back();
        pos_[x] = -1;
    }

    int size() const {
        return que_.size();
    }

    bool contains(int x) const {
        return pos_[x] != -1;
    }

    int operator[](int idx) const {
        return que_[idx];
    }

    const vector<int>& get_elements() const {
        return que_;
    }

private:
    vector<int> que_;
    vector<int> pos_;
};

Back to top page