可搜索的环形缓冲区

Question

我想知道是否有人可以建议一种c++数据结构，它既具有环缓冲区(有保证的有限存储)的能力，同时又允许高效的线程安全地搜索指定数据的环缓冲区？

Answer 1

Intel TBB containers非常适合解决这类问题。

concurrent_unordered_map应该为你的情况做一些事情，但是如果你真的想要一些环结构，你可能可以使用concurrent_bounded_queue并进行自己的推送来模拟环的行为(见下文)。然而，这种结构的搜索复杂度是线性的，而不是地图中的对数复杂度。

template<class T>
struct concurrent_ring : tbb::concurrent_bounded_queue<T>
{
    void push(const T& t) 
    {
        while(!tbb::concurrent_bounded_queue<T>::try_push(t)) 
           pop();
    }
}