# frozen **Repository Path**: dlmu-cone/frozen ## Basic Information - **Project Name**: frozen - **Description**: No description available - **Primary Language**: Unknown - **License**: Apache-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2025-11-29 - **Last Updated**: 2025-11-29 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README Frozen ###### .. image:: https://travis-ci.org/serge-sans-paille/frozen.svg?branch=master :target: https://travis-ci.org/serge-sans-paille/frozen Header-only library that provides 0 cost initialization for immutable containers, fixed-size containers, and various algorithms. Frozen provides: - immutable (a.k.a. frozen), ``constexpr``-compatible versions of ``std::set``, ``std::unordered_set``, ``std::map`` and ``std::unordered_map``. - fixed-capacity, ``constinit``-compatible versions of ``std::map`` and ``std::unordered_map`` with immutable, compile-time selected keys mapped to mutable values. - 0-cost initialization version of ``std::search`` for frozen needles using Boyer-Moore or Knuth-Morris-Pratt algorithms. The ``unordered_*`` containers are guaranteed *perfect* (a.k.a. no hash collision) and the extra storage is linear with respect to the number of keys. Once initialized, the container keys cannot be updated, and in exchange, lookups are faster. And initialization is free when ``constexpr`` or ``constinit`` is used :-). Stable Version -------------- The Frozen library is pretty stable now, have been so for years, so: 1. The ``master`` version can be used as the default **stable** version. 2. It is in maintenance mode. I still accept commits that make the code cleaner ``|`` faster ``|`` more modern, but expect some latency in the review process. Installation ------------ Just copy the ``include/frozen`` directory somewhere and points to it using the ``-I`` flag. Alternatively, using CMake: .. code-block:: sh mkdir build cd build cmake -D CMAKE_BUILD_TYPE=Release .. make install Installation via CMake populates configuration files into the ``/usr/local/share`` directory which can be consumed by CMake's ``find_package`` intrinsic function. Requirements ------------ A C++ compiler that supports C++14. Clang version 5 is a good pick, GCC version 6 lags behind in terms of ``constexpr`` compilation time (At least on my setup), but compiles correctly. Visual Studio 2017 also works correctly! Note that GCC 5 isn't supported. (Here's an `old compat branch`_ where a small amount of stuff was ported.) .. _old compat branch: https://github.com/cbeck88/frozen/tree/gcc5-support Usage ----- Compiled with ``-std=c++14`` flag: .. code-block:: C++ #include constexpr frozen::set some_ints = {1,2,3,5}; constexpr bool letitgo = some_ints.count(8); extern int n; bool letitgoooooo = some_ints.count(n); As the constructor and some methods are ``constexpr``, it's also possible to write weird stuff like: .. code-block:: C++ #include template std::enable_if_t< frozen::set{{1,11,111}}.count(N), int> foo(); String support is built-in: .. code-block:: C++ #include #include constexpr frozen::unordered_map olaf = { {"19", 19}, {"31", 31}, }; constexpr auto val = olaf.at("19"); The associative containers have different functionality with and without ``constexpr``. With ``constexpr``, frozen maps have immutable keys and values. Without ``constexpr``, the values can be updated in runtime (the keys, however, remain immutable): .. code-block:: C++ #include #include static constinit frozen::unordered_map voice = { {"Anna", "???"}, {"Elsa", "???"} }; int main() { voice.at("Anna") = "Kristen"; voice.at("Elsa") = "Idina"; } You may also prefer a slightly more DRY initialization syntax: .. code-block:: C++ #include constexpr auto some_ints = frozen::make_set({1,2,3,5}); There are similar ``make_X`` functions for all frozen containers. Exception Handling ------------------ For compatibility with STL's API, Frozen may eventually throw exceptions, as in ``frozen::map::at``. If you build your code without exception support, or define the ``FROZEN_NO_EXCEPTIONS`` macro variable, they will be turned into an ``std::abort``. Extending --------- Just like the regular C++14 container, you can specialize the hash function, the key equality comparator for ``unordered_*`` containers, and the comparison functions for the ordered version. It's also possible to specialize the ``frozen::elsa`` structure used for hashing. Note that unlike `std::hash`, the hasher also takes a seed in addition to the value being hashed. .. code-block:: C++ template struct elsa { // in case of collisions, different seeds are tried constexpr std::size_t operator()(T const &value, std::size_t seed) const; }; Ideally, the hash function should have nice statistical properties like *pairwise-independence*: If ``x`` and ``y`` are different values, the chance that ``elsa{}(x, seed) == elsa{}(y, seed)`` should be very low for a random value of ``seed``. Note that frozen always ultimately produces a perfect hash function, and you will always have ``O(1)`` lookup with frozen. It's just that if the input hasher performs poorly, the search will take longer and your project will take longer to compile. Troubleshooting --------------- If you hit a message like this: .. code-block:: none [...] note: constexpr evaluation hit maximum step limit; possible infinite loop? Then either you've got a very big container and you should increase Clang's thresholds, using ``-fconstexpr-steps=1000000000`` for instance, or the hash functions used by frozen do not suit your data, and you should change them, as in the following: .. code-block:: c++ struct olaf { constexpr std::size_t operator()(frozen::string const &value, std::size_t seed) const { return seed ^ value[0];} }; constexpr frozen::unordered_set hans = { "a", "b" }; Tests and Benchmarks -------------------- Using hand-written Makefiles crafted with love and care: .. code-block:: sh # running tests make -C tests check # running benchmarks make -C benchmarks GOOGLE_BENCHMARK_PREFIX= Using CMake to generate a static configuration build system: .. code-block:: sh mkdir build cd build cmake -D CMAKE_BUILD_TYPE=Release \ -D frozen.benchmark=ON \ -G <"Unix Makefiles" or "Ninja"> .. # building the tests and benchmarks... make # ... with make ninja # ... with ninja cmake --build . # ... with cmake # running the tests... make test # ... with make ninja test # ... with ninja cmake --build . --target test # ... with cmake ctest # ... with ctest # running the benchmarks... make benchmark # ... with make ninja benchmark # ... with ninja cmake --build . --target benchmark # ... with cmake Using CMake to generate an IDE build system with test and benchmark targets .. code-block:: sh mkdir build cd build cmake -D frozen.benchmark=ON -G <"Xcode" or "Visual Studio 15 2017"> .. # using cmake to drive the IDE build, test, and benchmark cmake --build . --config Release cmake --build . --target test cmake --build . --target benchmark Credits ------- The perfect hashing is strongly inspired by the blog post `Throw away the keys: Easy, Minimal Perfect Hashing `_. Thanks a lot to Jérôme Dumesnil for his high-quality reviews, and to Chris Beck for his contributions on perfect hashing. Contact ------- Serge sans Paille ````