Processing math: 100%
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 提出コード 提出コード(高速版)