c++ - 可搜索环形缓冲区

Question

我想知道是否有人可以建议一个 c++ 数据结构，它既具有 Ring Buffer 的功能(保证有限存储)，但同时允许对 Ring Buffer 进行高效的线程安全搜索以查找指定数据？

Answer 1

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

concurrent_unordered_map 应该为您的情况做事，但如果您真的想要一些环形结构，您可以使用 concurrent_bounded_queue 并自己推送来模拟环形行为(见下文)。但是，您将使用此结构获得线性搜索复杂度，而不是 map 中的对数复杂度。

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();
    }
}