static multiset

ソースコード

  1#include <vector>
  2#include <algorithm>
  3using namespace std;
  4
  5// StaticMultiset
  6namespace titan23 {
  7
  8    template<typename T>
  9    class StaticMultiset {
 10      private:
 11        vector<T> data;
 12        T missing;
 13        int n;
 14
 15      public:
 16        StaticMultiset() {}
 17        StaticMultiset(T missing) : missing(missing) {}
 18        StaticMultiset(vector<T> &a, T missing) : data(a), missing(missing) {
 19            sort(data.begin(), data.end());
 20            n = (int)data.size();
 21        }
 22
 23        //! 要素数を返す / `O(1)`
 24        int len() const {
 25            return n;
 26        }
 27
 28        //! 空かどうか / `O(1)`
 29        bool empty() const {
 30            return n == 0;
 31        }
 32
 33        //! 昇順 `k` 番目の要素を返す / `O(1)`
 34        T get(const int i) const {
 35            return data[i];
 36        }
 37
 38        //! `key` 以上で最小 / `O(logn)`
 39        T ge(const T &key) const {
 40            if (key > data.back() || empty()) return missing;
 41            int l = -1, r = n-1;
 42            while (r - l > 1) {
 43                int mid = (l + r) >> 1;
 44                (data[mid] >= key ? r : l) = mid;
 45            }
 46            return data[r];
 47        }
 48
 49        //! `key` より大きくて最小 / `O(logn)`
 50        T gt(const T &key) const {
 51            if (key >= data.back() || empty()) return missing;
 52            int l = -1, r = n-1;
 53            while (r - l > 1) {
 54                int mid = (l + r) >> 1;
 55                (data[mid] > key ? r : l) = mid;
 56            }
 57            return data[r];
 58        }
 59
 60        //! `key` 以下で最大 / `O(logn)`
 61        T le(const T &key) const {
 62            if (key < data[0] || empty()) return missing;
 63            int l = 0, r = n;
 64            while (r - l > 1) {
 65                int mid = (l + r) >> 1;
 66                (data[mid] <= key ? l : r) = mid;
 67            }
 68            return data[l];
 69        }
 70
 71        //! `key` 未満で最大 / `O(logn)`
 72        T lt(const T &key) const {
 73            if (key <= data[0] || empty()) return missing;
 74            int l = 0, r = n;
 75            while (r - l > 1) {
 76                int mid = (l + r) >> 1;
 77                (data[mid] < key ? l : r) = mid;
 78            }
 79            return data[l];
 80        }
 81
 82        //! `upper` 未満の要素数を返す / `O(logn)`
 83        int index(const T &upper) const {
 84            int l = -1, r = n;
 85            while (r - l > 1) {
 86                int mid = (l + r) >> 1;
 87                (data[mid] < upper ? l : r) = mid;
 88            }
 89            return r;
 90        }
 91
 92        //! `upper` 以下の要素数を返す / `O(logn)`
 93        int index_right(const T &upper) const {
 94            int l = -1, r = n;
 95            while (r - l > 1) {
 96                int mid = (l + r) >> 1;
 97                (data[mid] <= upper ? l : r) = mid;
 98            }
 99            return r;
100        }
101
102        //! `key` の要素数を返す / `O(logn)`
103        int count(const T &key) const {
104            return index_right(key) - index(key);
105        }
106
107        //! `[lower, upper)` の要素数を返す / `O(logn)`
108        int count_range(const T &lower, const T &upper) const {
109            assert(lower <= upper);
110            return index(upper) - index(lower);
111        }
112
113        //! `key` の存在判定 / `o(logn)`
114        bool contains(const T &key) const {
115            int idx = index(key);
116            if (idx == (int)data.size()) {
117                return false;
118            }
119            return data[idx] == key;
120        }
121
122        friend ostream& operator<<(ostream& os, const titan23::StaticMultiset<T>& s) {
123            int n = s.len();
124            os << "{";
125            for (int i = 0; i < n; ++i) {
126                os << s.data[i];
127                if (i != n-1) os << ", ";
128            }
129            os << "}";
130            return os;
131        }
132    };
133}

仕様

Warning

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