“有界优先级队列”的自由实现在 C++
我正在寻找 C++ 中有界优先级队列抽象的免费软件实现。基本上，我需要一个行为类似于 std::priority_queue 的数据结构，但始终最多保存“最佳”n 个元素。
示例：
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
有谁知道这样的事情的良好实施吗？有这方面的经验吗？
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.
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
Does anyone know of a good implementation of such thing? Any experience with it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为此线程中讨论的算法 可能就是您正在寻找的。如果您想抢占先机，您可能需要考虑基于 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_indirectwhich is part of Boost.Graph (ind_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.为什么不使用带有仿函数/比较函数的 std::vector 并将其 std::sort() 按正确的顺序排列？
代码可能非常简单
Why not use a std::vector with a functor/comparison function and std::sort() it into the correct order?
The code is probably pretty trivial