有无锁的向量实现吗？

Question

谷歌搜索“无锁向量”的第一个结果是由Damian Dechev，Peter Pirkelbauer和Bjarne Stroustrup撰写的一篇研究论文，描述了一个理论上的无锁向量。是否已经实现了这个或任何其他无锁向量？

Answer 1

MS提供ppl::concurrent_vector，英特尔提供tbb::concurrent_vector。在Windows上，至少ppl和tbb是C-Runtime的一部分。

Answer 2

我刚刚在维基百科上查到了向量是什么。

我认为(思考一下，记住)一个完全无锁的版本有点问题。

考虑一下；您创建数组，按照正常方式访问它，等等。为此，您不需要无锁的。当你需要调整大小时，问题就来了。进入并发现这一点的线程需要malloc。这是一个真正独特的操作-在这一点上，其他线程必须阻塞/旋转。如果他们试图提供帮助，例如自己执行malloc，您可能会有许多线程发出malloc。现在可能在实践中，线程的数量是如此之低，这是可以接受的-在这种情况下，你可能有许多线程执行malloc，胜利者自动激活新的内存，失败者看到这一点，然后释放他们的内存。

然后为了执行复制，当一个线程访问一个元素时，我们需要跟踪列表中所有分配的数组，我们通过列表访问它们，最早的先访问它们，直到我们找到我们想要的元素，如果它不在最新的数组中，我们移动它，然后访问它。

然后，我们还需要一种方法，让线程知道它已经移动了最后一个元素，并可以释放该数组，因此我们必须计算元素的数量；因此，我们有潜在的无界分配要求的风险。更重要的是，数据结构(我说的是列表，但也可以是其他东西，尽管可能不是很好)将需要是原子的(因为也许线程可以同时删除一个数组)，原子无锁列表直到最近还是无锁数据结构的顶峰，因为它们很复杂，需要SMR，并且具有复杂的实现。

(我要说的是，直到最近，有人发明了一种无锁的红黑树，整个过程，添加和删除！)

TBH，我不明白为什么有人会使用向量。为什么不直接使用平衡二叉树或散列呢？