有顺序保证的阻塞队列

Blocking queue with order guarantee

我有 8 个线程以条带形式处理图像。条带按光栅顺序排列。当每个线程完成一个 strip 时,该线程将其 strip id 号添加到一个阻塞队列中。我希望队列仅在数字从 0 到 N 的顺序时允许弹出。因此,无论线程添加其 ID 的顺序如何,队列输出都将为 0,1,2,3,... ..N. STL 中是否存在具有此功能的现有结构?

我想一个简单的实现是一个带有从 0 开始的计数器的普通队列。当添加 0 时,它弹出并将计数器移动到 1,并一直弹出直到找不到匹配项。但这听起来效率不高。

编辑:如果我包装一个 STL 优先级队列使其阻塞,这可能会起作用。

这看起来根本不像队列!队列应该只支持 push_back 和 pop_front。里面没有偷看。

我会建议 map<ID,image>,并保留最后处理的图像 ID。然后您可以快速检查该地图的 front() 是否在您的序列中,然后将其删除。

你想要的结构是一个最小堆(见std::priority_queue)。这给出了具有最低 ID 的元素。

每当新添加的元素在队列的开头时唤醒消费者线程。

一口气消费完所有顺序的元素。