CppCon 2018 has ended
Back To Schedule
Tuesday, September 25 • 16:45 - 17:45
Frozen data structures in C++14

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

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 .


Serge Guelton

Software Engineer, Quarkslab
Serge « sans paille » Guelton is a compiler engineer at QuarksLab where he builds an LLVM-based code obfuscator. He's also the maintainer of the Pythran compiler that turns scientific Python kernels into efficient C++ code.

Tuesday September 25, 2018 16:45 - 17:45 PDT
Copper Mountain Theater (2nd Floor)
  • Data Structures and Algorithms