tag_container.hpp¶
带全局加法偏移的哈希表，支持启发式合并；合并运算须满足交换、结合和加法平移相容性，如 min/max，右侧保留较小的原映射。
Complexity: Time: Expected amortized \(O(1)\) insert/erase/query, \(O(1)\) add. A join visits min(lhs.size(), rhs.size()) entries; rehashing is amortized. Space: \(O(N)\) per map, excluding retained maps after joins.
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Expected amortized O(1) insert/erase/query, O(1) add.
/// A join visits min(lhs.size(), rhs.size()) entries; rehashing is amortized.
/// Space: O(N) per map, excluding retained maps after joins.
#include "noya/ds/hashmap.hpp"
#include <utility>
namespace noya {
/// @brief HashMap with a global additive offset and small-to-large merging.
/// op is associative, commutative, and satisfies op(a+t,b+t)=op(a,b)+t
/// (e.g. min/max, not sum). V() is additive zero; arithmetic must not overflow.
template <class K, class V, auto op> struct tag_HashMap {
HashMap<K, V> S;
V tag = V();
/// @brief Insert or merge a key-value pair; val is its current true value.
void insert(K key, V val) {
V raw = val - tag;
auto [it, inserted] = S.try_emplace(key, std::move(raw));
if (!inserted)
it->second = op(it->second, raw);
}
void erase(K key) { S.erase(key); }
int size() const { return (int)S.size(); }
/// @brief Merge rhs into this map. If lhs was no larger, the two maps
/// and tags are swapped first; rhs retains that smaller pre-merge map.
/// O(M log M) expected total for a merge tree with M initial entries,
/// provided retained rhs maps are not reused as independent inputs.
void join(tag_HashMap<K, V, op> &rhs) {
if (size() <= rhs.size()) {
S.swap(rhs.S);
std::swap(tag, rhs.tag);
}
for (auto &[key, val] : rhs.S)
insert(key, val + rhs.tag);
}
/// @brief Add x to the global tag (offsets all stored values).
void add(V x) { tag += x; }
/// @brief Return the true value, or V() for an absent key without inserting.
V operator[](const K &x) const {
auto it = S.find(x);
return it == S.end() ? V() : it->second + tag;
}
};
} // namespace noya
// NOYA_TAG_CONTAINER_HPP
#ifndef NOYA_TAG_CONTAINER_HPP
#define NOYA_TAG_CONTAINER_HPP 1
/// @complexity Time: Expected amortized O(1) insert/erase/query, O(1) add.
/// A join visits min(lhs.size(), rhs.size()) entries; rehashing is amortized.
/// Space: O(N) per map, excluding retained maps after joins.
#include "noya/ds/hashmap.hpp"
#include <utility>
namespace noya {
/// @brief HashMap with a global additive offset and small-to-large merging.
/// op is associative, commutative, and satisfies op(a+t,b+t)=op(a,b)+t
/// (e.g. min/max, not sum). V() is additive zero; arithmetic must not overflow.
template <class K, class V, auto op> struct tag_HashMap {
HashMap<K, V> S;
V tag = V();
/// @brief Insert or merge a key-value pair; val is its current true value.
void insert(K key, V val) {
V raw = val - tag;
auto [it, inserted] = S.try_emplace(key, std::move(raw));
if (!inserted)
it->second = op(it->second, raw);
}
void erase(K key) { S.erase(key); }
int size() const { return (int)S.size(); }
/// @brief Merge rhs into this map. If lhs was no larger, the two maps
/// and tags are swapped first; rhs retains that smaller pre-merge map.
/// O(M log M) expected total for a merge tree with M initial entries,
/// provided retained rhs maps are not reused as independent inputs.
void join(tag_HashMap<K, V, op> &rhs) {
if (size() <= rhs.size()) {
S.swap(rhs.S);
std::swap(tag, rhs.tag);
}
for (auto &[key, val] : rhs.S)
insert(key, val + rhs.tag);
}
/// @brief Add x to the global tag (offsets all stored values).
void add(V x) { tag += x; }
/// @brief Return the true value, or V() for an absent key without inserting.
V operator[](const K &x) const {
auto it = S.find(x);
return it == S.end() ? V() : it->second + tag;
}
};
} // namespace noya
#endif // NOYA_TAG_CONTAINER_HPP
/// @complexity Time: Expected amortized O(1) insert/erase/query, O(1) add.
/// A join visits min(lhs.size(), rhs.size()) entries; rehashing is amortized.
/// Space: O(N) per map, excluding retained maps after joins.
/// @complexity Time: Expected O(1) per map operation.
/// Space: O(n).
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <unordered_map>
namespace noya {
/// @brief Randomized splitmix64 hash to prevent hash collision attacks.
/// Two xor-shift/multiply avalanche rounds spread nearby integer keys across
/// all bits, while a process-local time-derived offset makes adversarial keys
/// from one run useless in the next.
struct splitmix64_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t RND =
std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + RND);
}
};
/// @brief Unordered map with anti-hash randomized hash function.
template <typename K, typename V, typename Hash = splitmix64_hash>
using HashMap = std::unordered_map<K, V, Hash>;
} // namespace noya
#include <utility>
namespace noya {
/// @brief HashMap with a global additive offset and small-to-large merging.
/// op is associative, commutative, and satisfies op(a+t,b+t)=op(a,b)+t
/// (e.g. min/max, not sum). V() is additive zero; arithmetic must not overflow.
template <class K, class V, auto op> struct tag_HashMap {
HashMap<K, V> S;
V tag = V();
/// @brief Insert or merge a key-value pair; val is its current true value.
void insert(K key, V val) {
V raw = val - tag;
auto [it, inserted] = S.try_emplace(key, std::move(raw));
if (!inserted)
it->second = op(it->second, raw);
}
void erase(K key) { S.erase(key); }
int size() const { return (int)S.size(); }
/// @brief Merge rhs into this map. If lhs was no larger, the two maps
/// and tags are swapped first; rhs retains that smaller pre-merge map.
/// O(M log M) expected total for a merge tree with M initial entries,
/// provided retained rhs maps are not reused as independent inputs.
void join(tag_HashMap<K, V, op> &rhs) {
if (size() <= rhs.size()) {
S.swap(rhs.S);
std::swap(tag, rhs.tag);
}
for (auto &[key, val] : rhs.S)
insert(key, val + rhs.tag);
}
/// @brief Add x to the global tag (offsets all stored values).
void add(V x) { tag += x; }
/// @brief Return the true value, or V() for an absent key without inserting.
V operator[](const K &x) const {
auto it = S.find(x);
return it == S.end() ? V() : it->second + tag;
}
};
} // namespace noya
// NOYA_TAG_CONTAINER_HPP