index set

ソースコード

 1#include <iostream>
 2#include <algorithm>
 3#include <vector>
 4#include <cassert>
 5using namespace std;
 6
 7namespace titan23 {
 8
 9class IndexSet {
10    // https://topcoder-tomerun.hatenablog.jp/entry/2021/06/12/134643
11  public:
12    vector<int> que, pos;
13
14    IndexSet() {}
15    IndexSet(int u) : pos(u, -1) {}
16
17    void add(int v) {
18        if (pos[v] != -1) return;
19        pos[v] = que.size();
20        que.push_back(v);
21    }
22
23    bool discard(int v) {
24        int p = pos[v];
25        if (p == -1) return false;
26        int b = que.back();
27        que[p] = b;
28        que.pop_back();
29        pos[b] = p;
30        pos[v] = -1;
31        return true;
32    }
33
34    void remove(int v) {
35        int p = pos[v];
36        assert(p != -1);
37        int b = que.back();
38        que[p] = b;
39        que.pop_back();
40        pos[b] = p;
41        pos[v] = -1;
42    }
43
44    bool contains(int v) const {
45        return pos[v] != -1;
46    }
47
48    void clear() {
49        fill(pos.begin(), pos.end(), -1);
50        que.clear();
51    }
52
53    int len() const {
54        return que.size();
55    }
56
57    bool empty() const {
58        return que.size() == 0;
59    }
60
61    int get(int v) const {
62        // assert(0 <= v && v < len());
63        return que[v];
64    }
65
66    friend ostream& operator<<(ostream& os, const titan23::IndexSet &ist) {
67        vector<int> a = ist.que;
68        sort(a.begin(), a.end());
69        int n = a.size();
70        os << "{";
71        for (int i = 0; i < n; ++i) {
72            os << a[i];
73            if (i != n-1) os << ", ";
74        }
75        os << "}";
76        return os;
77    }
78};
79} // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/index_set.cpp