Приоритетные очереди. Строение класса priority_queue

   
На этом шаге мы приведем строение класса 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.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий