title: Can functional/immutable data structures still be useful for concurrency in a non-garbage collected context?
body: <p>One of the selling points of immutable data structures is that they are automatically parallelizable.  If no mutation is going on, then references to a functional data structure can be passed around between threads without any locking.</p>
  
  <p>I got to thinking about how functional data structures would be implemented in c++.  Suppose that we have a reference count on each node of our data structure.  (Functional data structures share structure between old and updated members of a data structure, so nodes would not belong uniquely to one particular data structure.)</p>
  
  <p>The problem is that if reference counts are being updated in different threads, then our data structure is no longer thread safe.  And attaching a mutex to every single node is both expensive and defeats the purpose of using immutable data structures for concurrency.</p>
  
  <p>Is there a way to make concurrent immutable data structures work in c++ (and other non-garbage collected environments)?</p>