dynamic list

ソースコード

  1#include <iostream>
  2#include <vector>
  3#include <cassert>
  4#include <cmath>
  5using namespace std;
  6
  7// DynamicList
  8namespace titan23 {
  9
 10    template<typename T>
 11    class DynamicList {
 12      private:
 13        static const int BUCKET_MAX = 500;
 14        vector<vector<T>> data;
 15        int n;
 16
 17        void build(const vector<T> &a) {
 18            long long s = len();
 19            int bucketn = max((int)(s+BUCKET_MAX-1)/BUCKET_MAX, (int)ceil(sqrt(s)));
 20            data.resize(bucketn);
 21            for (int i = 0; i < bucketn; ++i) {
 22                int start = s*i/bucketn;
 23                int stop = min((int)len(), (int)(s*(i+1)/bucketn));
 24                data[i] = vector<T>(a.begin()+start, a.begin()+stop);
 25            }
 26        }
 27
 28        pair<int, int> get_bucket(int k) const {
 29            if (k == len()) return {-1, -1};
 30            if (k < len()/2) {
 31                for (int i = 0; i < data.size(); ++i) {
 32                    if (k < data[i].size()) return {i, k};
 33                    k -= data[i].size();
 34                }
 35            } else {
 36                int tot = len();
 37                for (int i = data.size()-1; i >= 0; --i) {
 38                    if (tot-data[i].size() <= k) {
 39                        return {i, k-(tot-data[i].size())};
 40                    }
 41                    tot -= data[i].size();
 42                }
 43            }
 44            assert(false);
 45        }
 46
 47      public:
 48        DynamicList() : n(0) {}
 49
 50        DynamicList(const vector<T> &a) : n(a.size()) {
 51            build(a);
 52        }
 53
 54        void emplace_back(T key) {
 55            insert(len(), key);
 56        }
 57
 58        void insert(int k, T key) {
 59            assert(0 <= k && k <= len());
 60            if (data.empty()) {
 61                ++n;
 62                data.push_back({key});
 63                return;
 64            }
 65            auto [bucket_pos, bit_pos] = get_bucket(k);
 66            if (bucket_pos == -1) {
 67                bucket_pos = data.size()-1;
 68                data.back().emplace_back(key);
 69            } else {
 70                data[bucket_pos].insert(data[bucket_pos].begin() + bit_pos, key);
 71            }
 72
 73            if (data[bucket_pos].size() > BUCKET_MAX) {
 74                vector<T> right(data[bucket_pos].begin() + BUCKET_MAX/2, data[bucket_pos].end());
 75                data[bucket_pos].erase(data[bucket_pos].begin() + BUCKET_MAX/2, data[bucket_pos].end());
 76                data.emplace(data.begin() + bucket_pos+1, right);
 77            }
 78            ++n;
 79        }
 80
 81        bool access(int k) const {
 82            assert(0 <= k && k < len());
 83            auto [bucket_pos, bit_pos] = get_bucket(k);
 84            return data[bucket_pos][bit_pos];
 85        }
 86
 87        T pop(int k) {
 88            assert(0 <= k && k < len());
 89            auto [bucket_pos, bit_pos] = get_bucket(k);
 90            bool res = data[bucket_pos][bit_pos];
 91            data[bucket_pos].erase(data[bucket_pos].begin() + bit_pos);
 92            --n;
 93            if (data[bucket_pos].empty()) {
 94                data.erase(data.begin() + bucket_pos);
 95            }
 96            return res;
 97        }
 98
 99        void set(int k, bool v) {
100            assert(0 <= k && k < len());
101            auto [bucket_pos, bit_pos] = get_bucket(k);
102            data[bucket_pos][bit_pos] = v;
103        }
104
105        vector<T> tovector() const {
106            vector<T> a(len());
107            int ptr = 0;
108            for (const vector<T> &d: data) for (const T &x: d) {
109                a[ptr++] = x;
110            }
111            return a;
112        }
113
114        void print() const {
115            vector<T> a = tovector();
116            int n = (int)a.size();
117            assert(n == len());
118            cout << "[";
119            for (int i = 0; i < n-1; ++i) {
120                cout << a[i] << ", ";
121            }
122            if (n > 0) {
123                cout << a.back();
124            }
125            cout << "]";
126            cout << endl;
127        }
128
129        bool empty() const { return n == 0; }
130        int len() const { return n; }
131    };
132} // namespace titan23

仕様

Warning

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