kwsFrozen

This repository is a version of the frozen library (https://github.com/serge-sans-paille/frozen) updated to support C++23. Note that this means you must have a compiler that supports C++23 to use this library.

---

Frozen

This is a header-only library that provides zero 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.

• zero-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. Initialization is free when constexpr or constinit is used.

Comparison with C++23 std::flat_set / std::flat_map

Under the hood, frozen::set and frozen::map store their elements in a sorted contiguous array (std::array) — the same flat layout that C++23's std::flat_set and std::flat_map use. The key differences are:

• Immutable keys and compile-time size. Frozen containers have their size N fixed as a template parameter and their contents are set at construction. std::flat_set/std::flat_map are mutable, runtime-sized containers backed by std::vector (by default) that support insert and erase.

• Optimized binary search. Because N is known at compile time, frozen's binary search unrolls into a branchless sequence of comparisons — eliminating loop overhead and branch misprediction. std::flat_set/std::flat_map use a conventional binary search loop since their size is only known at runtime.

• Zero-cost initialization. Frozen containers can be fully constructed at compile time (constexpr/constinit), meaning no runtime sorting or allocation. std::flat_set/std::flat_map sort their elements at runtime during construction.

If you need a fixed, known-at-compile-time set of keys, frozen containers will generally outperform their C++23 flat counterparts — especially for lookup-heavy workloads — because of the branchless search and zero initialization cost.

Installation

Copy the include/frozen directory somewhere and point to it using the -I flag. Alternatively, using CMake:

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++23. Minimum supported compiler versions:

Compiler	Minimum Version
GCC	13
Clang	16
MSVC	19.38 (Visual Studio 2022 17.8)

Usage

Compiled with -std=c++23 flag:

#include <frozen/set.h>

constexpr frozen::set<int, 4> 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:

#include <frozen/set.h>

template<std::size_t N>
std::enable_if_t< frozen::set<int, 3>{{1,11,111}}.count(N), int> foo();

String support is built-in via std::string_view:

#include <frozen/unordered_map.h>
#include <frozen/string.h>       // provides frozen::string (= std::string_view)
#include <frozen/bits/elsa_std.h> // hash specialization for std::string_view

constexpr frozen::unordered_map<std::string_view, int, 2> olaf = {
    {"19", 19},
    {"31", 31},
};
constexpr auto val = olaf.at("19");

frozen::string is a type alias for std::string_view. You can use either interchangeably. Include <frozen/bits/elsa_std.h> when using std::string_view or std::string as container keys — it provides the hash specialization.

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):

#include <frozen/unordered_map.h>
#include <frozen/string.h>
#include <frozen/bits/elsa_std.h>

static constinit frozen::unordered_map<std::string_view, std::string_view, 2> voice = {
    {"Anna", "???"},
    {"Elsa", "???"}
};

int main() {
    voice.at("Anna") = "Kristen";
    voice.at("Elsa") = "Idina";
}

You may also prefer a slightly more DRY initialization syntax:

#include <frozen/set.h>

constexpr auto some_ints = frozen::make_set<int>({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++23 containers, you can specialize the hash function, the key equality comparator for unordered_* containers, and the comparison functions for the ordered version.

Heterogeneous Lookup (Default)

All frozen containers now use transparent comparators by default (std::less<> for ordered containers, std::equal_to<> for unordered containers). This means you can look up keys with any type that is comparable to the key type, without explicit conversion:

#include <frozen/map.h>
#include <frozen/bits/elsa_std.h>

constexpr frozen::map<std::string_view, int, 2> m = {
    {"hello", 1}, {"world", 2}
};

// All of these work — no std::string_view construction needed:
std::string key = "hello";
m.count(key);              // lookup with std::string
m.count("hello");          // lookup with const char*
m.at(std::string_view{"hello"});  // lookup with string_view

For ordered containers with numeric keys, you can also look up with implicitly convertible types:

constexpr frozen::set<long, 3> s = {10L, 20L, 30L};
static_assert(s.count(20) == 1);  // int lookup in long set

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.

template <class T> struct elsa {
  // in case of collisions, different seeds are tried
  constexpr std::size_t operator()(T const &value, std::size_t seed) const;
};

Hash specializations for std::string_view and std::string are provided in <frozen/bits/elsa_std.h>. Include this header when using standard string types as container keys.

Ideally, the hash function should have nice statistical properties like pairwise-independence:

If x and y are different values, the chance that elsa<T>{}(x, seed) == elsa<T>{}(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:

[...]
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:

struct olaf {
  constexpr std::size_t operator()(std::string_view value, std::size_t seed) const { return seed ^ value[0];}
};

constexpr frozen::unordered_set<std::string_view, 2, olaf/*custom hash*/> hans = { "a", "b" };

Tests and Benchmarks

Using hand-written Makefiles crafted with love and care:

# running tests
make -C tests check
# running benchmarks
make -C benchmarks GOOGLE_BENCHMARK_PREFIX=<GOOGLE-BENCHMARK_INSTALL_DIR>

Using CMake to generate a static configuration build system:

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:

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

Migration from v1.x

This version requires C++23 and includes the following breaking changes:

v1.x	v2.x (this version)
frozen::string (custom type)	frozen::string = std::string_view (alias)
Explicit std::less<void> for transparent lookup	std::less<> is now the default comparator
Explicit std::equal_to<void> for transparent lookup	std::equal_to<> is now the default equality
#include <frozen/string.h> for string keys	Also need #include <frozen/bits/elsa_std.h> for hash
C++14/17 with feature-detection macros	C++23 required, no feature-detection macros
FROZEN_LETITGO_HAS_DEDUCTION_GUIDES	Deduction guides are always available
FROZEN_LETITGO_HAS_STRING_VIEW	std::string_view is always available
FROZEN_LETITGO_HAS_CHAR8T	char8_t is always available
FROZEN_LETITGO_HAS_CONSTEVAL	consteval is always available

Credits

Thanks to Serge sans Paille for creating the original frozen library.

In the original frozen library, thanks to Jérôme Dumesnil for his high-quality reviews, and to Chris Beck for his contributions on perfect hashing.

The perfect hashing in the original frozen library (and this version) is strongly inspired by the blog post Throw away the keys: Easy, Minimal Perfect Hashing.