c++ - 并发无锁单链表 C++：并发会影响接口吗？迭代器还有意义吗？

Question

我即将在 C++ 上实现一个并发链接（单独）列表，并想与以前可能遇到类似挑战的人澄清一些观点。背景：最初该列表计划成为跳跃列表的一部分，而跳跃列表又是内存索引的一部分。当我开始实现这个时，我会想为什么不创建一个通用解决方案（以类似 stl 的方式），它可以在跳过列表之外使用。但似乎并发容器的工作方式可能与单线程容器有很大不同。例如，插入和删除操作将迭代器作为 std::list 中的输入参数，但在并发实现的情况下，如果另一个线程修改其附近的列表，则迭代器将变得无效。

如果列表是跳过列表的“层”，这不是问题，因为在这种情况下它是排序的，并且可以避免迭代器。但是我很好奇是否有人尝试实施通用解决方案来解决问题。

另一个问题.. 让这样的容器与 stl 算法兼容是否值得？似乎它们中的大多数可能由于并发而失败。

提前致谢！

Answer 1

创建实现接口的并发链表容器非常容易std::list，并且完全兼容stl算法。您只需为每个操作锁定整个事物。当然，这不是无锁的，这不是你想要的。

关键是并发性并不会天生就无法std::list实现——让它变得困难的是特定的实现细节，而您的无锁标准可能会让这变得困难。std::list只有在有意义的情况下，您才应该完全做到这一点；因为这个接口特别要求所有迭代器在列表的整个修改过程中都必须保持有效，所以这里的事情可能会有点麻烦。我不知道你用什么无锁算法来实现这个，所以我不能评论。

只要满足迭代器保证，即使容器没有实现std::list，容器也将与 stl 算法兼容，所以听起来你的问题是确保满足这些迭代器保证。