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

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

Unordered Map

コードについての説明(個人的メモ)

hash を用いた連想配列クラスの実装である. std::unordered_map は (参考 1), (参考 2) にあるように実行速度が遅いことが知られている. そこでこれらのベンチマークで良い性能を示している robin hood hashing を用いた unordered_map の実装を行ってみた.
以下の実装はある程度 std::unordered_map と同様に動作するが, 実装していない関数もある. 自作のハッシュ関数を使う場合は第 $3$ テンプレート引数として与える. 第 4 引数については最後に書く. デフォルトでは std::hash を用いてますが本実装においては MOD を 2 べきで取っている仕様上簡単に 衝突しまくる ので こちら を参考に murmur hash などましなハッシュ関数を引数として与えることを とてもおすすめする(例えば key として 2 べきの値がたくさん来る場合はすべて衝突します).
速度を重視したので rehash が起きると イテレーター破壊 が起きる!!(逆に言えば find, insert, erase などの操作をしなければイテレーター破壊は起きません.)
実装は普通のコードと高速版のコードが置いてあり, 高速版の方はメモリ効率をよくするためハッシュ値を保持せず毎回キー値を比較しているので int 型や long long 型などに対してのみ用いる(具体的には一致判定が高速にできるような型に対して用いる). つまりキー値に string などを用いる場合は $1$ つ目のコードを使う.
simple_erase は要素を erase したあとに次の要素へのイテレーターを返さない erase で後述のようにバケットのサイズの縮小を行わないとバケット数に対して要素数が少ないとき erase された要素の次の要素を見つけるのにとても時間がかかることがあるのでそれを避けるために用いることができる.
(注) MAX_LOAD_RATE((要素数)/(バケット数) の最大値), MIN_LOAD_RATE((要素数)/(バケット数) の最小値(DOWNSIZE の場合にのみ有効)), DOWNSIZE_THRESHOLD(バケットの縮小を行う際の最低のバケット数) はヒューリスティックに決めている.
第 $4$ 引数の DOWNSIZE は rehash でバケット数の拡大だけでなく縮小も行うかどうかを表している. つまりバケット数に対して要素数が少ないときにバケットのサイズを縮小させるかどうかを決めることができる. unordered_map を for_each でなめたり, erase したりなどは要素数だけでなくバケット数にも比例するので, バケットサイズの縮小をしないととても速度が遅くなることがあったので用意した.
まあまあ verify はしたが, 変な使い方をするとおかしな挙動をするかもしれない.

コード

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

コード(高速版) (キー値比較が高速な型に対して用いる. 具体的にはキー値が int や long long などの場合)

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

verify 用の問題

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