CppCon 2018

This talk introduces frozen, an open source, header-only library that provides alternatives to std::map, std::set, std::unordered_map and std::unordered_set, with the extra constraint of making these data structures not mutable.
In exchange, their constructor is marked as constexpr, which makes it possible to initialize the containers at compile time, avoiding binary intialization cost and, as a side effect, static initialization order fiasco. As the whole interface is constexpr, they can even be used for meta-programming :-)

The talk details how a priori knowledge of the container size and values is taken advantage of to make unordered containers collision free, providing faster lookups than the standard containers. The design of an almost branch-free version of the search in the ordered containers will also be presented.

As a follow-up, we will also discuss the implementation of ``std::search`` for strings in the context of frozen, when the needle is known at compile time, leading to a reflexion on dynamic vs. static tradeoff for a class of algorithm.

The frozen library is being used at Tesla to store static configuration with low memory footprint and fast initialization, at QuarksLab to statically encode enumeration ＜＞ string representation in the LIEF library, but also to sucessfully store thousands of html entities to html code. It is avilable online at https://github.com/serge-sans-paille/frozen .