Очередь с расширенным приоритетом

Я ищу реализацию очереди приоритетов в C ++.
Помимо основной функциональности в STL приоритетная очередь, это требует следующих методов:

  1. Он может удалить все те же элементы (определяется функцией) при нажатии (аналогично набору)
  2. Он может отфильтровать некоторые элементы (определяемые другой функцией).

Есть ли у вас предложения о том, как это реализовать?

4

Решение

Ты можешь использовать std::set в качестве приоритетной очереди без дубликатов. top элемент может быть найден через rbegin(), Асимптотическая сложность такая же, как и для двоичной кучи: O (1) top согласно стандартным требованиям для rbegin, O (LG N) push и O (LG N) pop, Константы будут выше, хотя.

Что касается фильтра, я предлагаю вам обернуть std::set в классе с обычаем push метод (который в любом случае является хорошей идеей), который запускает предикат фильтрации для вас.

4

Другие решения

Просто заверните priority_queue:

#include <set>
#include <queue>

// Default predicate allows all objects through
template <typename T>
struct allow_any {
bool operator()(T const&) const {
return true;
}
};

// F is a callable type for the filtering predicate -- either a
// function pointer, or a class having an operator()(T const&).
template <typename T, typename F = allow_any<T> >
class filtering_priority_queue {
public:
explicit filtering_priority_queue(F f) : allow(f) {}

void push(T x) {
if (allow(x) && s.find(x) == s.end()) {
q.push(x);
s.insert(x);
}
}

T const& top() const {
return q.top();
}

void pop() {
s.erase(top());
q.pop();
}

private:
std::set<T> s;
std::priority_queue<T> q;
F allow;
};
3

По вопросам рекламы [email protected]