a header-only, constexpr alternative to gperf for C++14 users




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


Just copy the include/frozen directory somewhere and points 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 instrinsic function.


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


Compiled with -std=c++14 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:

#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");

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>

static constinit frozen::unordered_map<frozen::string, frozen::string, 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.


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.

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;

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.


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()(frozen::string const &value, std::size_t seed) const { return seed ^ value[0];}

constexpr frozen::unordered_set<frozen::string, 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

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


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.


Serge sans Paille <[email protected]>

  • Don't add sources for subproject

    Don't add sources for subproject

    This prevents adding the frozen headers as source files to all libraries that link to the frozen interface library. Otherwise IDEs such as Xcode display the frozen headers as source files for each library that requires frozen.

    opened by TheLartians 12
  • feature: elsa for std string types

    feature: elsa for std string types

    This will allow using frozen containers with std::string_view(C++17) and std::string(C++20). I'm not sure if tests are needed for this ... I plan to add a heterogeneous search in the next PR, there it will already be possible to write tests that will use the hash for std::string_view.

    opened by impugachev 9
  • Added support for wide chars via frozen::wstring

    Added support for wide chars via frozen::wstring

    This is an extension of frozen::string to support wide strings. I simply moved the default frozen::string to a templated class called frozen::basic_string and used it to define frozen::string (frozen::basic_string<char>) and frozen::wstring (frozen::basic_string<wchar_t>). I also added the _ws string literal for frozen::wstrings.

    opened by marcoffee 9
  • Added basic CPack support

    Added basic CPack support

    Greeting again. This pull request extends the cmake support a bit and adds some inline comments explaining what is being done.

    p.s. congrats on your CPPCon acceptance!

    opened by apmccartney 9
  • constexpr-compatible linear congruantial engine

    constexpr-compatible linear congruantial engine

    @cbeck88 this is an implementation of the std interface for the engine we care about. I used it in your headers and it works nice, so once this is merged, you can rebase on master.

    opened by serge-sans-paille 9
  • Compilation errors in VS 2019

    Compilation errors in VS 2019


    Thanks for the great library. I am trying to use it with Visual Studio 2019 (v142) but am encountering compilation errors when using unordered_map as shown in the examples in the README (the set example does compile though).

    I saw the README only mentions VS 2017, so perhaps 2019 just isn't supported yet? If so, any plans for supporting 2019?

    Here is a Visual Studio solution that shows compilation errors, and here is the code:

    // dllmain.cpp : Defines the entry point for the DLL application.
    #include "pch.h"
    #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");

    Build output:

    1>------ Build started: Project: Frozen, Configuration: Debug x64 ------
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): warning C4003: not enough arguments for function-like macro invocation 'max'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2589: '(': illegal token on right side of '::'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2062: type 'unknown-type' unexpected
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2737: 'private: static unsigned __int64 const frozen::bits::seed_or_index::MINUS_ONE': 'constexpr' object must be initialized
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2059: syntax error: ')'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(135,42): error C2131: expression did not evaluate to a constant
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(135,44): message : failure was caused by a read of an uninitialized symbol
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(135,44): message : see usage of 'MINUS_ONE'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(186,68): warning C4003: not enough arguments for function-like macro invocation 'max'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(186,68): error C2589: '(': illegal token on right side of '::'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(65,32): warning C4003: not enough arguments for function-like macro invocation 'min'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(66,32): warning C4003: not enough arguments for function-like macro invocation 'max'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(65,1): error C2059: syntax error: ')'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78): message : see reference to class template instantiation 'frozen::linear_congruential_engine<UIntType,a,c,m>' being compiled
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(65,1): error C2334: unexpected token(s) preceding ':'; skipping apparent function body
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): error C2143: syntax error: missing ')' before ';'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): error C2059: syntax error: ')'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): error C2238: unexpected token(s) preceding ';'
    1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): fatal error C1201: unable to continue after syntax error in class template definition
    1>Done building project "Frozen.vcxproj" -- FAILED.
    ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========


    opened by mistval 7
  • should the

    should the "initial" hash also be "randomized" ?

    Thanks for sharing your implementation here -- I have been studying it for a while now. I have some questions:

    In the perfect minimal hashing implementation frozen/bits/pmh.h, you have quite faithfully implemented what is described generally here: http://stevehanov.ca/blog/index.php?id=119

    And in this blog, it is claimed that the algorithm takes linear time, due to this paper: http://cmph.sourceforge.net/papers/esa09.pdf

    However, it seems to me that there is a disconnect, because in that paper, not only are the hashes for each bucket random, but the "initial" hash is also. In the blog post (and in frozen), the hash key used for each bucket is either chosen strategically or by trial and error, but the "initial" hash that is used to populate the buckets is fixed, and is not random.

    This is a problem because the overall running time analysis relies on all of the buckets being small ~ as if the initial hash is random. In the totally random hash function model, suppose that we are going along and handling the buckets greedily. If we already have mapped a constant fraction of the items, and we encounter a bucket with k items, we expect to take 2^O(k) guesses before we find a hash seed that accommodates them all. So if "most" of the items are in "large" buckets, we take exponential time.

    I think it means that for "bad" inputs, or basically, inputs where the unseeded version of elsa gives a bad distribution of buckets, the algorithm will always fail or take a long time.

    Intuitively, one way to fix it is, use the seeded version of elsa for the initial bucket placement also. Then, inspect the distribution of buckets, and if there were a huge number of collisions, then try a different seed, until it is within some tolerance.

    I attempted to do this in an ad-hoc way in a branch here: https://github.com/cbeck88/frozen/tree/pmh_seeds

    However, I'm having problems with runtime performance now -- it seems that when I compile with clang, invoking elsa twice instead of once makes us slower than gcc for unordered_map<int, int>.

    My hope would be that this would help users who are troubleshooting "possible infinite loop" etc. Since basically, if the initial hash is bad and they get a bucket with half of the items in it, (or even, several buckets with sqrt(n) items), I would expect the algorithm to time out.

    Do you think that my assessment is wrong? Do you think it would be a good idea to try to simplify elsa so that it can be run twice as fast? Do you think instead of using elsa for the initial hash, a different hash should be used, and elsa should only be used for the second part?

    Where did the elsa hash algorithm come from?

    opened by cbeck88 7
  • Branchless binary search

    Branchless binary search

    Since the size of your frozen::set is known at compile time, you should be able to implement a branchless binary search for the lookup when the number of elements is a power of 2 minus 1. I found an old piece of code I wrote some time ago which uses such a branchless binary search:

     * This function inserts first in [first+1, first+8), which is a
     * sorted sequence.
    template<typename RandomAccessIterator, typename Compare=std::less<>>
    auto front_insert8(RandomAccessIterator first, Compare compare={}) const
        -> void
        auto it = first;
        it += compare(it[4], *first) << 2;
        it += compare(it[2], *first) << 1;
        it += compare(it[1], *first) << 0;
        switch (std::distance(first, it))
            // rotate_left rotates the sequence beginning at the passed
            // iterator by N positions to the left
            case 1: rotate_left<2>(first); break;
            case 2: rotate_left<3>(first); break;
            case 3: rotate_left<4>(first); break;
            case 4: rotate_left<5>(first); break;
            case 5: rotate_left<6>(first); break;
            case 6: rotate_left<7>(first); break;
            case 7: rotate_left<8>(first); break;
            default: break;

    When I benchmarked this version, it was globally faster than the usual one. You could try to specialize your own lower_bound function to use a branchless binary search when possible and see whether it's faster :)

    Note that it probably isn't better than a regular binary search when the compare function it self isn't branchless.

    opened by Morwenn 7
  • feature: heterogeneous lookup for ordered containers

    feature: heterogeneous lookup for ordered containers

    1. Deleted useless is_transparent from map.
    2. Fixed type safety of map.
    3. Added heterogenous lookup for set.

    CompareKey isn't overcomplication, as I said before. It's an adaptor for bound functions, so that there is no need to write additional overloads.

    opened by impugachev 6
  • Fix control flow around bucket overflows in make_pmh_buckets

    Fix control flow around bucket overflows in make_pmh_buckets

    This is a correctness issue reported in frozen issue #95

    The issue is that the continue is meant to continue the outer while (1) loop, so that we wipe out the buckets and try another seed. As written, the code will simply not place the item that overflowed. Then lookup of that item will likely fail.

    I have never seen this happen in practice, I think because we make the buckets pretty large, like sqrt(N), during the construction. So likely overflow never occurs. Otherwise I would expect the map to give a junk answer in practice.

    I think I introduced this bug in this commit: https://github.com/serge-sans-paille/frozen/commit/2897706fc23936a04666e9e9e3d60903c7866c7b#diff-b7220304cb6955468f4a0071ade6af7e

    opened by cbeck88 6
  • GCC 9.1.1 strict-overflow warnings

    GCC 9.1.1 strict-overflow warnings

    GCC warns when enabling -Wstrict-overflow=n for n > 1. Some of the warnings can be suppressed with #pragmas, but others can't as they are triggered at the call site during constexpr expansion.

    [build] .../frozen-master/include/frozen/bits/pmh.h:174:8: error: assuming pointer wraparound does not occur when comparing P +- C1 with P +- C2 [-Werror=strict-overflow]
    [build]   174 |   auto buckets = step_one.get_sorted_buckets();
    [build]       |        ^~~~~~~
    [build] .../frozen-master/include/frozen/bits/pmh.h:228:1: error: assuming pointer wraparound does not occur when comparing P +- C1 with P +- C2 [-Werror=strict-overflow]
    [build]   228 | }
    [build]       | ^
    opened by invexed 6
  • Frozen bimap?

    Frozen bimap?

    In a lot of use cases for frozen, such as enum-to-string mappings, it feels like it would be very useful to have the option for looking up values from either side. Obviously, one could do this by manually making another map with the keys and values swapped, or, even use a macro or code generator to do so, but those solutions tend to be either annoying to implement and use, or relatively fickle.

    That in mind, I've implemented a quick and "simple" bimap on top of frozen::unordered_map, which can handle constexpr elements, and looks something like this:

    template <typename T1, typename T2>
    struct swappedPair {
        constexpr std::pair<T2, T1> operator()(const std::pair<T1, T2>& inPair) {
            return {inPair.second, inPair.first};
    template <typename K, typename V, std::size_t N>
    struct FrozenBimap {
        const frozen::unordered_map<K, V, N> left;
        const frozen::unordered_map<V, K, N> right;
        constexpr std::array<std::pair<V, K>, N> makeR(std::pair<K, V> const (&items)[N]) {
            return [] <std::size_t... I>(std::pair<K, V> const (&s)[N], std::index_sequence<I...>) -> std::array<std::pair<V, K>, N> {
                return {swappedPair<K, V>{}(s[I]) ...};
            }(std::forward<std::pair<K, V> const[N]>(items), std::make_index_sequence<N>{});
        constexpr FrozenBimap() = delete;
        constexpr FrozenBimap(std::pair<K, V> const (&items)[N]) :
            left(frozen::unordered_map<K, V, N>{items}),
            right(makeR(items)) {
        constexpr FrozenBimap(std::array<std::pair<K, V>, N> const& items) :
            left(frozen::unordered_map<K, V, N>{items}),
            right(makeR(items)) {

    Would something like this be useful as a part of frozen proper? I could try to further refine it then do a PR. Note that this version only works with C++20, but I'm pretty sure C++14 would be doable, although not quite as clean on the makeR method's implementation. Also, obviously because the values are keys for the second map, this would likely be limited to both keys and values being immutable.

    opened by RazielXYZ 0
  • How to create a string key at runtime?

    How to create a string key at runtime?

    Here is non-frozen code. I need the key being looked up to come from data outside the program... i.e. not a literal. Does frozen do this or does it not solve that gperf-like problem?

            std::unordered_map<std::string_view, int> m = {
            std::string line;
            std::getline(std::cin, line);
            fprintf(stderr,"%s\n", line.c_str());
            fprintf(stderr,"%.*s index: %d\n", (int)line.length(), line.c_str(), m.at({line.c_str(),line.length()}));
    opened by jgm-ktg 3
  • Status of cvector and carray

    Status of cvector and carray

    Hi, I would like to ask, whether cvector and carray are consisted part of public symbols or for internal usage only.

    I have been playing with them in my project an I have done some extending. Would you be interested in PR?

    opened by jdupak 0
  • Add map/set final() method?

    Add map/set final() method?

    final method should return some map type without insert and other non const methods.

    In that case you can use eytzinger/btree/vEB (add user ability to choose) for more efficient search.

    What do you think?

    opened by MBkkt 1
  • Added `insert()`, `erase()`, and `reserve()`/`resize()` support to vector.

    Added `insert()`, `erase()`, and `reserve()`/`resize()` support to vector.

    Note: This is currently based on top of https://github.com/serge-sans-paille/frozen/pull/123, which has yet to be merged, and as a result includes all of the commits from that PR. Only the last 3 commits in this PR are relevant here. Once https://github.com/serge-sans-paille/frozen/pull/123 is merged, I will update this PR accordingly.

    opened by adamshapiro0 0
Easy to use, header only, macro generated, generic and type-safe Data Structures in C

C Macro Collections Easy to use, header only, macro generated, generic and type-safe Data Structures in C. Table of Contents Installation Contributing

Leonardo Vencovsky 347 Jan 8, 2023
nanoplan is a header-only C++11 library for search-based robot planning.

nanoplan is a header-only C++11 library for search-based robot planning. The primary design goals are correctness, ease-of-use, and efficiency (in tha

Jordan Ford 14 May 17, 2022
Simple Useful Libraries: C++17/20 header-only dynamic bitset

dynamic_bitset Simple Useful Libraries: C++17/20 header-only dynamic bitset Requirements To use this dynamic bitset, you will need a C++17 (or later)

Maxime Pinard 118 Dec 12, 2022
A family of header-only, very fast and memory-friendly hashmap and btree containers.

The Parallel Hashmap Overview This repository aims to provide a set of excellent hash map implementations, as well as a btree alternative to std::map

Gregory Popovitch 1.7k Jan 9, 2023
C++14 header only result monad implementation

constexpr Either <S, E> C++14 header only result monad implementation. Features constexpr support 0 dependencies single header Status in development T

null 4 Oct 7, 2021
ring-span lite - A C++yy-like ring_span type for C++98, C++11 and later in a single-file header-only library

ring-span lite: A circular buffer view for C++98 and later Contents Example usage In a nutshell Dependencies Installation Synopsis Reported to work wi

Martin Moene 127 Dec 28, 2022
Header-only compile time key-value map written in C++20.

C++ Static Map Header-only compile time key-value map written in C++20. Getting Started Simply add the files in your source and #include "@dir/Static_

null 1 Oct 19, 2021
Multi-Purpose Header-Only C Data Structures

USAGE These header files are meant to be a simple means of using datastructures in a C project. They are universally useable with any other C datatype

Andre Schneider 2 Jul 15, 2022
A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.

K-HASH A simple single header 64 bit hash function using only add, sub, ror, and xor. This a just general-purpose hash function for like making hash m

null 70 Dec 27, 2022
Step is a C++17, header-only library of STL-like algorithms and data structures

Step is a C++17, header-only library of STL-like algorithms and data structures. Installation git clone --depth 1 https://github.com/storm-ptr/step.gi

storm-ptr 3 Sep 1, 2022
R :package: and header-only C++ library for geospatial space-division based compression and encoding

spress spress provides utilities for encoding and compressing geospatial objects, such as sf objects. Installation This package requires C++11 for com

UF-OKN 5 Dec 9, 2021
R :package: and header-only C++ library for geospatial space-division based compression and encoding

spress spress provides utilities for encoding and compressing geospatial objects, such as sf objects. Installation This package requires C++11 for com

UF-OKN 5 Dec 9, 2021
Play GTA San Andreas Multiplayer with mouse only and no keyboard

Play GTA SAMP with your mouse and no keyboard! For some reason some people think it's a troll or an inside joke, IT IS NOT! This is a legit mod for th

iAmir 21 Aug 31, 2022
Like neofetch, but much faster because written in c. Only Linux.

fastfetch fastfetch is a neofetch like tool for fetching system information and displaying them in a pretty way. It is written in c to achieve much be

Linus Dierheimer 490 Jan 7, 2023
C header library for typed lists (using macros and "template" C).

vector.h C header library for typed lists (using macros and "template" C). Essentially, this is a resizable array of elements of your choosing that is

Christopher Swenson 33 Dec 19, 2022
Miniz in a single C header.

MiniMiniZ This the amalgamated miniz library in a single header. Usage Copy miniminiz.h into your C or C++ project, include it anywhere you want to us

Eduardo Bart 8 Jul 20, 2022
A reverse engineering tool to interactively reconstruct structures and generate header files

ReGenny ReGenny is a reverse engineering tool to interactively reconstruct structures and generate usable C++ header files. Header file generation is

null 91 Dec 28, 2022
C header to execute user-space functions in ring 0

r0e - Execute User Code in Ring0 This small header allows executing functions in your application in ring 0, i.e., with kernel privileges. Use cases i

Michael Schwarz 11 Nov 11, 2022
Bsl - Rust 2018 and C++20, "constexpr everything", AUTOSAR compliant header-only library intended to support the development of critical systems applications

Description The Bareflank Support Library (BSL) is a Rust 2018 and C++20, "constexpr everything", AUTOSAR compliant header-only library intended to su

Bareflank 76 Dec 8, 2022