deque

ソースコード

  1#include <iostream>
  2#include <vector>
  3#include <cassert>
  4using namespace std;
  5
  6namespace titan23 {
  7
  8    template<typename T>
  9    struct Deque {
 10        vector<T> front, back;
 11
 12        Deque() {}
 13
 14        Deque(vector<T> a) : back(a) {}
 15
 16        void _rebuild() {
 17            int n = (int)(front.size() + back.size()) / 2;
 18            int idx_front = 0, idx_back = 0;
 19            vector<T> new_front, new_back;
 20            new_front.reserve(n);
 21            new_back.reserve(n);
 22            for (int i = 0; i < n; ++i) {
 23                if (idx_front < front.size()) {
 24                    new_front.emplace_back(front[idx_front++]);
 25                } else if (idx_back < back.size()) {
 26                    new_back.emplace_back(back[idx_back++]);
 27                }
 28            }
 29            reverse(new_front.begin(), new_front.end());
 30            for (int i = 0; i < n; ++i) {
 31                if (idx_front < front.size()) {
 32                    new_front.emplace_back(front[idx_front++]);
 33                } else if (idx_back < back.size()) {
 34                    new_back.emplace_back(back[idx_back++]);
 35                }
 36            }
 37            this->front = new_front;
 38            this->back = new_back;
 39        }
 40
 41        void push_back(const T v) {
 42            back.push_back(v);
 43        }
 44
 45        void push_front(const T v) {
 46            front.push_back(v);
 47        }
 48
 49        T pop_back() {
 50            if (back.empty()) _rebuild();
 51            T res;
 52            if (back.empty()) {
 53                res = front.back();
 54                front.pop_back();
 55            } else {
 56                res = back.back();
 57                back.pop_back();
 58            }
 59            return res;
 60        }
 61
 62        T pop_front() {
 63            if (front.empty()) _rebuild();
 64            T res;
 65            if (front.empty()) {
 66                res = back.back();
 67                back.pop_back();
 68            } else {
 69                res = front.back();
 70                front.pop_back();
 71            }
 72            return res;
 73        }
 74
 75        vector<T> tovector() const {
 76            vector<int> a;
 77            a.reserve(front.size() + back.size());
 78            for (int i = front.size() - 1; i >= 0; i--) {
 79                a.emplace_back(front[i]);
 80            }
 81            for (int i = 0; i < back.size(); i++) {
 82                a.emplace_back(back[i]);
 83            }
 84            return a;
 85        }
 86
 87        T& operator[](int k) {
 88            if (k < 0) k += len();
 89            return k < front.size() ? front[front.size() - k - 1] : back[k - front.size()];
 90        }
 91
 92        const T& operator()(int k) const {
 93            if (k < 0) k += len();
 94            return k < front.size() ? front[front.size() - k - 1] : back[k - front.size()];
 95        }
 96
 97        int len() const {
 98            return (int)(front.size() + back.size());
 99        }
100
101        bool empty() const {
102            return (bool)(front.size() + back.size());
103        }
104
105        bool contains(const T v) const {
106            for (const T &a : front) {
107                if (a == v) return true;
108            }
109            for (const T &a : back) {
110                if (a == v) return true;
111            }
112            return false;
113        }
114        
115        void print() const {
116            vector<T> a = tovector();
117            cout << "Deque([";
118            for (int i = 0; i < len()-1; ++i) {
119                cout << a[i] << ", ";
120            }
121            if (len() > 0) {
122                cout << a.back();
123            }
124            cout << "])\n";
125        }
126    };
127}  // namespace titan23

仕様

Warning

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