Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Unordered Set

コードについての説明

hash を用いた順序付き集合クラスの実装である. やっていることは こちら の実装と同じ.
もう少し verify を重ねたい気はしている.

コード

  1. template<class _Key, class _Hash, bool DOWNSIZE> class UnorderedSetIterator;
  2.  
  3. template<class _Key, class _Hash = hash<_Key>, bool DOWNSIZE = false>
  4. class UnorderedSet
  5. {
  6. private:
  7. using iterator = UnorderedSetIterator<_Key, _Hash, DOWNSIZE>;
  8. using aligned_pointer = typename aligned_storage<sizeof(_Key), alignof(_Key)>::type;
  9. friend UnorderedSetIterator<_Key, _Hash, DOWNSIZE>;
  10. struct bucket {
  11. unsigned int _hash;
  12. short int _dist;
  13. bool _last, _end;
  14. aligned_pointer _key_ptr;
  15. bucket() noexcept : _dist(-1), _last(false), _end(false){}
  16. bucket& operator=(const bucket& another) noexcept {
  17. _hash = another._hash, _dist = another._dist, _last = another._last, _end = another._end;
  18. if(!another.empty()){
  19. new(&_key_ptr) _Key(*reinterpret_cast<const _Key*>(&another._key_ptr));
  20. }
  21. return *this;
  22. }
  23. ~bucket(){ if(!empty()) key_ptr()->~_Key(); }
  24. inline void clear() noexcept { _dist = -1; }
  25. inline void _delete(){ _dist = -1, key_ptr()->~_Key(); }
  26. inline bool empty() const noexcept { return (_dist == -1); }
  27. inline _Key& key() noexcept {
  28. return *reinterpret_cast<_Key*>(&_key_ptr);
  29. }
  30. inline _Key* key_ptr() noexcept {
  31. return reinterpret_cast<_Key*>(&_key_ptr);
  32. }
  33. inline void new_key(_Key&& key){
  34. new(&_key_ptr) _Key(move(key));
  35. }
  36. };
  37. inline static unsigned int ceilpow2(unsigned int u) noexcept {
  38. if(u == 0u) return 0u;
  39. --u, u |= u >> 1, u |= u >> 2, u |= u >> 4, u |= u >> 8;
  40. return (u | (u >> 16)) + 1;
  41. }
  42. inline static bucket *increment(bucket *cur) noexcept {
  43. for(++cur; !cur->_end; ++cur){
  44. if(!cur->empty()) break;
  45. }
  46. return cur;
  47. }
  48. inline bucket *next_bucket(bucket *cur) const noexcept {
  49. return cur->_last ? _buckets : cur + 1;
  50. }
  51. inline unsigned int make_hash(const _Key& key) const noexcept {
  52. return _Hash()(key);
  53. }
  54. inline float load_rate() const noexcept {
  55. return (float)_data_count / _bucket_count;
  56. }
  57. bucket *insert(bucket *cur, unsigned int hash, short int dist, _Key&& key){
  58. bucket *ret = cur;
  59. bool flag = false;
  60. while(true){
  61. if(cur->empty()){
  62. cur->_hash = hash, cur->_dist = dist, cur->new_key(move(key));
  63. if(!flag) ret = cur, flag = true;
  64. break;
  65. }else if(dist > cur->_dist){
  66. swap(hash, cur->_hash), swap(dist, cur->_dist), swap(key, cur->key());
  67. if(!flag) ret = cur, flag = true;
  68. }
  69. ++dist;
  70. cur = next_bucket(cur);
  71. }
  72. return ret;
  73. }
  74. bucket *_find(const _Key& key) const {
  75. unsigned int hash = make_hash(key);
  76. bucket *cur = _buckets + (hash & _mask);
  77. short int dist = 0;
  78. while(dist <= cur->_dist){
  79. if(hash == cur->_hash && key == cur->key()) return cur;
  80. ++dist, cur = next_bucket(cur);
  81. }
  82. return _buckets + _bucket_count;
  83. }
  84. template<class Key>
  85. bucket *find_insert(Key&& key){
  86. unsigned int hash = make_hash(key);
  87. bucket *cur = _buckets + (hash & _mask);
  88. short int dist = 0;
  89. while(dist <= cur->_dist){
  90. if(hash == cur->_hash && key == cur->key()) return cur;
  91. ++dist, cur = next_bucket(cur);
  92. }
  93. ++_data_count;
  94. if(rehash_check()){
  95. cur = _buckets + (hash & _mask), dist = 0;
  96. }
  97. _Key new_key = forward<Key>(key);
  98. return insert(cur, hash, dist, move(new_key));
  99. }
  100. template<typename... Args>
  101. bucket *emplace(Args&&... args){
  102. return find_insert(_Key(forward<Args>(args)...));
  103. }
  104. bucket *backward_shift(bucket *cur, bool next_ret){
  105. bucket *next = next_bucket(cur), *ret = cur;
  106. if(next->_dist < 1) return next_ret ? increment(cur) : cur;
  107. do {
  108. cur->_hash = next->_hash, cur->_dist = next->_dist - 1;
  109. cur->new_key(move(next->key()));
  110. cur = next, next = next_bucket(cur);
  111. }while(next->_dist >= 1);
  112. cur->clear();
  113. return ret;
  114. }
  115. bucket *erase_impl(bucket *cur, bool next_ret){
  116. assert(static_cast<size_t>(cur - _buckets) != _bucket_count);
  117. cur->_delete();
  118. --_data_count;
  119. return backward_shift(cur, next_ret);
  120. }
  121. bucket *erase_itr(bucket *cur, bool next_ret = true){
  122. const _Key key = cur->key();
  123. return erase_impl(rehash_check() ? _find(key) : cur, next_ret);
  124. }
  125. size_t erase_key(const _Key& key){
  126. rehash_check();
  127. bucket *cur = _find(key);
  128. if(static_cast<size_t>(cur - _buckets) == _bucket_count){
  129. return 0;
  130. }else{
  131. erase_impl(cur, false);
  132. return 1;
  133. }
  134. }
  135. bool rehash_check(){
  136. if(_bucket_count == 0){
  137. rehash(1u);
  138. return true;
  139. }else if(load_rate() >= MAX_LOAD_RATE){
  140. rehash(_bucket_count * 2u);
  141. return true;
  142. }else if(DOWNSIZE){
  143. if(load_rate() <= MIN_LOAD_RATE && _bucket_count >= DOWNSIZE_THRESHOLD){
  144. rehash(_bucket_count / 2u);
  145. return true;
  146. }
  147. }
  148. return false;
  149. }
  150. void move_data(bucket *cur){
  151. insert(_buckets + (cur->_hash & _mask), cur->_hash, 0, move(cur->key()));
  152. }
  153. void rehash(unsigned int new_bucket_count){
  154. UnorderedSet new_unordered_set(new_bucket_count);
  155. new_unordered_set._data_count = _data_count;
  156. for(bucket *cur = _buckets; !cur->_end; ++cur){
  157. if(!cur->empty()){
  158. new_unordered_set.move_data(cur);
  159. }
  160. }
  161. swap(*this, new_unordered_set);
  162. }
  163. friend void swap(UnorderedSet& ust1, UnorderedSet& ust2){
  164. swap(ust1._bucket_count, ust2._bucket_count);
  165. swap(ust1._mask, ust2._mask);
  166. swap(ust1._data_count, ust2._data_count);
  167. swap(ust1._buckets, ust2._buckets);
  168. }
  169.  
  170. private:
  171. unsigned int _bucket_count, _mask, _data_count;
  172. bucket *_buckets;
  173. public:
  174. const float MAX_LOAD_RATE = 0.5f;
  175. const float MIN_LOAD_RATE = 0.1f;
  176. const unsigned int DOWNSIZE_THRESHOLD = 16u;
  177. UnorderedSet(unsigned int bucket_size = 0u)
  178. : _bucket_count(ceilpow2(bucket_size)), _mask(_bucket_count - 1),
  179. _data_count(0u), _buckets(new bucket[_bucket_count + 1]){
  180. if(_bucket_count > 0) _buckets[_bucket_count - 1]._last = true;
  181. else _mask = 0;
  182. _buckets[_bucket_count]._end = true;
  183. }
  184. UnorderedSet(const UnorderedSet& another)
  185. : _bucket_count(another._bucket_count), _mask(another._mask), _data_count(another._data_count){
  186. _buckets = new bucket[_bucket_count + 1u];
  187. for(unsigned int i = 0u; i <= _bucket_count; ++i){
  188. _buckets[i] = another._buckets[i];
  189. }
  190. }
  191. UnorderedSet(UnorderedSet&& another)
  192. : _bucket_count(move(another._bucket_count)), _mask(move(another._mask)),
  193. _data_count(move(another._data_count)), _buckets(another._buckets){
  194. another._buckets = nullptr;
  195. }
  196. UnorderedSet& operator=(const UnorderedSet& another){
  197. delete[] _buckets;
  198. _bucket_count = another._bucket_count;
  199. _mask = another._mask;
  200. _data_count = another._data_count;
  201. _buckets = new bucket[_bucket_count + 1u];
  202. for(unsigned int i = 0u; i <= _bucket_count; ++i){
  203. _buckets[i] = another._buckets[i];
  204. }
  205. return *this;
  206. }
  207. UnorderedSet& operator=(UnorderedSet&& another){
  208. delete[] _buckets;
  209. _bucket_count = move(another._bucket_count);
  210. _mask = move(another._mask);
  211. _data_count = move(another._data_count);
  212. _buckets = another._buckets;
  213. another._buckets = nullptr;
  214. return *this;
  215. }
  216. void allocate(unsigned int element_size){
  217. rehash(ceilpow2(ceil(element_size / MAX_LOAD_RATE) + 1));
  218. }
  219. ~UnorderedSet(){ delete[] _buckets; }
  220. friend ostream& operator<< (ostream& os, UnorderedSet& ust) noexcept {
  221. for(_Key& val : ust) os << val << " ";
  222. return os;
  223. }
  224. void clear(){
  225. UnorderedSet new_unordered_set(0u);
  226. swap(*this, new_unordered_set);
  227. }
  228. size_t size() const noexcept { return _data_count; }
  229. size_t bucket_count() const noexcept { return _bucket_count; }
  230. bool empty() const noexcept { return (_data_count == 0); }
  231. iterator begin() noexcept {
  232. return (_buckets->empty() && _bucket_count > 0) ? iterator(increment(_buckets)) : iterator(_buckets);
  233. }
  234. iterator end() noexcept { return iterator(_buckets + _bucket_count); }
  235. iterator find(const _Key& key) const { return iterator(_find(key)); }
  236. size_t count(const _Key& key) const { return (_find(key) != _buckets + _bucket_count); }
  237. iterator insert(const _Key& key){ return iterator(find_insert(key)); }
  238. iterator insert(_Key&& key){ return iterator(find_insert(move(key))); }
  239. template<typename... Args>
  240. iterator emplace(Args&&... args){ return iterator(_emplace(forward<Args>(args)...)); }
  241. size_t erase(const _Key& key){ return erase_key(key); }
  242. iterator erase(const iterator& itr){ return iterator(erase_itr(itr.bucket_ptr)); }
  243. void simple_erase(const _Key& key){ erase_key(key); }
  244. void simple_erase(const iterator& itr){ erase_itr(itr.bucket_ptr, false); }
  245.  
  246. // DEBUG 用
  247. short int maximum_distance() const noexcept {
  248. short int ret = -1;
  249. for(bucket *cur = _buckets; !cur->_end; ++cur){
  250. ret = max(ret, cur->_dist);
  251. }
  252. return ret;
  253. }
  254. };
  255.  
  256. template<class _Key, class _Hash, bool DOWNSIZE>
  257. class UnorderedSetIterator {
  258. private:
  259. friend UnorderedSet<_Key, _Hash, DOWNSIZE>;
  260. typename UnorderedSet<_Key, _Hash, DOWNSIZE>::bucket *bucket_ptr;
  261. using iterator_category = forward_iterator_tag;
  262. using value_type = _Key;
  263. using difference_type = ptrdiff_t;
  264. using pointer = _Key*;
  265. using reference = _Key&;
  266.  
  267. private:
  268. UnorderedSetIterator(typename UnorderedSet<_Key, _Hash, DOWNSIZE>::bucket *_bucket_ptr)
  269. noexcept : bucket_ptr(_bucket_ptr){}
  270. public:
  271. UnorderedSetIterator() noexcept : bucket_ptr(){}
  272. UnorderedSetIterator(const UnorderedSetIterator& itr) noexcept : bucket_ptr(itr.bucket_ptr){}
  273. UnorderedSetIterator& operator=(const UnorderedSetIterator& itr)
  274. & noexcept { return bucket_ptr = itr.bucket_ptr, *this; }
  275. UnorderedSetIterator& operator=(const UnorderedSetIterator&& itr)
  276. & noexcept { return bucket_ptr = itr.bucket_ptr, *this; }
  277. reference operator*() const noexcept { return bucket_ptr->key(); }
  278. pointer operator->() const noexcept { return bucket_ptr->key_ptr(); }
  279. UnorderedSetIterator& operator++() noexcept {
  280. return bucket_ptr = UnorderedSet<_Key, _Hash, DOWNSIZE>::increment(bucket_ptr), *this;
  281. }
  282. UnorderedSetIterator operator++(int) const noexcept {
  283. return UnorderedSetIterator(UnorderedSet<_Key, _Hash, DOWNSIZE>::increment(this->bucket_ptr));
  284. }
  285. bool operator==(const UnorderedSetIterator& itr) const noexcept { return !(*this != itr); };
  286. bool operator!=(const UnorderedSetIterator& itr) const noexcept { return bucket_ptr != itr.bucket_ptr; }
  287. };

