2

我有以下要求：

我需要一个带有键值对的数据结构（如果有帮助，键是整数）。

我需要以下操作：-

  1. 迭代（最常用）
  2. 插入（第二常用）
  3. 按键查找和删除（最少）

我计划在结构上使用多个锁来进行并发访问。理想的数据结构是什么？

地图还是无序地图？

我认为无序映射是有道理的，因为我可以在 O(1) 中插入，在 O(1) 中删除。但我不确定迭代。与地图相比，性能有多差？

另外，我计划在块上使用多个锁而不是整个结构。有什么好的实现例子吗？

谢谢

4

5 回答 5

3

迭代器递增的速度O(1)适用于两个容器，尽管您可能会从std::unordered_map.

除了较慢的O(log N)查找/插入/擦除功能之外std::map，另一个区别是std::map提供双向迭代器，而较快的（摊销O(1)元素访问）std::unordered_map仅提供前向迭代器。

Anthony Williams的优秀书籍C++ Concurrency in Action: Practical Multithreading提供了一个多线程的代码示例，unordered_map每个条目都有一个锁。如果你正在做严肃的多线程编码，强烈推荐这本书。

于 2013-08-05T11:15:18.370 回答
0

为什么不简单地使用在TBB和Concrtconcurrent_unordered_map中都可以找到的现有。

于 2013-08-05T11:34:56.953 回答
0

你有没有想过尝试一个std::deque推理如下：

  1. 迭代速度很快 - 数据应该或多或少地打包关闭（与列表不同）
  2. 插入（在任一端）应该很快 - 双端队列中的数据永远不会调整大小
  3. 迭代和删除缓慢（但不常见的用例）。

如果最后两种情况很常见，std::list则可以使用 a。还可以考虑测试 std::vector`，因为它的缓存效率更高。

unordered_map由于迭代哈希表中大量未使用的元素，在 an 中的迭代可能会很慢。插入将停止，直到碰撞级别变得无法容忍，此时整个数据结构将需要重新布局。

maps 的迭代速度相对较快，只是数据元素可能相距甚远。由于这需要重新平衡红黑树，插入可能会很慢。

unordered_maps 的主要用例是用于快速查找 (O1)。法线贴图具有快速查找（O log n）但迭代性能要好得多。

于 2013-08-05T12:28:18.363 回答
0

如果你有严格的实时要求，我会推荐 map over unordered_map。std::map 保证了 100% 的性能，但 std::unordered_map 可能会在某些关键的极端情况下进行重新哈希并完全破坏实时性能。一般来说，如果我需要绝对保证最坏情况的性能，我更喜欢红黑树（std::map）而不是哈希表（std::unordered_map）。

于 2014-10-09T22:59:31.243 回答
0

迭代在unordered_map. 它的效率比向量低一点，但在很大程度上不是这样。

与往常一样，您需要针对您的用例进行基准测试，并与其他容器类型进行比较，如果它是您代码的关键部分。

不确定“块而不是整个结构上的多个锁”是什么意思 - 任何容器更新都需要为整个容器锁定......

于 2013-08-05T11:13:31.313 回答