Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

CppNow via YouTube

Overview

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.

Syllabus

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

Taught by

CppNow

Reviews

Start your review of The Holy Grail - A Persistent Hash-Array-Mapped Trie for C++

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.