我必须设计一个要在多线程环境中使用的数据结构。基本 API 很简单:插入元素、删除元素、检索元素、检查元素是否存在。该结构的实现使用隐式锁定来保证单个 API 调用的原子性。在我实现这个之后，很明显，我真正需要的是跨多个 API 调用的原子性。例如，如果调用者需要在尝试插入元素之前检查元素的存在，即使每个 API 调用都是原子的，他也不能原子地执行此操作:
if(!data_structure.exists(element)) {
data_structure.insert(element);
}
这个例子有点尴尬，但基本的一点是，在我们从原子上下文返回后，我们不能再相信“存在”调用的结果(生成的程序集清楚地显示了两个调用之间上下文切换的可能性很小)。
我目前要解决的问题是通过数据结构的公共(public) API 公开锁。这样，客户将不得不显式地锁定事物，但至少他们不必创建自己的锁。对于这类问题，是否有更好的众所周知的解决方案？只要我们还在，你能推荐一些关于线程安全设计的优秀文献吗？
编辑:我有一个更好的例子。假设元素检索返回一个引用或指向存储元素的指针，而不是它的副本。调用返回后，如何保护调用者安全地使用此指针\引用？如果您认为不返回副本是一个问题，那么请考虑深拷贝，即对象也应该复制它们在内部指向的另一个对象。
谢谢你。
最佳答案
您要么提供外部锁定机制(不好)，要么重新设计 API，如 putIfAbsent .后一种方法例如用于 Java 的 concurrent data-structures.
而且，当涉及到这些基本集合类型时，您应该检查您选择的语言是否已经在其标准库中提供了它们。
[编辑]澄清:外部锁定对类的用户不利，因为它引入了另一个潜在错误来源。是的，有时候，对于并发数据结构的性能考虑确实比外部同步数据结构更糟糕，但这些情况很少见，然后它们通常只能由比我有更多知识/经验的人解决/优化。
一个可能很重要的性能提示位于 Will's answer以下。
[/编辑]
[edit2]给定你的新例子:基本上你应该尽可能地保持集合的同步和元素的分离。如果元素的生命周期与它在一个集合中的存在绑定(bind)，那么您将遇到问题；当使用 GC 时，这种问题实际上变得更简单了。否则，您将不得不使用一种代理而不是原始元素才能在集合中；在最简单的 C++ 情况下，您可以使用 boost::shared_ptr ，它使用原子引用计数。在此处插入通常的性能免责声明。当您使用 C++ 时(我怀疑您谈论指针和引用)，boost::shared_ptr 的组合和 boost::make_shared应该够用一段时间了。
[/编辑2]
关于multithreading - 线程安全的数据结构设计，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2476505/