STL之priority_queue实现详解

分手后的思念是犯贱 2022-05-29 05:21 163阅读 0赞

# 优先队列 #

优先队列可以从尾部插入元素，然后从头部取出优先级（通过一个数值表示）最高的对象。这种支持插入，然后每次仅仅取出一个对象数据结构，完全天然和堆一一对应，所以通过堆实现优先队列适配器是天然的选择。也就是说最大堆其实就是优先队列。优先队列没有迭代器，进出都有一定的规则，只有queue顶端的元素（权重最高者），才有机会被外界取用。

# STL源码 #

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
    template <class T, class Sequence = vector<T>, 
              class Compare = less<typename Sequence::value_type> >
    #else
    template <class T, class Sequence, class Compare>
    #endif
    class  priority_queue {
    public:
      typedef typename Sequence::value_type value_type;
      typedef typename Sequence::size_type size_type;
      typedef typename Sequence::reference reference;
      typedef typename Sequence::const_reference const_reference;
    protected:
      Sequence c;
      Compare comp;
    public:
      priority_queue() : c() {}
      explicit priority_queue(const Compare& x) :  c(), comp(x) {}
    
    #ifdef __STL_MEMBER_TEMPLATES
      template <class InputIterator>
      priority_queue(InputIterator first, InputIterator last, const Compare& x)
        : c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); }
      template <class InputIterator>
      priority_queue(InputIterator first, InputIterator last) 
        : c(first, last) { make_heap(c.begin(), c.end(), comp); }
    #else /* __STL_MEMBER_TEMPLATES */
      priority_queue(const value_type* first, const value_type* last, 
                     const Compare& x) : c(first, last), comp(x) {
        make_heap(c.begin(), c.end(), comp);
      }
      priority_queue(const value_type* first, const value_type* last) 
        : c(first, last) { make_heap(c.begin(), c.end(), comp); }//将元素优先级比较
    #endif /* __STL_MEMBER_TEMPLATES */
    
      bool empty() const { return c.empty(); }
      size_type size() const { return c.size(); }
      const_reference top() const { return c.front(); }
      void push(const value_type& x) {
       //实际就是插入，然后push_heap
        __STL_TRY {
          c.push_back(x); 
          push_heap(c.begin(), c.end(), comp);
        }
        __STL_UNWIND(c.clear());
      }
      void pop() {
       //实际就是pop_heap，然后弹出外部元素
        __STL_TRY {
          pop_heap(c.begin(), c.end(), comp);
          c.pop_back();
        }
        __STL_UNWIND(c.clear());
      }
    };

# 使用例子 #

#include <iostream>
    #include <list>
    #include <algorithm>
    #include <iterator>
    #include <deque>
    #include <queue>
    #include <algorithm>
    #include <stdio.h>
    #include <string>
    using namespace std;
    class Course{
    public:
        Course(){}
        Course(const string &n , const int &pri):name(n) , priority(pri){}
        bool operator<(const Course& x) const{
            return priority < x.priority;
        }
        string name;
        int priority;
    };
    
    int main()
    {
        Course Course1("math" , 5);
        Course Course2("english" ,   4);
        Course Course3("chinese" ,   3 );
        Course Course4("history" ,   2);
        Course Course5("chemistry" , 1);
        priority_queue<Course> pri_que;
        pri_que.push(Course5);
        pri_que.push(Course4);
        pri_que.push(Course3);
        pri_que.push(Course2);
        pri_que.push(Course1);
        while(!pri_que.empty()){
            std::cout << pri_que.top().name << endl;//取出优先级最高
            pri_que.pop();//然后谈出元素
        }

![这里写图片描述][Image 1]  
注意：先top读取，然后pop删除优先队列顶的元素。实际上是通过堆操作的，上述重要的就是重载<运算符，使得两个科目对象可以比较。

[Image 1]: