The Holy Grail - A Persistent Hash-Array-Mapped Trie for C++

Explore the concept of Persistent Hash-Array-Mapped Trie (HAMT) for C++ in this comprehensive conference talk from C++Now 2017. Dive deep into the workings of this efficient data structure that combines characteristics of trees and hash tables, offering superior performance and memory efficiency. Learn how HAMTs can be easily made persistent, making them ideal for concurrent and functional programming applications. Examine a reference implementation proposed as a Boost library, and discover its practical applications and performance characteristics. Compare HAMTs with existing C++ associative containers like set, map, unordered_set, and unordered_map, understanding their advantages and trade-offs. Follow along as the speaker builds the data structure from the ground up, covering topics such as insertion techniques for integers and strings, bit counting, chunk and leaf alignment, and version control in persistent data structures.

Introduction
Sex
Characteristics
Persistent
List
Tree
RedBlack Trees
Binary Trees
The Solution
Inserting 100k integers
Inserting 100k strings
Counting set bits
Chunk
Leaf
Alignment
Create
Branch
Unpopulated
CreateEmpty
CreatePair
Insert
Version