static set¶
ソースコード¶
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5// StaticSet
6namespace titan23 {
7
8 /**
9 * @brief 静的な全順序集合を管理するデータ構造
10 */
11 template<typename T>
12 class StaticSet {
13 private:
14 vector<T> data;
15 T missing;
16 int n;
17
18 public:
19 StaticSet() {}
20
21 /**
22 * @brief Construct a new Static Set object / `O(1)`
23 *
24 * @param missing 使用しない値
25 */
26 StaticSet(T missing) : missing(missing) {}
27
28 /**
29 * @brief Construct a new Static Set object / `O(nlogn)`
30 *
31 * @param a
32 * @param missing 使用しない値
33 */
34 StaticSet(vector<T> &a, T missing) : data(a), missing(missing) {
35 sort(data.begin(), data.end());
36 data.erase(unique(data.begin(), data.end()), data.end());
37 n = (int)data.size();
38 }
39
40 // コンストラクタ以外で使用するとき専用のメソッド
41 void build(vector<T> a, T missing) {
42 this->data = a;
43 this->missing = missing;
44 sort(data.begin(), data.end());
45 data.erase(unique(data.begin(), data.end()), data.end());
46 n = (int)data.size();
47 }
48
49 //! 要素数を返す / `O(1)`
50 int len() const {
51 return n;
52 }
53
54 //! 空かどうか / `O(1)`
55 bool empty() const {
56 return n == 0;
57 }
58
59 //! 昇順 `k` 番目の要素を返す / `O(1)`
60 T get(const int k) const {
61 assert(0 <= k && k < len());
62 return data[k];
63 }
64
65 //! `key` 以上で最小 / `O(logn)`
66 T ge(const T &key) const {
67 if (key > data.back() || empty()) return missing;
68 int l = -1, r = n-1;
69 while (r - l > 1) {
70 int mid = (l + r) >> 1;
71 (data[mid] >= key ? r : l) = mid;
72 }
73 return data[r];
74 }
75
76 //! `key` より大きくて最小 / `O(logn)`
77 T gt(const T &key) const {
78 if (key >= data.back() || empty()) return missing;
79 int l = -1, r = n-1;
80 while (r - l > 1) {
81 int mid = (l + r) >> 1;
82 (data[mid] > key ? r : l) = mid;
83 }
84 return data[r];
85 }
86
87 //! `key` 以下で最大 / `O(logn)`
88 T le(const T &key) const {
89 if (key < data[0] || empty()) return missing;
90 int l = 0, r = n;
91 while (r - l > 1) {
92 int mid = (l + r) >> 1;
93 (data[mid] <= key ? l : r) = mid;
94 }
95 return data[l];
96 }
97
98 //! `key` 未満で最大 / `O(logn)`
99 T lt(const T &key) const {
100 if (key <= data[0] || empty()) return missing;
101 int l = 0, r = n;
102 while (r - l > 1) {
103 int mid = (l + r) >> 1;
104 (data[mid] < key ? l : r) = mid;
105 }
106 return data[l];
107 }
108
109 //! `upper` 未満の要素数を返す / `O(logn)`
110 int index(const T &upper) const {
111 int l = -1, r = n;
112 while (r - l > 1) {
113 int mid = (l + r) >> 1;
114 (data[mid] < upper ? l : r) = mid;
115 }
116 return r;
117 }
118
119 //! `upper` 以下の要素数を返す / `O(logn)`
120 int index_right(const T &upper) const {
121 int l = -1, r = n;
122 while (r - l > 1) {
123 int mid = (l + r) >> 1;
124 (data[mid] <= upper ? l : r) = mid;
125 }
126 return r;
127 }
128
129 //! `key` の要素数を返す / `O(logn)`
130 int count(const T &key) const {
131 return contains(key) ? 1 : 0;
132 }
133
134 //! `[lower, upper)` の要素数を返す / `O(logn)`
135 int count_range(const T &lower, const T &upper) const {
136 assert(lower <= upper);
137 return index(upper) - index(lower);
138 }
139
140 //! `key` の存在判定 / `O(logn)`
141 bool contains(const T &key) const {
142 int idx = index(key);
143 if (idx == (int)data.size()) {
144 return false;
145 }
146 return data[idx] == key;
147 }
148
149 T neighbor(const T &key) const {
150 T ge_key = ge(key);
151 T le_key = le(key);
152 if (ge_key == missing) return le_key;
153 if (le_key == missing) return ge_key;
154 return (ge_key-key < key-le_key) ? ge_key : le_key;
155 }
156
157 friend ostream& operator<<(ostream& os, const titan23::StaticSet<T>& s) {
158 int n = s.len();
159 os << "{";
160 for (int i = 0; i < n; ++i) {
161 os << s.data[i];
162 if (i != n-1) os << ", ";
163 }
164 os << "}";
165 return os;
166 }
167 };
168}
仕様¶
Warning
doxygenfile: Cannot find file “titan_cpplib/data_structures/static_set.cpp