コード(高速版)

  1. template<class _Key, class _Hash, bool DOWNSIZE> class UnorderedSetIterator;
  2.  
  3. template<class _Key, class _Hash = hash<_Key>, bool DOWNSIZE = false>
  4. class UnorderedSet
  5. {
  6. private:
  7. using iterator = UnorderedSetIterator<_Key, _Hash, DOWNSIZE>;
  8. friend UnorderedSetIterator<_Key, _Hash, DOWNSIZE>;
  9. struct bucket {
  10. _Key _key;
  11. short int _dist;
  12. bool _last, _end;
  13. bucket() noexcept : _dist(-1), _last(false), _end(false){}
  14. bucket& operator=(const bucket& another) = default;
  15. ~bucket(){ if(!empty()) _key.~_Key(); }
  16. inline void clear() noexcept { _dist = -1; }
  17. inline void _delete(){ _dist = -1, _key.~_Key(); }
  18. inline bool empty() const noexcept { return (_dist == -1); }
  19. };
  20. inline static unsigned int ceilpow2(unsigned int u) noexcept {
  21. if(u == 0u) return 0u;
  22. --u, u |= u >> 1, u |= u >> 2, u |= u >> 4, u |= u >> 8;
  23. return (u | (u >> 16)) + 1;
  24. }
  25. inline static bucket *increment(bucket *cur) noexcept {
  26. for(++cur; !cur->_end; ++cur){
  27. if(!cur->empty()) break;
  28. }
  29. return cur;
  30. }
  31. inline bucket *next_bucket(bucket *cur) const noexcept {
  32. return cur->_last ? _buckets : cur + 1;
  33. }
  34. inline unsigned int make_hash(const _Key& key) const noexcept {
  35. return _Hash()(key);
  36. }
  37. inline float load_rate() const noexcept {
  38. return (float)_data_count / _bucket_count;
  39. }
  40. bucket *insert(bucket *cur, short int dist, _Key&& key){
  41. bucket *ret = cur;
  42. bool flag = false;
  43. while(true){
  44. if(cur->empty()){
  45. cur->_key = move(key), cur->_dist = dist;
  46. if(!flag) ret = cur, flag = true;
  47. break;
  48. }else if(dist > cur->_dist){
  49. swap(key, cur->_key), swap(dist, cur->_dist);
  50. if(!flag) ret = cur, flag = true;
  51. }
  52. ++dist;
  53. cur = next_bucket(cur);
  54. }
  55. return ret;
  56. }
  57. bucket *_find(const _Key& key) const {
  58. bucket *cur = _buckets + (make_hash(key) & _mask);
  59. int dist = 0;
  60. while(dist <= cur->_dist){
  61. if(key == cur->_key) return cur;
  62. ++dist, cur = next_bucket(cur);
  63. }
  64. return _buckets + _bucket_count;
  65. }
  66. template<class Key>
  67. bucket *find_insert(Key&& key){
  68. unsigned int hash = make_hash(key);
  69. bucket *cur = _buckets + (hash & _mask);
  70. int dist = 0;
  71. while(dist <= cur->_dist){
  72. if(key == cur->_key) return cur;
  73. ++dist, cur = next_bucket(cur);
  74. }
  75. ++_data_count;
  76. if(rehash_check()){
  77. cur = _buckets + (hash & _mask), dist = 0;
  78. }
  79. _Key new_key = forward<Key>(key);
  80. return insert(cur, dist, move(new_key));
  81. }
  82. template<typename... Args>
  83. bucket *emplace(Args&&... args){
  84. return find_insert(_Key(forward<Args>(args)...));
  85. }
  86. bucket *backward_shift(bucket *cur, bool next_ret){
  87. bucket *next = next_bucket(cur), *ret = cur;
  88. if(next->_dist < 1) return next_ret ? increment(cur) : cur;
  89. do {
  90. cur->_key = next->_key, cur->_dist = next->_dist - 1;
  91. cur = next, next = next_bucket(cur);
  92. }while(next->_dist >= 1);
  93. cur->clear();
  94. return ret;
  95. }
  96. bucket *erase_impl(bucket *cur, bool next_ret){
  97. assert(static_cast<size_t>(cur - _buckets) != _bucket_count);
  98. cur->_delete();
  99. --_data_count;
  100. return backward_shift(cur, next_ret);
  101. }
  102. bucket *erase_itr(bucket *cur, bool next_ret = true){
  103. const _Key key = cur->_key;
  104. return erase_impl(rehash_check() ? _find(key) : cur, next_ret);
  105. }
  106. size_t erase_key(const _Key& key){
  107. rehash_check();
  108. bucket *cur = _find(key);
  109. if(static_cast<size_t>(cur - _buckets) == _bucket_count){
  110. return 0;
  111. }else{
  112. erase_impl(cur, false);
  113. return 1;
  114. }
  115. }
  116. bool rehash_check(){
  117. if(_bucket_count == 0){
  118. rehash(1u);
  119. return true;
  120. }else if(load_rate() >= MAX_LOAD_RATE){
  121. rehash(_bucket_count * 2u);
  122. return true;
  123. }else if(DOWNSIZE){
  124. if(load_rate() <= MIN_LOAD_RATE && _bucket_count >= DOWNSIZE_THRESHOLD){
  125. rehash(_bucket_count / 2u);
  126. return true;
  127. }
  128. }
  129. return false;
  130. }
  131. void move_data(bucket *cur){
  132. insert(_buckets + (make_hash(cur->_key) & _mask), 0, move(cur->_key));
  133. }
  134. void rehash(unsigned int new_bucket_count){
  135. UnorderedSet new_unordered_set(new_bucket_count);
  136. new_unordered_set._data_count = _data_count;
  137. for(bucket *cur = _buckets; !cur->_end; ++cur){
  138. if(!cur->empty()){
  139. new_unordered_set.move_data(cur);
  140. }
  141. }
  142. swap(*this, new_unordered_set);
  143. }
  144. friend void swap(UnorderedSet& ust1, UnorderedSet& ust2){
  145. swap(ust1._bucket_count, ust2._bucket_count);
  146. swap(ust1._mask, ust2._mask);
  147. swap(ust1._data_count, ust2._data_count);
  148. swap(ust1._buckets, ust2._buckets);
  149. }
  150.  
  151. private:
  152. unsigned int _bucket_count, _mask, _data_count;
  153. bucket *_buckets;
  154. public:
  155. const float MAX_LOAD_RATE = 0.5f;
  156. const float MIN_LOAD_RATE = 0.1f;
  157. const unsigned int DOWNSIZE_THRESHOLD = 16u;
  158. UnorderedSet(unsigned int bucket_size = 0u)
  159. : _bucket_count(ceilpow2(bucket_size)), _mask(_bucket_count - 1),
  160. _data_count(0u), _buckets(new bucket[_bucket_count + 1]){
  161. if(_bucket_count > 0) _buckets[_bucket_count - 1]._last = true;
  162. else _mask = 0;
  163. _buckets[_bucket_count]._end = true;
  164. }
  165. UnorderedSet(const UnorderedSet& another)
  166. : _bucket_count(another._bucket_count), _mask(another._mask), _data_count(another._data_count){
  167. _buckets = new bucket[_bucket_count + 1u];
  168. for(unsigned int i = 0u; i <= _bucket_count; ++i){
  169. _buckets[i] = another._buckets[i];
  170. }
  171. }
  172. UnorderedSet(UnorderedSet&& another)
  173. : _bucket_count(move(another._bucket_count)), _mask(move(another._mask)),
  174. _data_count(move(another._data_count)), _buckets(another._buckets){
  175. another._buckets = nullptr;
  176. }
  177. UnorderedSet& operator=(const UnorderedSet& another){
  178. delete[] _buckets;
  179. _bucket_count = another._bucket_count;
  180. _mask = another._mask;
  181. _data_count = another._data_count;
  182. _buckets = new bucket[_bucket_count + 1u];
  183. for(unsigned int i = 0u; i <= _bucket_count; ++i){
  184. _buckets[i] = another._buckets[i];
  185. }
  186. return *this;
  187. }
  188. UnorderedSet& operator=(UnorderedSet&& another){
  189. delete[] _buckets;
  190. _bucket_count = move(another._bucket_count);
  191. _mask = move(another._mask);
  192. _data_count = move(another._data_count);
  193. _buckets = another._buckets;
  194. another._buckets = nullptr;
  195. return *this;
  196. }
  197. void allocate(unsigned int element_size){
  198. rehash(ceilpow2(ceil(element_size / MAX_LOAD_RATE) + 1));
  199. }
  200. ~UnorderedSet(){ delete[] _buckets; }
  201. friend ostream& operator<< (ostream& os, UnorderedSet& ust) noexcept {
  202. for(_Key& val : ust) os << val << " ";
  203. return os;
  204. }
  205. void clear(){
  206. UnorderedSet new_unordered_set(0u);
  207. swap(*this, new_unordered_set);
  208. }
  209. size_t size() const noexcept { return _data_count; }
  210. size_t bucket_count() const noexcept { return _bucket_count; }
  211. bool empty() const noexcept { return (_data_count == 0); }
  212. iterator begin() noexcept {
  213. return (_buckets->empty() && _bucket_count > 0) ? iterator(increment(_buckets)) : iterator(_buckets);
  214. }
  215. iterator end() noexcept { return iterator(_buckets + _bucket_count); }
  216. iterator find(const _Key& key) const { return iterator(_find(key)); }
  217. size_t count(const _Key& key) const { return (_find(key) != _buckets + _bucket_count); }
  218. iterator insert(const _Key& key){ return iterator(find_insert(key)); }
  219. iterator insert(_Key&& key){ return iterator(find_insert(move(key))); }
  220. template<typename... Args>
  221. iterator emplace(Args&&... args){ return iterator(_emplace(forward<Args>(args)...)); }
  222. size_t erase(const _Key& key){ return erase_key(key); }
  223. iterator erase(const iterator& itr){ return iterator(erase_itr(itr.bucket_ptr)); }
  224. void simple_erase(const _Key& key){ erase_key(key); }
  225. void simple_erase(const iterator& itr){ erase_itr(itr.bucket_ptr, false); }
  226.  
  227. // DEBUG 用
  228. short int maximum_distance() const noexcept {
  229. short int ret = -1;
  230. for(bucket *cur = _buckets; !cur->_end; ++cur){
  231. ret = max(ret, cur->_dist);
  232. }
  233. return ret;
  234. }
  235. };
  236.  
  237. template<class _Key, class _Hash, bool DOWNSIZE>
  238. class UnorderedSetIterator {
  239. private:
  240. friend UnorderedSet<_Key, _Hash, DOWNSIZE>;
  241. typename UnorderedSet<_Key, _Hash, DOWNSIZE>::bucket *bucket_ptr;
  242. using iterator_category = forward_iterator_tag;
  243. using value_type = _Key;
  244. using difference_type = ptrdiff_t;
  245. using pointer = _Key*;
  246. using reference = _Key&;
  247.  
  248. private:
  249. UnorderedSetIterator(typename UnorderedSet<_Key, _Hash, DOWNSIZE>::bucket *_bucket_ptr)
  250. noexcept : bucket_ptr(_bucket_ptr){}
  251. public:
  252. UnorderedSetIterator() noexcept : bucket_ptr(){}
  253. UnorderedSetIterator(const UnorderedSetIterator& itr) noexcept : bucket_ptr(itr.bucket_ptr){}
  254. UnorderedSetIterator& operator=(const UnorderedSetIterator& itr)
  255. & noexcept { return bucket_ptr = itr.bucket_ptr, *this; }
  256. UnorderedSetIterator& operator=(const UnorderedSetIterator&& itr)
  257. & noexcept { return bucket_ptr = itr.bucket_ptr, *this; }
  258. reference operator*() const noexcept { return bucket_ptr->_key; }
  259. pointer operator->() const noexcept { return &(bucket_ptr->_key); }
  260. UnorderedSetIterator& operator++() noexcept {
  261. return bucket_ptr = UnorderedSet<_Key, _Hash, DOWNSIZE>::increment(bucket_ptr), *this;
  262. }
  263. UnorderedSetIterator operator++(int) const noexcept {
  264. return UnorderedSetIterator(UnorderedSet<_Key, _Hash, DOWNSIZE>::increment(this->bucket_ptr));
  265. }
  266. bool operator==(const UnorderedSetIterator& itr) const noexcept { return !(*this != itr); };
  267. bool operator!=(const UnorderedSetIterator& itr) const noexcept { return bucket_ptr != itr.bucket_ptr; }
  268. };

verify 用の問題

AOJ : Set - Set: Delete 提出コード 提出コード(高速版)