/* This file is part of Fennix Kernel. Fennix Kernel is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Fennix Kernel is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Fennix Kernel. If not, see <https://www.gnu.org/licenses/>. */ #pragma once #include <initializer_list> #include <functional> #include <stdexcept> #include <algorithm> #include <iterator> #include <utility> #include <vector> #include <memory> #include <cmath> #include <list> namespace std { template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<std::pair<const Key, T>>> class unordered_multimap; template <class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<std::pair<const Key, T>>> class unordered_map { public: using key_type = Key; using mapped_type = T; using value_type = std::pair<const Key, T>; using size_type = std::size_t; using difference_type = std::ptrdiff_t; using hasher = Hash; using key_equal = KeyEqual; using allocator_type = Allocator; using reference = value_type &; using const_reference = const value_type &; using pointer = typename std::allocator_traits<Allocator>::pointer; using const_pointer = typename std::allocator_traits<Allocator>::const_pointer; // using iterator = typename std::vector<std::list<value_type>>::iterator; // using const_iterator = typename std::vector<std::list<value_type>>::const_iterator; // using local_iterator = typename std::list<value_type>::iterator; // using const_local_iterator = typename std::list<value_type>::const_iterator; using node_type = std::list<value_type>; template <class Iter, class NodeType> struct __insert_return_type { Iter position; bool inserted; NodeType node; }; class iterator { friend class unordered_map; public: using difference_type = std::ptrdiff_t; using value_type = std::pair<const Key, T>; using pointer = value_type *; using reference = value_type &; using iterator_category = std::bidirectional_iterator_tag; private: std::vector<node_type> &buckets; std::vector<std::list<value_type>>::iterator bucket; std::list<value_type>::iterator element; public: iterator(std::vector<node_type> &buckets, std::vector<std::list<value_type>>::iterator bucket, std::list<value_type>::iterator element) : buckets(buckets), bucket(bucket), element(element) { } iterator &operator++() { if (element != bucket->end()) ++element; if (element == bucket->end()) { ++bucket; while (bucket != buckets.end() && bucket->empty()) ++bucket; if (bucket != buckets.end()) element = bucket->begin(); } return *this; } iterator operator++(int) { auto copy = *this; ++(*this); return copy; } iterator &operator--() { if (element != bucket->begin()) --element; if (element == bucket->begin()) { --bucket; while (bucket != buckets.begin() && bucket->empty()) --bucket; if (bucket != buckets.begin()) element = --bucket->end(); } return *this; } iterator operator--(int) { auto copy = *this; --(*this); return copy; } reference operator*() { return *element; } const_reference operator*() const { return *element; } pointer operator->() { return &(*element); } const_pointer operator->() const { return &(*element); } bool operator==(const iterator &other) const { return bucket == other.bucket && element == other.element; } bool operator!=(const iterator &other) const { return !(*this == other); } }; class const_iterator { friend class unordered_map; public: using difference_type = std::ptrdiff_t; using value_type = std::pair<const Key, T>; using pointer = const value_type *; using reference = const value_type &; using iterator_category = std::bidirectional_iterator_tag; private: const std::vector<node_type> &buckets; std::vector<std::list<value_type>>::const_iterator bucket; std::list<value_type>::const_iterator element; public: const_iterator(const std::vector<node_type> &buckets, std::vector<std::list<value_type>>::const_iterator bucket, std::list<value_type>::const_iterator element) : buckets(buckets), bucket(bucket), element(element) { } const_iterator(const iterator &it) : bucket(it.bucket), element(it.element) { } const_iterator &operator++() { if (element != bucket->end()) ++element; if (element == bucket->end()) { ++bucket; while (bucket != buckets.end() && bucket->empty()) ++bucket; if (bucket != buckets.end()) element = bucket->begin(); } return *this; } const_iterator operator++(int) { auto copy = *this; ++(*this); return copy; } const_iterator &operator--() { if (element != bucket->begin()) --element; if (element == bucket->begin()) { --bucket; while (bucket != buckets.begin() && bucket->empty()) --bucket; if (bucket != buckets.begin()) element = --bucket->end(); } return *this; } const_iterator operator--(int) { auto copy = *this; --(*this); return copy; } reference operator*() const { return *element; } pointer operator->() const { return &(*element); } bool operator==(const const_iterator &other) const { return bucket == other.bucket && element == other.element; } bool operator!=(const const_iterator &other) const { return !(*this == other); } }; class local_iterator { friend class unordered_map; public: using difference_type = std::ptrdiff_t; using value_type = std::pair<const Key, T>; using pointer = value_type *; using reference = value_type &; using iterator_category = std::bidirectional_iterator_tag; private: std::list<value_type>::iterator element; public: local_iterator(std::list<value_type>::iterator element) : element(element) { } local_iterator &operator++() { ++element; return *this; } local_iterator operator++(int) { auto copy = *this; ++(*this); return copy; } local_iterator &operator--() { --element; return *this; } local_iterator operator--(int) { auto copy = *this; --(*this); return copy; } reference operator*() { return *element; } pointer operator->() { return &(*element); } bool operator==(const local_iterator &other) const { return element == other.element; } bool operator!=(const local_iterator &other) const { return !(*this == other); } }; class const_local_iterator { friend class unordered_map; public: using difference_type = std::ptrdiff_t; using value_type = std::pair<const Key, T>; using pointer = const value_type *; using reference = const value_type &; using iterator_category = std::bidirectional_iterator_tag; private: std::list<value_type>::const_iterator element; public: const_local_iterator(std::list<value_type>::const_iterator element) : element(element) { } const_local_iterator &operator++() { ++element; return *this; } const_local_iterator operator++(int) { auto copy = *this; ++(*this); return copy; } const_local_iterator &operator--() { --element; return *this; } const_local_iterator operator--(int) { auto copy = *this; --(*this); return copy; } reference operator*() const { return *element; } pointer operator->() const { return &(*element); } bool operator==(const const_local_iterator &other) const { return element == other.element; } bool operator!=(const const_local_iterator &other) const { return !(*this == other); } }; using insert_return_type = __insert_return_type<iterator, node_type>; private: std::vector<node_type> buckets; Hash hashFunction; double maxLoadFactor = 0.75; size_type elementsCount = 0; public: #pragma region Constructors unordered_map() = default; unordered_map(const unordered_map &other) : buckets(other.buckets) { } unordered_map(unordered_map &&other) : buckets(std::move(other.buckets)) { } unordered_map(std::initializer_list<value_type> il) { insert(il); } ~unordered_map() = default; unordered_map &operator=(const unordered_map &other) { buckets = other.buckets; return *this; } unordered_map &operator=(unordered_map &&other) /* noexcept(std::allocator_traits<Allocator>::is_always_equal::value && std::is_nothrow_move_assignable<Hash>::value && std::is_nothrow_move_assignable<Pred>::value) */ { buckets = std::move(other.buckets); return *this; } unordered_map &operator=(std::initializer_list<value_type> ilist) { clear(); insert(ilist); return *this; } allocator_type get_allocator() const noexcept { return allocator_type(); } #pragma endregion Constructors #pragma region Iterators iterator begin() noexcept { auto it = buckets.begin(); while (it != buckets.end() && it->empty()) ++it; return iterator(buckets, it, it == buckets.end() ? typename node_type::iterator() : it->begin()); } const_iterator begin() const noexcept { auto it = buckets.begin(); while (it != buckets.end() && it->empty()) ++it; return const_iterator(buckets, it, it == buckets.end() ? typename node_type::const_iterator() : it->begin()); } const_iterator cbegin() const noexcept { return begin(); } iterator end() noexcept { return iterator(buckets, buckets.end(), typename node_type::iterator()); } const_iterator end() const noexcept { return const_iterator(buckets, buckets.end(), typename node_type::const_iterator()); } const_iterator cend() const noexcept { return end(); } #pragma endregion Iterators #pragma region Capacity [[nodiscard]] bool empty() const noexcept { return elementsCount == 0; /* begin() == end() */ } size_type size() const noexcept { return elementsCount; /* std::distance(begin(), end()) */ } size_type max_size() const noexcept { return std::numeric_limits<difference_type>::max(); } #pragma endregion Capacity #pragma region Modifiers void clear() noexcept { for (auto &bucket : buckets) bucket.clear(); elementsCount = 0; } std::pair<iterator, bool> insert(const value_type &value) { if (buckets.empty()) rehash(16); size_type index = hashFunction(value.first) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == value.first) return std::make_pair(iterator(buckets, buckets.begin() + index, it), false); } bucket.push_back(value); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(value.first) % buckets.size(); } return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true); } std::pair<iterator, bool> insert(value_type &&value) { if (buckets.empty()) rehash(16); size_type index = hashFunction(value.first) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == value.first) return std::make_pair(iterator(buckets, buckets.begin() + index, it), false); } bucket.push_back(std::move(value)); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(value.first) % buckets.size(); } return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true); } template <class P> std::pair<iterator, bool> insert(P &&value) { if (buckets.empty()) rehash(16); size_type index = hashFunction(value.first) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == value.first) return std::make_pair(iterator(buckets, buckets.begin() + index, it), false); } bucket.push_back(std::forward<P>(value)); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(value.first) % buckets.size(); } return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true); } iterator insert(const_iterator hint, const value_type &value) { fixme("hint %p", &hint); return insert(value).first; } iterator insert(const_iterator hint, value_type &&value) { fixme("hint %p", &hint); return insert(std::move(value)).first; } template <class P> iterator insert(const_iterator hint, P &&value) { fixme("hint %p", &hint); return insert(std::forward<P>(value)).first; } template <class InputIt> void insert(InputIt first, InputIt last) { for (auto it = first; it != last; ++it) insert(*it); } void insert(std::initializer_list<value_type> ilist) { for (const auto &value : ilist) insert(value); } insert_return_type insert(node_type &&nh) { if (buckets.empty()) rehash(16); size_type index = hashFunction(nh.front().first) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == nh.front().first) return {iterator(buckets, buckets.begin() + index, it), false, std::move(nh)}; } bucket.splice(bucket.end(), nh); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(nh.front().first) % buckets.size(); } return {iterator(buckets, buckets.begin() + index, --bucket.end()), true, std::move(nh)}; } iterator insert(const_iterator hint, node_type &&nh) { fixme("hint %p", &hint); return insert(std::move(nh)).position; } template <class M> std::pair<iterator, bool> insert_or_assign(const Key &k, M &&obj) { if (auto it = find(k); it != end()) { it->second = std::forward<M>(obj); return std::make_pair(it, false); } if (buckets.empty()) rehash(16); size_type index = hashFunction(k) % buckets.size(); auto &bucket = buckets[index]; bucket.push_back(std::make_pair(k, std::forward<M>(obj))); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(k) % buckets.size(); } return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true); } template <class M> std::pair<iterator, bool> insert_or_assign(Key &&k, M &&obj) { if (auto it = find(k); it != end()) { it->second = std::forward<M>(obj); return std::make_pair(it, false); } if (buckets.empty()) rehash(16); size_type index = hashFunction(k) % buckets.size(); auto &bucket = buckets[index]; bucket.push_back(std::make_pair(std::move(k), std::forward<M>(obj))); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(k) % buckets.size(); } return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true); } template <class M> iterator insert_or_assign(const_iterator hint, const Key &k, M &&obj) { fixme("hint %p", &hint); return insert_or_assign(k, std::forward<M>(obj)).first; } template <class M> iterator insert_or_assign(const_iterator hint, Key &&k, M &&obj) { fixme("hint %p", &hint); return insert_or_assign(std::move(k), std::forward<M>(obj)).first; } template <class... Args> __deprecated_msg("Function not implemented") std::pair<iterator, bool> emplace(Args &&...args) { assert(!"std::tuple : Function not implemented"); // size_type index = hashFunction(std::get<0>(std::forward_as_tuple(args...))) % buckets.size(); // auto &bucket = buckets[index]; // for (auto it = bucket.begin(); it != bucket.end(); ++it) // { // if (it->first == std::get<0>(std::forward_as_tuple(args...))) // return std::make_pair(iterator(buckets, buckets.begin() + index, it), false); // } // bucket.push_back(std::make_pair(std::get<0>(std::forward_as_tuple(args...)), std::get<1>(std::forward_as_tuple(args...)))); // ++elementsCount; // if (elementsCount > max_load_factor() * buckets.size()) // { // rehash(buckets.size() * 2); // index = hashFunction(std::get<0>(std::forward_as_tuple(args...))) % buckets.size(); // } // return std::make_pair(iterator(buckets, buckets.begin() + index, --bucket.end()), true); } template <class... Args> __deprecated_msg("Function not implemented") iterator emplace_hint(const_iterator hint, Args &&...args) { fixme("hint %p", &hint); return emplace(std::forward<Args>(args)...).first; } template <class... Args> __deprecated_msg("Function not implemented") std::pair<iterator, bool> try_emplace(const Key &k, Args &&...args) { assert(!"Function not implemented"); } template <class... Args> __deprecated_msg("Function not implemented") std::pair<iterator, bool> try_emplace(Key &&k, Args &&...args) { assert(!"Function not implemented"); } template <class K, class... Args> __deprecated_msg("Function not implemented") std::pair<iterator, bool> try_emplace(K &&k, Args &&...args) { assert(!"Function not implemented"); } template <class... Args> __deprecated_msg("Function not implemented") iterator try_emplace(const_iterator hint, const Key &k, Args &&...args) { assert(!"Function not implemented"); } template <class... Args> __deprecated_msg("Function not implemented") iterator try_emplace(const_iterator hint, Key &&k, Args &&...args) { assert(!"Function not implemented"); } template <class K, class... Args> __deprecated_msg("Function not implemented") iterator try_emplace(const_iterator hint, K &&k, Args &&...args) { assert(!"Function not implemented"); } iterator erase(iterator pos) { auto &bucket = *pos.bucket; auto it = bucket.erase(pos.element); --elementsCount; return iterator(buckets, pos.bucket, it); } __deprecated_msg("Function not implemented") iterator erase(const_iterator pos) { assert(!"Function not implemented"); // auto &bucket = *pos.bucket; // auto it = bucket.erase(pos.element); // --elementsCount; // return iterator(pos.bucket, it); } __deprecated_msg("Function not implemented") iterator erase(const_iterator first, const_iterator last) { assert(!"Function not implemented"); // for (auto it = first; it != last; ++it) // erase(it); // return iterator(last.bucket, last.element); } size_type erase(const Key &key) { if (buckets.empty()) return 0; size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) { bucket.erase(it); --elementsCount; return 1; } } return 0; } void swap(unordered_map &other) /* noexcept(std::allocator_traits<Allocator>::is_always_equal::value && std::is_nothrow_swappable<Hash>::value && std::is_nothrow_swappable<key_equal>::value) */ { std::swap(buckets, other.buckets); } __deprecated_msg("Function not implemented") node_type extract(const_iterator position) { assert(!"Function not implemented"); } __deprecated_msg("Function not implemented") node_type extract(const Key &k) { assert(!"Function not implemented"); } template <class H2, class P2> __deprecated_msg("Function not implemented") void merge(std::unordered_map<Key, T, H2, P2, Allocator> &source) { assert(!"Function not implemented"); } template <class H2, class P2> __deprecated_msg("Function not implemented") void merge(std::unordered_map<Key, T, H2, P2, Allocator> &&source) { assert(!"Function not implemented"); } template <class H2, class P2> __deprecated_msg("Function not implemented") void merge(std::unordered_multimap<Key, T, H2, P2, Allocator> &source) { assert(!"Function not implemented"); } template <class H2, class P2> __deprecated_msg("Function not implemented") void merge(std::unordered_multimap<Key, T, H2, P2, Allocator> &&source) { assert(!"Function not implemented"); } #pragma endregion Modifiers #pragma region Lookup T &at(const Key &key) { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return it->second; } throw std::out_of_range("Key not found"); } const T &at(const Key &key) const { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return it->second; } throw std::out_of_range("Key not found"); } T &operator[](const Key &key) { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return it->second; } bucket.push_back(std::make_pair(key, T())); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(key) % buckets.size(); } bucket = buckets[index]; return bucket.back().second; } T &operator[](Key &&key) { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return it->second; } bucket.push_back(std::make_pair(std::move(key), T())); ++elementsCount; if (elementsCount > max_load_factor() * buckets.size()) { rehash(buckets.size() * 2); index = hashFunction(key) % buckets.size(); } bucket = buckets[index]; return bucket.back().second; } size_type count(const Key &key) const { if (buckets.empty()) return 0; size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return 1; } return 0; } template <class K> size_type count(const K &x) const { if (buckets.empty()) return 0; size_type index = hashFunction(x) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == x) return 1; } return 0; } iterator find(const Key &key) { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return iterator(buckets, buckets.begin() + index, it); } return end(); } const_iterator find(const Key &key) const { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return const_iterator(buckets, buckets.begin() + index, it); } return end(); } template <class K> iterator find(const K &x) { if (buckets.empty()) rehash(16); size_type index = hashFunction(x) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == (Key)x) return iterator(buckets, buckets.begin() + index, it); } return end(); } template <class K> const_iterator find(const K &x) const { if (buckets.empty()) rehash(16); size_type index = hashFunction(x) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == x) return const_iterator(buckets, buckets.begin() + index, it); } return end(); } bool contains(const Key &key) const { if (buckets.empty()) return false; size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return true; } return false; } template <class K> bool contains(const K &x) const { if (buckets.empty()) return false; size_type index = hashFunction(x) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == x) return true; } return false; } std::pair<iterator, iterator> equal_range(const Key &key) { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return std::make_pair(iterator(buckets, buckets.begin() + index, it), iterator(buckets, buckets.begin() + index, it)); } return std::make_pair(end(), end()); } std::pair<const_iterator, const_iterator> equal_range(const Key &key) const { if (buckets.empty()) rehash(16); size_type index = hashFunction(key) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == key) return std::make_pair(const_iterator(buckets, buckets.begin() + index, it), const_iterator(buckets, buckets.begin() + index, it)); } return std::make_pair(end(), end()); } template <class K> std::pair<iterator, iterator> equal_range(const K &x) { if (buckets.empty()) rehash(16); size_type index = hashFunction(x) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == x) return std::make_pair(iterator(buckets, buckets.begin() + index, it), iterator(buckets, buckets.begin() + index, it)); } return std::make_pair(end(), end()); } template <class K> std::pair<const_iterator, const_iterator> equal_range(const K &x) const { if (buckets.empty()) rehash(16); size_type index = hashFunction(x) % buckets.size(); auto &bucket = buckets[index]; for (auto it = bucket.begin(); it != bucket.end(); ++it) { if (it->first == x) return std::make_pair(const_iterator(buckets, buckets.begin() + index, it), const_iterator(buckets, buckets.begin() + index, it)); } return std::make_pair(end(), end()); } #pragma endregion Lookup #pragma region Bucket Interface local_iterator begin(size_type n) { return buckets[n].begin(); } const_local_iterator begin(size_type n) const { return buckets[n].begin(); } const_local_iterator cbegin(size_type n) const { return buckets[n].begin(); } local_iterator end(size_type n) { return buckets[n].end(); } const_local_iterator end(size_type n) const { return buckets[n].end(); } const_local_iterator cend(size_type n) const { return buckets[n].end(); } size_type bucket_count() const { return buckets.size(); } size_type max_bucket_count() const { return buckets.max_size(); } size_type bucket_size(size_type n) const { if (n >= buckets.size()) return 0; return buckets[n].size(); } size_type bucket(const Key &key) const { assert(!buckets.empty()); return hashFunction(key) % buckets.size(); } #pragma endregion Bucket Interface #pragma region Hash Policy float load_factor() const { return static_cast<float>(size()) / static_cast<float>(bucket_count()); } float max_load_factor() const { return maxLoadFactor; } void max_load_factor(float ml) { maxLoadFactor = ml; } void rehash(size_type count) { debug("Rehashing to %d", count); size_type currentLoadFactor = size() / max_load_factor(); if (count < currentLoadFactor) { debug("count %d => %d", count, currentLoadFactor); count = currentLoadFactor; } std::vector<node_type> newBuckets(count); for (const auto &bucket : buckets) { for (const auto &element : bucket) { size_type newIndex = hashFunction(element.first) % count; newBuckets[newIndex].push_back(element); } } buckets = std::move(newBuckets); } void reserve(size_type count) { rehash(std::ceil(count / max_load_factor())); } #pragma endregion Hash Policy #pragma region Observers hasher hash_function() const { return hashFunction; } key_equal key_eq() const { return key_equal(); } #pragma endregion Observers }; template <class Key, class T, class Hash, class KeyEqual, class Alloc> bool operator==(const std::unordered_map<Key, T, Hash, KeyEqual, Alloc> &lhs, const std::unordered_map<Key, T, Hash, KeyEqual, Alloc> &rhs) { return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); } }