问题标签 [concurrentskiplistmap]

我正在寻找C++ 中的无锁数据结构来替换以下内容：

该集合应该支持.insert()并且.size()最多具有 O(logN) 复杂度，具有迭代器，并且应该能够使用自定义比较器保持其顺序。基本上与Java中的相同ConcurrentSkipListSet。理想情况下，它应该独立于平台。

我正在查看 CDS： http: //libcds.sourceforge.net/doc/cds-api/modules.html但不确定哪种数据结构可以实现目标。该文档对于某些数据结构并没有真正的复杂性。

任何建议都会很棒，谢谢！

Java 集合框架中的大多数类默认情况下是不同步的，但如果您需要它们是线程安全的，可以将它们制成同步的东西。同步有性能损失，所以如果你写的东西不需要是线程安全的，你最好使用非同步版本。

但ConcurrentSkipListMap不遵循这个方案。没有不同步的版本。为什么SkipListMap不需要线程安全的应用程序没有更快的非同步，与集合框架的其余部分一致？

我能想到的是，跳过列表的最简单实现已经是线程安全的，因此拥有同步版本不会有性能损失。这会有些道理，但是看一下源代码并不能完全证明这一点。尽管代码中没有synchronized块，但 Javadoc 确实以

此类实现 SkipLists 的并发变体...

这表明它正在不遗余力地修改算法以使其成为线程安全的。后来，我们读到

这些列表中的基本思想是在删除时标记已删除节点的“下一个”指针，以避免与并发插入冲突......

这听起来好像涉及某种开销。

仅仅是这个开销是如此之小以至于不值得拥有一个非线程安全的SkipListMap吗？

我有一个键和值的 ConcurrentSkipListMap。保持键的顺序非常重要。

当我尝试在特定位置插入新值时出现问题。插入值的唯一一种方法是将这个值放在最后一个位置的 put()。

使用 replace 方法只能编辑值，不能编辑键。

可能吗？我能做些什么？你能告诉我另一堂课吗？

最近在探索时，ConcurrentSkipListMap我浏览了它的实现，发现它的 put 方法不是线程安全的。它在内部调用doPut实际添加项目。但是我发现这个方法并没有使用任何类似于ConcurrentHashMap.

因此，我想知道是否add是线程安全的。看看这个方法，它似乎不是线程安全的——也就是说，如果这个方法由两个线程同时执行，那么可能会出现问题。

我知道ConcurrentSkipListMap内部使用跳过列表数据结构，但我希望add方法是线程安全的。我理解有什么问题吗？真的ConcurrentSkipListMap不是线程安全的吗？

全部，

遇到 ConcurrentModificationException 问题并努力寻找解决方案，部分原因是我在迭代列表时看不到我在哪里修改列表......有什么想法吗？我已经突出显示了导致问题的行 (it3.remove())。这个真的是停不下来了。。

编辑：堆栈跟踪：

第 1621 行对应于我上面引用的代码中的 it3.remove()。

假设我有多个线程向ConcurrentSkipListMap. 我有另一个线程在预定义的时间段上运行集合并使用迭代器更新它的数据。考虑到并发访问如何做到这一点。如何迭代？迭代器是否支持弱一致性？

我正在查看 Java 的 ConcurrentSkipListMap，因为它是一个引人入胜的数据结构并且似乎适用于我的使用，但迭代器有一些有趣的行为，这对我来说似乎违反直觉。以下面的代码为例：

这个想法是地图用值初始化，创建一个迭代器，然后开始迭代。在这些操作之间，另一个线程将“Jon”放入地图中。为简单起见，在我的示例中，我没有使用实际的线程和循环，而是将代码按人为的顺序排列，并直接引用每个项目。

我预计输出是true/true，但实际输出是true/false。深入研究 Map 的实现，我发现迭代器缓存了下一个节点/值（在其 Advance() 方法中）。此缓存将跳过在 iterator.next() 被调用后立即创建的任何下一个项目。为什么它会贪婪地缓存下一项，而不是等到调用 Iterator next() 方法后再推进下一项？

我想使用基于比较器的键值映射。这将具有读取和罕见的写入操作（每 3 个月通过调度程序执行一次）。集合的初始加载将在应用程序启动时完成。另请注意，写入将：

• 向地图添加单个条目
• 不会修改地图的任何现有条目。

ConcurrentSkipListMap 将是一个很好的候选者。对此的get操作是否允许同时访问多个线程？我正在寻找并发非阻塞读取但原子写入。

我不确定是否有问题java.util.concurrent.ConcurrentSkipListSet？我正在尝试将一些对象添加到 ConcurrentSkipListSet （由我自己的比较器维护的顺序）。添加后，我改变了一些对象的状态。我更改的属性包括比较器中使用的属性。现在，当我尝试删除一些对象时，它失败了。该对象不会从 ConcurrentSkipListSet 中删除，并且remove(Object)返回 false。

如果我用 TreeSet 替换 ConcurrentSkipListSet 我看不到这种行为。

不确定我是否在这里做一些愚蠢的事情或遗漏了什么:(。这是一个示例代码片段。

}

输出如下所示：

请注意，此行为并不一致。有时元素会被删除。

我在 OS X 版本 10.11.6 上使用 java 版本“1.8.0_131”。

为破旧的代码道歉。赶紧煮好了。

谢谢。

我有一个ConcurrentSkipListMap. 我需要删除低于 then 的元素key。

这是我如何执行它：

看起来不错，但我对这些事实感到困惑：

1.

返回的地图由此地图支持，因此返回地图中的更改会反映在此地图中，反之亦然。

这是否意味着垃圾收集器不会删除旧值？
即我们删除了旧地图，现在我们有了一张新地图。但是这张新地图是由旧地图支持的。那么，旧地图会发生什么？它会被删除还是会永远留在记忆中？

2.

返回的映射将在尝试在其范围之外插入键时抛出 IllegalArgumentException。

那么，现在我不能放置小于 10.25 且大于上一个最大值的新键？

我很困惑。那么我需要如何正确地从 ConcurrentSkipListMap 中删除元素？