Frozen C++14 零开销完美哈希容器

介绍

Frozen 是一个专为 C++14 用户设计的头文件库，它提供了一种零开销的初始化方式，用于创建不可变容器、固定大小容器以及各种算法。作为 gperf 的 constexpr 替代品，Frozen 库由 Serge Sans Paille 开发，旨在解决传统容器在编译时和运行时性能上的瓶颈。该库的核心理念是利用 C++14 的 constexpr 特性，实现容器在编译期的初始化，从而在运行时避免任何动态分配或哈希计算的开销。

Frozen：C++14 零开销完美哈希容器的革新

Frozen 的起源可以追溯到开发者对完美哈希函数的探索，它受到了“Throw away the keys: Easy, Minimal Perfect Hashing”博客文章的启发。该库提供 immutable（不可变）的版本，包括 std::set、std::unordered_set、std::map 和 std::unordered_map 的 constexpr 兼容实现。此外，它还支持固定容量的 constinit 兼容 map 和 unordered_map，这些容器允许在编译时固定键值，而值可以在运行时修改。库中还包括零开销的 std::search 实现，使用 Boyer-Moore 或 Knuth-Morris-Pratt 算法针对固定针（needle）的搜索。

在实际开发中，Frozen 特别适合那些需要高性能、零开销查找的场景，例如嵌入式系统、游戏引擎或任何对初始化时间敏感的应用。它的头文件-only 设计使得集成极为简单，只需复制 include/frozen 目录并通过 -I 标志指向即可。库支持 Clang 5、GCC 6 和 Visual Studio 2017 等编译器，但 GCC 5 不受支持。Frozen 强调稳定性，目前处于维护模式，master 分支即为稳定版本，欢迎贡献以提升代码的清洁度、速度和现代化。

Frozen 的独特之处在于其完美哈希保证：unordered_ 容器确保无哈希冲突，额外存储与键数线性相关。一旦容器初始化，键不可更新，但查找速度更快，尤其在 constexpr 或 constinit 下初始化免费。这使得 Frozen 成为 C++ 开发者在追求极致性能时的首选工具。通过提供内置字符串支持和异常处理兼容性，Frozen 不仅简化了代码，还提升了安全性（在无异常支持下，转为 std::abort）。

总体而言，Frozen 填补了标准库在编译时容器方面的空白，为现代 C++ 开发注入新活力。它不仅仅是一个容器库，更是一种编程范式的转变，鼓励开发者在编译期完成更多计算，从而优化运行时表现。

特性

Frozen 的特性主要围绕其提供的容器和算法展开，按模块分类可以分为三大类：不可变容器、固定容量容器和搜索算法。每类模块都注重零开销、constexpr 兼容性和完美哈希。

第一，不可变容器模块包括 frozen::set、frozen::unordered_set、frozen::map 和 frozen::unordered_map。这些容器是 std:: 对应容器的 immutable 版本，支持 constexpr 初始化，确保在编译期构建哈希表或有序结构。frozen::set 和 frozen::map 基于有序存储，而 unordered_ 版本使用完美哈希函数，确保 O(1) 查找且无冲突。额外存储线性于键数，这意味着对于固定数据集，内存效率极高。

例如，frozen::unordered_set 保证完美哈希，即使在运行时查询非 constexpr 值，也能保持高效。字符串支持通过 frozen::string 实现，这是一个内置的 constexpr 兼容字符串类型。

其次，固定容量容器模块针对那些键固定但值可变的场景，提供 frozen::map 和 frozen::unordered_map 的 constinit 版本。这些容器在编译时选择键，值可在运行时修改，适合配置表或缓存场景。初始化使用 constinit，确保全局静态初始化零开销。

第三，搜索算法模块提供零开销的 frozen::search，针对 frozen 针的 std::search 变体，使用 Boyer-Moore 或 Knuth-Morris-Pratt 算法。这些算法在编译期预计算模式，确保运行时搜索高效。

此外，Frozen 支持自定义扩展：用户可以特化哈希函数（如 frozen::elsa）、键相等比较器或有序比较函数。elsa 哈希器接受种子参数，确保 pairwise-independence 以减少冲突。如果默认哈希不适合数据，用户可自定义以加速编译。

异常处理特性也很灵活：默认兼容 STL API，可能抛出异常（如 at 方法），但定义 FROZEN_NO_EXCEPTIONS 可转为 abort。库还提供 make_X 函数简化初始化，如 frozen::make_set，避免重复指定类型。

在性能上，Frozen 的 constexpr 特性使容器在编译期冻结，运行时仅需简单访问。相比 gperf，它更现代化，支持更广泛的容器类型。模块分类详尽，确保开发者根据需求选择：有序 vs 无序、不可变 vs 值可变、容器 vs 算法。

