我正在使用 std::map 来实现我的本地哈希表，它将被多个线程同时访问。 我做了一些研究，发现 std::map 不是线程安全的。 所以我会使用一个互斥锁来对 map 进行插入和删除操作。 我计划有单独的互斥量，每个映射条目一个，以便可以独立修改它们。
我是否需要将查找操作也放在临界区下？ 插入/删除操作会影响查找操作吗？ 有没有比使用 std::map 更好的实现来处理所有事情？
最佳答案
二叉树并不特别适合多线程，因为重新平衡可能会在树范围内的修改中退化。此外，全局互斥锁会对性能产生非常负面的影响。
我强烈建议使用已经编写好的线程安全容器。例如，Intel TBB包含一个 concurrent_hash_map。
但是，如果您想学习，这里有一些关于构建并发排序关联容器的提示(我相信完整的介绍不仅超出我的能力范围，而且也不合适，在这里) .
读者/作家
您可能想要使用 Reader/Writer Mutex，而不是常规的 Mutex。这意味着并行读取，而写入保持严格顺序。
自己的树
您还可以构建自己的红黑树或 AVL 树。通过为每个节点添加一个 Reader/Writer Mutex 来扩充树结构。这允许您只阻塞树的部分，而不是整个结构，即使在重新平衡时也是如此。 例如键分开足够远的插入可以是平行的。
跳过列表
链表更适合并发操作，因为您可以轻松隔离修改区域。
A Skip List建立在这种优势之上，但增加了结构以提供 O(log N) key 访问。
遍历列表的典型方法是使用hand over hand 习惯用法，也就是说，在释放当前节点的互斥量之前获取下一个节点的互斥量。跳过列表添加了第二个维度，因为您可以在两个节点之间跳水，从而释放它们(并让其他步行者走在您前面)。
实现比二叉搜索树简单得多。
持久性
另一个有趣的部分是持久(或半持久)数据结构的概念，这在函数式编程中很常见。二叉搜索树特别适合它。
基本思想是永远不要更改节点(或其内容)一旦存在。为此，您可以共享一个可变的 head，它将指向更高版本。
- 阅读:复制当前头部，然后放心使用(信息不可变)
- 写入:您将在常规树中修改的每个节点都被复制，拷贝被修改，因此您每次都重建树的一部分(直到根)，并更新head 指向新的根。有一些有效的方法可以重新平衡树的下降。 写入是顺序的
主要优点是 map 版本始终可用。也就是说，即使另一个线程正在执行插入或删除操作，您也始终可以读取。此外，由于读取访问只需要一次并发读取(复制根指针时)，它们几乎是无锁的，因此具有出色的性能。
引用计数(内在)是这些节点的 friend 。
注意:树的拷贝非常便宜:)
我不知道并发跳跃列表或并发半持久二进制搜索树在 C++ 中的任何实现。
关于c++ - 设计问题:std::map 的线程安全，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7078785/