Бесплатная реализация «очереди с ограниченным приоритетом» в C ++

Question

Я ищу бесплатную программную реализацию абстракции с ограниченным приоритетом в 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

Кто-нибудь знает о хорошей реализации такой вещи? Есть опыт?

Answer 1

Я думаю, что алгоритм, обсуждаемый в этой теме , вероятно, то, что вы ищете. Если вы хотите получить преимущество, вы можете рассмотреть возможность реализации реализации Boost d_ary_heap_indirect, которая является частью Boost.Graph (в d_ary_heap.hpp). Если вы хорошо поработали с ним, вы можете отправить его в Boost. Это может сделать небольшое дополнение, потому что такая реализация, безусловно, имеет много применений.

Answer 2

Почему бы не использовать std :: vector с функцией функтора / сравнения и std :: sort () в правильном порядке?Код, вероятно, довольно тривиальный