这些特性使 Frozen 在嵌入式、实时系统和高性能计算中脱颖而出，提供了一种“冻结”数据的优雅方式。

Frozen C++14 零开销完美哈希容器

Frozen：C++14 零开销完美哈希容器

架构

Frozen 的架构设计简洁高效，核心基于完美哈希和 constexpr 机制。整体架构分为容器层、哈希层和算法层。

容器层是库的主体，实现了四种主要容器：set、unordered_set、map 和 unordered_map。每种容器内部使用数组或类似结构存储数据，对于 unordered_ 版本，采用最小完美哈希函数（minimal perfect hashing），确保哈希表无空槽且冲突率为零。这通过在编译期尝试不同种子来实现，如果哈希冲突，库会自动重试直到完美。

哈希层以 frozen::elsa 为核心，这是一个模板结构，提供带种子的哈希计算。elsa 的设计强调统计独立性：对于不同值 x 和 y，elsa(x, seed) == elsa(y, seed) 的概率极低。这允许库在 constexpr 上下文中构建完美哈希表。用户可特化 elsa 以适应特定数据分布，例如针对字符串的自定义哈希。

算法层专注于搜索，提供 frozen::search 的变体。它在编译期预计算 Boyer-Moore 的坏字符表或 KMP 的前缀表，确保运行时 O(n) 搜索中常数因子最小。架构上，这与容器集成，支持 frozen::string 作为针。

在内存布局上，容器使用固定大小数组，键和值（如果适用）内联存储，避免指针间接。constexpr 构造函数确保所有计算在编译期完成，生成静态数据。constinit 支持全局变量零开销初始化。

异常处理集成在 API 中，at 方法等可能抛出 out_of_range，但可配置为 abort。架构还包括兼容层，支持 C++14 特性如模板推导和 constexpr lambda。

测试和基准架构使用 Makefile 或 CMake，支持 Google Benchmark。测试覆盖 constexpr 验证、运行时行为和自定义扩展。整体架构的模块化允许轻松扩展，例如添加新容器类型。

这种架构确保 Frozen 轻量（头文件 only）、高效（零开销）和可扩展，适合从小型项目到大型系统的集成。

快速上手

开始使用 Frozen 超级简单。第一，下载库：从 GitHub 克隆 serge-sans-paille/frozen，或直接复制 include/frozen 目录到项目中。通过编译器标志 -I/path/to/frozen/include 包含头文件。

使用 CMake 安装：

 mkdir build
 cd build
 cmake -D CMAKE_BUILD_TYPE=Release ..
 make install

这会将配置文件置于 /usr/local/share，便于 find_package 使用。

要求：C++14 编译器，如 Clang 5+ 或 GCC 6+。启用 -std=c++14。

基本示例：创建 frozen::set。

 #include <frozen/set.h>
 
 constexpr frozen::set<int, 4> some_ints = {1, 2, 3, 5};
 
 constexpr bool contains_five = some_ints.count(5);  // true

这里，容器在编译期初始化，count 是 constexpr。

对于运行时：

 extern int n;
 bool has_n = some_ints.count(n);

字符串 unordered_map 示例：

 #include <frozen/unordered_map.h>
 #include <frozen/string.h>
 
 constexpr frozen::unordered_map<frozen::string, int, 2> olaf = {
     {"19", 19},
     {"31", 31}
 };
 
 constexpr auto val = olaf.at("19");  // 19

值可变版本：

 #include <frozen/unordered_map.h>
 #include <frozen/string.h>
 
 static constinit frozen::unordered_map<frozen::string, frozen::string, 2> voice = {
     {"Anna", "???"},
     {"Elsa", "???"}
 };
 
 int main() {
     voice.at("Anna") = "Kristen";
     voice.at("Elsa") = "Idina";
     return 0;
 }

使用 make_ 函数简化：

 constexpr auto some_ints = frozen::make_set<int>({1, 2, 3, 5});

自定义哈希以解决冲突：

 struct custom_hash {
     constexpr std::size_t operator()(frozen::string const &value, std::size_t seed) const {
         return seed ^ value[0];
     }
 };
 
 constexpr frozen::unordered_set<frozen::string, 2, custom_hash> hans = {"a", "b"};

搜索算法示例：假设使用 frozen::search，需要包含相关头文件（库中算法部分）。针对固定针：

 #include <frozen/algorithm.h>  // 假设路径
 
 constexpr frozen::string needle = "pattern";
 auto pos = frozen::search(haystack.begin(), haystack.end(), needle.begin(), needle.end());

（注：实际需检查头文件；库提供 Boyer-Moore 等）。

异常处理：如果键不存在，at 会抛出；定义 FROZEN_NO_EXCEPTIONS 转为 abort。

