C++Now 2014

To write correct and efficient concurrent and parallel programs you need concurrent data structures. Simply slapping a mutex on top of a vector is rarely the right solution. Functional programmers have discovered a great trick – they use immutable data structures that are by definition thread safe. But how can you write programs if you can’t modify your data? And why can’t you just use a const vector?

It turns out that there is a whole science to designing efficient functional data structures. There is sharing and mutation behind the scenes and some tricky synchronization problems. There are tricks to defer copying of data using lazy evaluation that let you, for instance, reverse a singly linked list in constant time (well, sort of).

In my talk, I’ll introduce you to the implementation of efficient thread-safe data structures in C++ based on lessons from functional programming -- in particular from Chris Okasaki’s seminal book, Purely Functional Data Structures.