-
Notifications
You must be signed in to change notification settings - Fork 843
Open
Description
The following was >2x faster than std::unordered_map for https://codeforces.com/gym/103861/problem/B and the pbds hash map was also terrible (slow construction time? too much memory use?):
typedef uint64_t ull;
template<class T>
struct HashMap {
int b;
vector<pair<ull, T>> v;
HashMap(int b) : b(b), v(1 << b) {}
T& operator[](ull x) {
ull y = x >> (64 - b), m = (1 << b) - 1;
while (v[y].first && v[y].first != x) ++y &= m;
v[y].first = x;
return v[y].second;
}
};
Maybe worth adding to KACTL instead of the pbds one?
Metadata
Metadata
Assignees
Labels
No labels