Abstract:

Frozen is a header-only C++14 library designed to provide immutable, high-performance containers with zero-cost initialization. It offers constexpr-compatible versions of set, map, unordered_set, and unordered_map, allowing these data structures to be fully constructed at compile time, thus eliminating runtime overhead. A key feature of the unordered containers is the use of a perfect hashing algorithm, which guarantees collision-free, O(1) lookups. Additionally, the library supports constinit-compatible maps where keys are immutable but values can be modified at runtime. It also includes compile-time initialized searchers for Boyer-Moore and Knuth-Morris-Pratt string searching algorithms. The library is licensed under the Apache License 2.0 and requires a C++14 compatible compiler.

A Deep Dive into the 'Frozen' C++ Library

• Core Functionality: Frozen is a header-only C++14 library that provides immutable containers with zero-cost initialization. This means containers are constructed entirely at compile time using constexpr or constinit, eliminating runtime setup overhead.
• Compiler Requirements: The library requires a C++14 compatible compiler, such as Clang 5+, GCC 6+, or Visual Studio 2017+.
• Immutable Containers: Provides constexpr-compatible versions of std::set, std::map, std::unordered_set, and std::unordered_map. Once constructed, their keys (and for constexpr maps, values) cannot be changed, leading to faster lookups.
• Mutable Values with constinit: A special feature allows frozen::map and frozen::unordered_map to be initialized at compile time with constinit, while still allowing their values (but not keys) to be modified at runtime.
• Perfect Hashing: The unordered_* containers guarantee perfect hashing, which means there are no hash collisions for the stored keys. This ensures true O(1) lookup performance. The default hashing mechanism is a customizable function named elsa.
• High-Performance Search Algorithms: The library includes 0-cost initialization versions of string search algorithms, providing constexpr-compatible Boyer-Moore and Knuth-Morris-Pratt searchers that can be used with frozen::search.
• Installation and Integration: As a header-only library, it can be integrated by simply copying the include/frozen directory. It also includes robust CMake support for easy integration into larger projects, including find_package compatibility.
• Customization and Extensibility: Users can provide custom hash functions (by specializing frozen::elsa) and key comparison functions, similar to the standard library containers, to optimize for specific data types or implement transparent lookups.
• Troubleshooting Compile Times: For very large containers, the compile-time evaluation may hit compiler limits. This can often be resolved by increasing the compiler's constexpr step limit (e.g., using -fconstexpr-steps with Clang) or by providing a more suitable hash function for the data.
• Licensing: The library is distributed under the permissive Apache License 2.0.