hashmap/hashmap-unerasable.hpp
Depends on
Required by
Verified with
Code
#pragma once
#include <cassert>
#include <vector>
using namespace std;
#include "../internal/internal-hash-function.hpp"
// 削除不可能な hashmap
//
// テンプレート引数
// fixed_size : これを true にするするとバケットサイズが固定になる
// get_hash : ハッシュ関数の指定
// 引数
// _default_value : val の初期値, この値で初期化
// _default_size :
// バケットサイズ, max(4, _default_size) 以上の 2 べきで初期化
// ただし fixed_size が true の時にしかサイズを変更できない
template <typename Key, typename Val, bool fixed_size = false,
unsigned long long (*get_hash)(const Key&) =
nyaan_internal::hash_function<Key>>
struct UnerasableHashMap {
int N, occupied_num, shift;
vector<Key> keys;
vector<Val> vals;
vector<char> flag;
Val default_value;
int default_size;
// サイズを n に変更する
void init(int n, bool reset = false) {
assert(n >= 4 && (n & (n - 1)) == 0);
if constexpr (fixed_size) {
assert(reset == true);
n = N;
}
if (reset == true) {
N = n, occupied_num = 0, shift = 64 - __builtin_ctz(n);
keys.resize(n);
vals.resize(n);
flag.resize(n);
fill(begin(vals), end(vals), default_value);
fill(begin(flag), end(flag), 0);
} else {
N = n, shift = 64 - __builtin_ctz(n);
vector<Key> keys2(n);
vector<Val> vals2(n, default_value);
vector<char> flag2(n);
swap(keys, keys2), swap(vals, vals2), swap(flag, flag2);
for (int i = 0; i < (int)flag2.size(); i++) {
if (flag2[i]) {
int j = hint(keys2[i]);
keys[j] = keys2[i], vals[j] = vals2[i], flag[j] = 1;
}
}
}
}
UnerasableHashMap(const Val& _default_value = Val{}, int _default_size = 4)
: occupied_num(0), default_value(_default_value) {
if (fixed_size == false) _default_size = 4;
N = 4;
while (N < _default_size) N *= 2;
default_size = N;
init(N, true);
}
int hint(const Key& k) {
int hash = get_hash(k) >> shift;
while (flag[hash] && keys[hash] != k) hash = (hash + 1) & (N - 1);
return hash;
}
// key が i である要素への参照を返す
Val& operator[](const Key& k) {
int i = hint(k);
if (!flag[i]) {
if constexpr (fixed_size == false) {
if (occupied_num * 2 >= N) {
init(2 * N), i = hint(k);
}
}
keys[i] = k, flag[i] = 1, occupied_num++;
}
return vals[i];
}
Val get(const Key& k) {
int i = hint(k);
return flag[i] ? vals[i] : default_value;
}
// 走査, f に関数 f(key, val) を入れる
template <typename F>
void enumerate(const F f) {
for (int i = 0; i < (int)flag.size(); i++) {
if (flag[i]) f(keys[i], vals[i]);
}
}
int count(const Key& k) { return flag[hint(k)]; }
bool contain(const Key& k) { return flag[hint(k)]; }
int size() const { return occupied_num; }
void reset() { init(default_size, true); }
void clear() { init(default_size, true); }
};
#line 2 "hashmap/hashmap-unerasable.hpp"
#include <cassert>
#include <vector>
using namespace std;
#line 2 "internal/internal-hash-function.hpp"
#line 4 "internal/internal-hash-function.hpp"
using namespace std;
#line 2 "internal/internal-seed.hpp"
#include <chrono>
using namespace std;
namespace nyaan_internal {
unsigned long long non_deterministic_seed() {
unsigned long long m =
chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count();
m ^= 9845834732710364265uLL;
m ^= m << 24, m ^= m >> 31, m ^= m << 35;
return m;
}
unsigned long long deterministic_seed() { return 88172645463325252UL; }
// 64 bit の seed 値を生成 (手元では seed 固定)
// 連続で呼び出すと同じ値が何度も返ってくるので注意
// #define RANDOMIZED_SEED するとシードがランダムになる
unsigned long long seed() {
#if defined(NyaanLocal) && !defined(RANDOMIZED_SEED)
return deterministic_seed();
#else
return non_deterministic_seed();
#endif
}
} // namespace nyaan_internal
#line 2 "internal/internal-type-traits.hpp"
#include <type_traits>
using namespace std;
namespace nyaan_internal {
template <typename T>
using is_broadly_integral =
typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> ||
is_same_v<T, __uint128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_signed =
typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_unsigned =
typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>,
true_type, false_type>::type;
#define ENABLE_VALUE(x) \
template <typename T> \
constexpr bool x##_v = x<T>::value;
ENABLE_VALUE(is_broadly_integral);
ENABLE_VALUE(is_broadly_signed);
ENABLE_VALUE(is_broadly_unsigned);
#undef ENABLE_VALUE
#define ENABLE_HAS_TYPE(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<typename T::var>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
#define ENABLE_HAS_VAR(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
} // namespace nyaan_internal
#line 8 "internal/internal-hash-function.hpp"
namespace nyaan_internal {
// 整数, 整数列を 64 bit unsigned int へ移す
using u64 = unsigned long long;
using u128 = __uint128_t;
ENABLE_HAS_TYPE(first_type);
ENABLE_HAS_TYPE(second_type);
ENABLE_HAS_TYPE(iterator);
template <typename T>
u64 hash_function(const T& x) {
static u64 r = seed();
constexpr u64 z1 = 11995408973635179863ULL;
if constexpr (is_broadly_integral_v<T>) {
// Integral
return (u64(x) ^ r) * z1;
} else if constexpr (has_first_type_v<T> && has_second_type_v<T>) {
// pair
constexpr u64 z2 = 10150724397891781847ULL;
return hash_function(x.first) + hash_function(x.second) * z2;
} else if constexpr (has_iterator_v<T>) {
// Container
constexpr u64 mod = (1LL << 61) - 1;
constexpr u64 base = 950699498548472943ULL;
u64 m = 0;
for (auto& z : x) {
u64 w;
if constexpr (is_broadly_integral_v<T>) {
w = u64(z) ^ r;
} else {
w = hash_function(z);
}
u128 y = u128(m) * base + (w & mod);
m = (y & mod) + (y >> 61);
if (m >= mod) m -= mod;
}
m ^= m << 24, m ^= m >> 31, m ^= m << 35;
return m;
} else {
static_assert([]() { return false; }());
}
}
template <typename Key>
struct HashObject {
size_t operator()(const Key& x) const { return hash_function(x); }
};
} // namespace nyaan_internal
/*
@brief ハッシュ関数
*/
#line 8 "hashmap/hashmap-unerasable.hpp"
// 削除不可能な hashmap
//
// テンプレート引数
// fixed_size : これを true にするするとバケットサイズが固定になる
// get_hash : ハッシュ関数の指定
// 引数
// _default_value : val の初期値, この値で初期化
// _default_size :
// バケットサイズ, max(4, _default_size) 以上の 2 べきで初期化
// ただし fixed_size が true の時にしかサイズを変更できない
template <typename Key, typename Val, bool fixed_size = false,
unsigned long long (*get_hash)(const Key&) =
nyaan_internal::hash_function<Key>>
struct UnerasableHashMap {
int N, occupied_num, shift;
vector<Key> keys;
vector<Val> vals;
vector<char> flag;
Val default_value;
int default_size;
// サイズを n に変更する
void init(int n, bool reset = false) {
assert(n >= 4 && (n & (n - 1)) == 0);
if constexpr (fixed_size) {
assert(reset == true);
n = N;
}
if (reset == true) {
N = n, occupied_num = 0, shift = 64 - __builtin_ctz(n);
keys.resize(n);
vals.resize(n);
flag.resize(n);
fill(begin(vals), end(vals), default_value);
fill(begin(flag), end(flag), 0);
} else {
N = n, shift = 64 - __builtin_ctz(n);
vector<Key> keys2(n);
vector<Val> vals2(n, default_value);
vector<char> flag2(n);
swap(keys, keys2), swap(vals, vals2), swap(flag, flag2);
for (int i = 0; i < (int)flag2.size(); i++) {
if (flag2[i]) {
int j = hint(keys2[i]);
keys[j] = keys2[i], vals[j] = vals2[i], flag[j] = 1;
}
}
}
}
UnerasableHashMap(const Val& _default_value = Val{}, int _default_size = 4)
: occupied_num(0), default_value(_default_value) {
if (fixed_size == false) _default_size = 4;
N = 4;
while (N < _default_size) N *= 2;
default_size = N;
init(N, true);
}
int hint(const Key& k) {
int hash = get_hash(k) >> shift;
while (flag[hash] && keys[hash] != k) hash = (hash + 1) & (N - 1);
return hash;
}
// key が i である要素への参照を返す
Val& operator[](const Key& k) {
int i = hint(k);
if (!flag[i]) {
if constexpr (fixed_size == false) {
if (occupied_num * 2 >= N) {
init(2 * N), i = hint(k);
}
}
keys[i] = k, flag[i] = 1, occupied_num++;
}
return vals[i];
}
Val get(const Key& k) {
int i = hint(k);
return flag[i] ? vals[i] : default_value;
}
// 走査, f に関数 f(key, val) を入れる
template <typename F>
void enumerate(const F f) {
for (int i = 0; i < (int)flag.size(); i++) {
if (flag[i]) f(keys[i], vals[i]);
}
}
int count(const Key& k) { return flag[hint(k)]; }
bool contain(const Key& k) { return flag[hint(k)]; }
int size() const { return occupied_num; }
void reset() { init(default_size, true); }
void clear() { init(default_size, true); }
};
Back to top page
marathon/top-k.hpp