На этом шаге мы приведем строение класса priority_queue.
Типичная реализация класса priority_queue<>, как и реализации классов stack<> и queue<>, понятна без комментариев:
namespace std {
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> >
class priority_queue {
public:
typedef typename Container::value_type value_type;
typedef typename Container::size_type size_type;
typedef Container container_type;
protected:
Compare comp; // Критерий сортировки
Container c; // Контейнер
public:
// Конструкторы
explicit priority_queue(const Compare& cmp = Compare(),
const Container& = Container())
: comp(cmp), c(cont) {
make_heap(c.begin(),c.end(),comp);
}
void push(const value_type& x) {
c.push_back(x);
push_heap(c.begin(),c.end(),comp);
}
void pop() {
pop_heap(c.begin(),c.end(),comp);
c.pop_back();
}
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const value_type& top() const { return c.front(); }
};
}
Как видно из приведенного листинга, приоритетная очередь использует алгоритмы STL для работы с кучей, описанные в 307 шаге. В отличие от других контейнерных адаптеров для приоритетной очереди не определены операторы сравнения.
В следующих шагах приводятся более подробные описания членов класса priority_queue<>.
На следующем шаге мы рассмотрим определения типов, используемые в классе priority_queue.
