不可变数据结构的卖点之一是它们可以自动并行化。如果没有发生变化,则可以在线程之间传递对功能数据结构的引用,而无需任何锁定。
我开始思考如何在 C++ 中实现函数式数据结构。假设我们在数据结构的每个节点上都有一个引用计数。 (功能数据结构在数据结构的旧成员和更新成员之间共享结构,因此节点不会唯一属于一个特定的数据结构。)
问题是,如果引用计数在不同的线程中更新,那么我们的数据结构就不再是线程安全的。将互斥锁附加到每个节点既昂贵又违背了使用不可变数据结构进行并发的目的。
有没有办法让并发的不可变数据结构在 C++(和其他非垃圾收集环境)中工作?
最佳答案
有无锁引用计数算法,参见,例如Lock-Free Reference Counting , Atomic Reference Counting Pointers .
另请注意,C++0x(可能很快会成为 C++11)包含原子整数类型,尤其是针对此类目的。
关于c++ - 功能/不可变数据结构在非垃圾收集上下文中是否仍然对并发有用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7253458/