Windows 提供了一个无锁的单链表，如本页所述： Win32 SList
我想知道是否存在围绕此功能的良好 C++ 包装器。当我说好时，我的意思是它尽可能地导出通常的 STL 接口，支持迭代器等。我宁愿使用别人的实现也不愿坐下来编写一个 STL 类型的容器。
问问题
1337 次
4 回答
5
您将永远无法在 SList 之上分层 STL 样式界面。为了避免内存管理问题，列表中唯一可访问的节点是列表的头部。访问该节点的唯一方法是将其从列表中弹出。这可以防止两个线程拥有相同的节点，然后一个线程删除该节点，而另一个线程仍在使用它。这就是我所说的“内存管理问题”，也是无锁编程中的常见问题。您总是可以弹出第一个节点，然后跟随 SLIST_ENTRY 结构中的“下一个”指针，但这是一个非常糟糕的主意，除非您可以保证列表不会缩小，并且在您阅读它时节点被释放。当然，这仍然会从列表中删除头节点。
基本上你试图错误地使用 SList 。对于听起来你想做的事情，你只需要使用一个 STL 容器并使用锁来保护对它的访问。STL 算法不适用于 SList 等可变的无锁数据结构。
话虽如此，您可以围绕 SList 创建一个 C++ 包装器，但它与 STL 不兼容。
于 2009-06-12T17:30:33.423 回答
3
值得注意的是，问题中引用的页面上的已发布接口实际上并未实现链接列表（尽管这可能是底层结构）-它实现了堆栈。因此，如果您想要 std::list 等类提供的链表功能，这可能不适合您。
还要注意堆栈不能支持迭代器（它们基本上只支持推送和弹出），所以很多关于支持迭代器和算法的讨论都是一厢情愿的想法。
于 2009-04-26T17:42:44.907 回答
1
您可以使用 boost 和 ::boost::iterator_facade 快速启动并运行。
不，它不是最优的或可移植的，迭代器语义是你应该听到 Alexandrescou 在 DevCon 突然反对的东西。您没有锁定容器，而是锁定（并可能重新锁定和解锁）操作。而锁定操作意味着串行执行，非常简单。有大量迭代器操作将对正在创建的抽象造成不必要的惩罚。
从火星的角度来看，迭代器隐藏了指针，并隐藏在一个半 OO 概念下，这与 OO-vs-Distributed 开发的几率一样。我肯定会使用“程序”界面并让用户/维护者付费注意为什么它是必要的。无锁操作仅与围绕它的“所有并行代码”一样好。自 96 年以来，随着人们不断给予 scoped_lock 包装重新发明的经典示例，它产生了漂亮的串行代码。
或者使用 atomic 和 Sutter 的 DDJ 条目作为穷人前进道路的参考（以及后来 10 多年的 Pentium Pro 无序性）。
（真正发生的事情是 boost 和 DDJ 在 .net 和 MS CCR 列车之后运行，该列车在不变性之后运行，以及英特尔列车在无锁开发的良好 OO 类似抽象之后运行。问题是它不能做得很好，有些人一次又一次地与之抗争；很像 TBB 的 concurrent_vector 胡说八道。同样的原因异常从来没有实现为非问题，尤其是跨环境，以及 C++ 未充分利用 CPU 中的向量处理的同样原因编译器等等等等..)
于 2009-04-28T00:29:35.747 回答
-1
我认为一个薄包装应该很容易编写。1-2 页之类的东西，可能都在 .h 文件中。而不是梳理谷歌我已经自己写了。
于 2009-04-26T17:09:25.610 回答