锁定免费的非分配集合

Question

我正在寻找一个集合数据结构：

1. 线程安全
2. 锁定免费
3. 不分配（摊销或预先分配是罚款）
4. 非侵入式
5. 不使用异国情调的内在函数

元素顺序无关紧要。堆栈，队列，包，一切都很好。我找到了很多满足这五个要求中的四个的例子，例如：

• .NET的List不是线程安全的。
• 如果我在上面放一个互斥锁，那么它就不会锁定。
• .NET的ConcurrentStack是线程安全的，无锁，使用简单的CompareExchange，但为每个元素分配一个新的Node。
• 如果我将next指针从Node移动到元素本身，那么它就是侵入性的。
• Array based lock free data structures往往需要多字内在函数。

我觉得我错过了一些非常明显的东西。这应该是一个解决的问题。

Answer 1

• .NET的ConcurrentQueue满足所有五个要求。它在后备存储空间不足时进行分配，类似于List<T>，但只要有额外的容量，就不会发生分配。不幸的是，预先保留额外容量的唯一方法是使用相同大小的集合初始化它，然后将所有元素出列。
• .NET的ConcurrentBag也是如此