Можно ли использовать очередь приоритетов stl c ++ с установленным stl?
Мой вопрос идентичен Существует ли реализация Queue (PriorityQueue), которая также является Set? за исключением того, что это о c ++ и stl.
Можно ли использовать очередь приоритетов stl с установленным stl в качестве класса контейнера? Если нет, есть ли альтернативный класс контейнера, который я могу использовать с очередью приоритетов, чтобы также сделать его набором?
Решение
Спецификация std::priority_queue не допускает «уникальное членство». Если вы хотите уникальное членство в приоритетных очередях, то ты не хочешь std::priority_queue.
Если вы хотите реализовать приоритетную очередь с уникальным членством, то std::set уже делает это, потому что он держит своих членов в отсортированном порядке.
Другие решения
Возможно, это не самая эффективная реализация, но вы можете сделать что-то вроде этого. (Обратите внимание, что я не пытаюсь соответствовать точному интерфейсу std :: priority_queue здесь, не заинтересован в изменении оператора сравнения, или нижележащего контейнера, или распределителя std :: set).
Вместо того, чтобы выдавать, когда дубликат выдвигается, эта реализация только делает вид, что толчок был успешным.
template<class T>
class UniquePriorityQueue
{
public:
typedef typename std::priority_queue<T>::size_type size_type;
void push(const T& v)
{
auto i = membership_.insert(v);
if(i.second)
{
queue_.push(v);
}
}
void pop(void)
{
membership_.erase(queue_.top());
queue_.pop();
}
const T& top() const
{
return queue_.top();
}
bool empty() const
{
return queue_.empty();
}
size_type size() const
{
return queue_.size();
}
private:
std::priority_queue<T> queue_;
std::set<T> membership_;
};
Главная, которая управляет функциями, которые реализованы …
int main()
{
UniquePriorityQueue<int> q;
q.push(1);
q.push(1);
q.push(8);
q.push(4);
q.push(2);
q.push(8);
q.push(5);
q.push(7);
assert(q.size() == 6);
assert(q.top() == 8);
q.pop();
assert(q.top() == 7);
q.pop();
assert(q.top() == 5);
q.pop();
assert(q.top() == 4);
q.pop();
assert(q.top() == 2);
q.pop();
assert(q.top() == 1);
q.pop();
assert(q.empty());
}