mirror of
https://github.com/Fennix-Project/Kernel.git
synced 2025-05-25 22:14:37 +00:00
1281 lines
29 KiB
Plaintext
1281 lines
29 KiB
Plaintext
/*
|
|
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 Member Functions
|
|
|
|
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 Member Functions
|
|
|
|
#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
|
|
{
|
|
foreach (auto &bucket in 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)
|
|
{
|
|
foreach (const auto &value in 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();
|
|
}
|
|
|
|
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();
|
|
}
|
|
|
|
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());
|
|
}
|
|
}
|