C++自由实现“有界优先级队列”

我正在寻找一个免费软件实现有界优先级队列C++ 中的抽象。基本上，我需要一个数据结构，其行为就像std::priority_queue但始终保持着“最好的”n最多元素。

Example:

std::vector<int> items; // many many input items
bounded_priority_queue<int> smallest_items(5);
for(vector<int>::const_iterator it=items.begin(); it!=items.end(); it++) {
  smallest_items.push(*it);
}
// now smallest_items holds the 5 smallest integers from the input vector

有谁知道这样的事情有一个好的实施吗？有这方面的经验吗？

我认为中讨论的算法这个线程 https://stackoverflow.com/questions/2933758/priority-queue-with-limited-space-looking-for-a-good-algorithm可能就是您正在寻找的。如果您想抢占先机，您可能需要考虑构建 Boost 的实现d_ary_heap_indirect这是 Boost.Graph 的一部分（在d_ary_heap.hpp）。如果你做得很好，你可以将它提交给 Boost。它可以做一个很好的补充，因为这样的实现肯定有很多用途。