priority_queue

前言

之前分析的 heap 是为了分析 priority_queue 做准备, priority_queue 是一个堆优先队列, 支持插入和删除元素, 但是对于插入和删除进行了限制, 对于插入只能在堆的最后进行插入, 只能获取和删除堆顶元素, 由于priority_queue 也是队列的一种体现, 所以为了维护队列的特性, 不提供迭代器以进行遍历操作. 同时它也不能被严格称作容器, 它是以支持RandomAccessIterator 类型迭代器容器和 heap 支持对容器数据进行堆操作的一个配置器

源码分析

类型定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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:
	// 符合traits编程规范
  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;	// 定义vector容器的对象
  Compare comp;	// 定义比较函数(伪函数)
  ...
};

对于 Sequence 也可以是 deque 因为 deque 也支持 RandomAccessIterator 类型迭代器

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class  priority_queue {
	...
public:
  priority_queue() : c() {}	// 默认构造函数
  explicit priority_queue(const Compare& x) :  c(), comp(x) {}	// 设置伪函数

#ifdef __STL_MEMBER_TEMPLATES
    // 接受以迭代器类型的参数
    // 接受两个迭代器以及函数. 传入的迭代器范围内表示的元素以comp定义的方式进行调整
  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 */
     // 接受两个迭代器以及函数. 传入的迭代器范围内表示的元素以comp定义的方式进行调整
  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 */
	...
};

属性获取

priority_queue 有三种获取其内部值的方法, 都是封装了 Sequence 的方法和 heap 中的函数

1
2
3
4
5
6
7
8
9
class  priority_queue {
	...
public:
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  const_reference top() const { return c.front(); }
    ...
};

push和pop实现

push 和 pop 具体都是采用的heap算法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class  priority_queue {
	...
public:
  void push(const value_type& x) {
    __STL_TRY {
      c.push_back(x); 
        // 间接使用heap算法
      push_heap(c.begin(), c.end(), comp);
    }
    __STL_UNWIND(c.clear());
  }
  void pop() {
    __STL_TRY {
     	// 间接使用heap算法
      pop_heap(c.begin(), c.end(), comp);
      c.pop_back();
    }
    __STL_UNWIND(c.clear());
  }
};

总结

priority_queue 本身实现是很复杂的, 但是其内部都是封装了 Sequence, heap , 就比较简单明了, 就是将 Sequence 作为容器, heap 作为算法来操作的配置器, 这也体现了STL的灵活性是很高的, 通过各个容器与算法的结合就能做出另一种功能的结构.