免费实现“有界优先队列"在 C++ 中 [英] Free implementation of "bounded priority queue" in C++

问题描述

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

I'm looking for a free software implementation of the bounded priority queue abstraction in C++. Basically, I need a data structure that will behave just like std::priority_queue but will at all times hold the "best" n elements at most.

示例:

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

有谁知道这种事情的一个很好的实现?有相关经验吗?

Does anyone know of a good implementation of such thing? Any experience with it?

推荐答案

我认为 这个主题 可能就是你要找的.如果您想抢先一步，您可能需要考虑构建 Boost 的实现 d_ary_heap_indirect，它是 Boost.Graph 的一部分(在 d_ary_heap.hpp 中).如果你做得很好，你可以把它提交给 Boost.它可以做一个很好的补充，因为这样的实现肯定有很多用途.

I think that the algorithm discussed in this thread is probably what you are looking for. If you want to get a head start, you might want to consider building upon Boost's implementation d_ary_heap_indirect which is part of Boost.Graph (in d_ary_heap.hpp). If you do a good job with it, you might submit it to Boost. It could make a nice little addition, because such an implementation certainly has many uses.

这篇关于免费实现“有界优先队列"在 C++ 中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！