编译问题：如果 constexpr 步数超限，用 -fconstexpr-steps=1000000000 增加阈值。

测试：make -C tests check；基准：需 Google Benchmark。

通过这些步骤，开发者可在几分钟内上手 Frozen，并享受其性能优势。

应用场景

Frozen 在多种场景中大放异彩，尤其适合需要编译时优化和高性能查找的应用。

第一，在嵌入式系统中，资源有限，Frozen 的零开销初始化至关重大。例如，创建一个配置表：

 #include <frozen/unordered_map.h>
 #include <frozen/string.h>
 
 static constinit frozen::unordered_map<frozen::string, int, 3> config = {
     {"baud_rate", 9600},
     {"timeout", 1000},
     {"retries", 3}
 };
 
 int get_config(const char* key) {
     frozen::string fkey(key);
     auto it = config.find(fkey);
     if (it != config.end()) {
         return it->second;
     }
     return -1;  // 默认值
 }

这里，键在编译期固定，值可运行时调整（但本例未改），适合 MCU 配置。

其次，在游戏开发中，Frozen 用于常量数据表，如关卡映射：

 #include <frozen/map.h>
 
 constexpr frozen::map<int, frozen::string, 4> levels = {
     {1, "Easy"},
     {2, "Medium"},
     {3, "Hard"},
     {4, "Expert"}
 };
 
 const char* get_level_name(int lvl) {
     auto it = levels.find(lvl);
     return (it != levels.end()) ? it->second.data() : "Unknown";
 }

有序 map 确保快速有序查找，constexpr 使数据嵌入二进制。

第三，在高性能计算（如科学模拟）中，使用 unordered_set 过滤数据：

 #include <frozen/unordered_set.h>
 
 constexpr frozen::unordered_set<int, 5> primes = {2, 3, 5, 7, 11};
 
 bool is_prime(int num) {
     return primes.count(num);
 }

完美哈希确保 O(1) 无冲突，适合热点代码。

第四，模板元编程场景：利用 constexpr 在编译期计算：

 #include <frozen/set.h>
 
 template<std::size_t N>
 std::enable_if_t<frozen::set<int, 3>{{1, 11, 111}}.count(N), int> foo() {
     return N;
 }
 
 // foo<1>() 有效，foo<2>() 编译错误

这扩展了 SFINAE 应用。

第五，字符串处理，如命令解析器：

 #include <frozen/unordered_map.h>
 #include <frozen/string.h>
 
 constexpr frozen::unordered_map<frozen::string, void(*)(void), 2> commands = {
     {"help", show_help},
     {"exit", do_exit}
 };
 
 void process_command(const char* cmd) {
     frozen::string fcmd(cmd);
     auto it = commands.find(fcmd);
     if (it != commands.end()) {
         it->second();
     }
 }

内置字符串支持简化处理。

第六，搜索算法在文本处理中：针对固定模式的日志分析。

 #include <frozen/algorithm.h>  // 假设
 
 constexpr frozen::string error_pattern = "ERROR:";
 auto found = frozen::search(log.begin(), log.end(), error_pattern.begin(), error_pattern.end());
 if (found != log.end()) {
     // 处理错误
 }

预计算确保高效。

在实时系统，如自动驾驶软件，Frozen 可用于固定路由表，避免运行时开销。在 Web 服务器中，用作路由映射，加速请求处理。

潜在挑战：大容器可能延长编译时间，需优化哈希。应用时，确保数据固定以发挥优势。

总体，Frozen 适用于任何追求性能的 C++ 项目，从小型脚本到企业级应用。

社区/生态

Frozen 的社区虽小但活跃，主要聚焦在 GitHub 上。仓库 serge-sans-paille/frozen 有稳定贡献者，如 Jérôme Dumesnil 和 Chris Beck，他们在完美哈希和代码审查上出力。开发者可通过 issue 报告 bug 或提议功能，pull request 欢迎现代化改善，如 C++17/20 支持。

生态方面，Frozen 与标准库无缝集成，可作为 gperf 替代，与 Boost 等库互补。例如，与 Boost.Container 结合，提供混合容器。测试使用 Google Benchmark，易于基准比较。

外部集成：CMake 支持 find_package，便于大型项目。兼容 Clang、GCC 和 MSVC，确保跨平台。

社区活动包括 Travis CI 构建，badge 显示状态。联系作者 Serge Sans Paille via email: sergesanspaille@free.fr。

虽无大型论坛，Frozen 在 Stack Overflow 和 Reddit 的 C++ 子版中偶有讨论。生态扩展潜力大，可与其他 constexpr 库如 CTRE（编译时正则）结合。

未来，社区可推动更多算法模块，如排序变体。总体，Frozen 的生态注重质量而非规模，适合专业开发者。