| 110 | ~SparseArray() { reset(0); } |
| 111 | |
| 112 | class iterator { |
| 113 | protected: |
| 114 | SparseArray* _a = nullptr; |
| 115 | size_t _i = 0; |
| 116 | void seek(size_t d) { |
| 117 | _i = _a->seek_existance(_i + d, d); |
| 118 | } |
| 119 | public: |
| 120 | iterator() = default; |
| 121 | iterator(SparseArray* a, size_t i = 0) : _a(a), _i(i) { } |
| 122 | iterator& operator++() { seek(1); return *this; } |
| 123 | iterator& operator--() { seek(-1); return *this; } |
| 124 | iterator operator++(int) { auto r = *this; seek(1); return r; } |
| 125 | iterator operator--(int) { auto r = *this; seek(-1); return r; } |
| 126 | void erase() { _a->erase(_i); } |
| 127 | const T& operator*() const { return *_a->get(_i); } |
| 128 | const T* operator->() const { return _a->get(_i); } |
| 129 | template<typename P> |
| 130 | void set(P&& x) { _a->set(_i, std::forward<P>(x)); } |
| 131 | bool operator==(const iterator& rhs) const { |
| 132 | return _a == rhs._a && _i == rhs._i; |
| 133 | } |
| 134 | bool operator!=(const iterator& rhs) const { |
| 135 | return !(*this == rhs); |
| 136 | } |
| 137 | T extract() { |
| 138 | assert(_a && _i < _a->size()); |
| 139 | assert(_a->get_bit(_i)); |
| 140 | auto v = _a->get(_i); |
| 141 | if (!v) return T(); |
| 142 | auto r = std::move(*v); |
| 143 | _a->erase_bit(_i); |
| 144 | return r; |
| 145 | } |
| 146 | iterator get_next() const { |
| 147 | return ++iterator(*this); |
| 148 | } |
| 149 | using difference_type = std::ptrdiff_t; |
| 150 | using value_type = T; |
| 151 | using pointer = T*; |
| 152 | using reference = T&; |
| 153 | using iterator_category = std::bidirectional_iterator_tag; |
| 154 | }; |
| 155 | |
| 156 | iterator begin() noexcept { return _begin(); } |
| 157 | iterator end() noexcept { return {this, _capacity}; } |