前言

priority_queue 是一个优先级队列，是带权值的。支持插入和删除操作，其只能从尾部插入，头部删除，并且其顺序也并非是根据加入的顺序排列的。priority_queue 因为也是队列的一种体现，所以也就跟队列一样不能直接的遍历数组，也就没有迭代器。priority_queue 本身也不算是一个容器，它是以 vector 为容器以 heap 为数据操作的 container adapter。

priority_queue

由于前置知识点 vector 与 heap 都已经梳理过，priority_queue 只是做了一层封装，比较简单，因此这里直接列出代码。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// 模板类 priority_queue
// 参数一代表数据类型，参数二代表容器类型，缺省使用 mystl::vector 作为底层容器
// 参数三代表比较权值的方式，缺省使用 mystl::less 作为比较方式

template <class T, class Container = tinystl::vector<T>,
          class Compare = tinystl::less<typename Container::value_type>>
class priority_queue {

public:
    typedef Container                           container_type;
    typedef Compare                             value_compare;
    // 使用底层容器的型别
    typedef typename Container::value_type      value_type;
    typedef typename Container::size_type       size_type;
    typedef typename Container::reference       reference;
    typedef typename Container::const_reference const_reference;

    static_assert(std::is_same<T, value_type>::value, "the value_type of Container should be same with T");

private:
    container_type c_;     // 用底层容器来表现 priority_queue
    value_compare  comp_;  // 权值比较的标准

public:  // 构造、复制、移动函数
    priority_queue() = default;
    priority_queue(const Compare& c) : c_(), comp_(c) {}
    explicit priority_queue(size_type n) : c_(n) { tinystl::make_heap(c_.begin(), c_.end(), comp_); }
    priority_queue(size_type n, const value_type& value) : c_(n, value) {
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
    }

    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last) : c_(first, last) {
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
    }

    priority_queue(std::initializer_list<value_type> ilist) : c_(ilist) {
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
    }

    priority_queue(const Container& c) : c_(c) {
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
    }

    priority_queue(Container&& c) : c_(tinystl::move(c)) {
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
    }

    priority_queue(const priority_queue& rhs) : c_(rhs.c_), comp_(rhs.comp_) {
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
    }

    priority_queue(priority_queue&& rhs) : c_(tinystl::move(rhs.c_)), comp_(rhs.comp_) {
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
    }

    priority_queue& operator=(const priority_queue& rhs) {
        c_ = rhs.c_;
        comp_ = rhs.comp_;
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
        return *this;
    }

    priority_queue& operator=(priority_queue&& rhs) {
        c_ = tinystl::move(rhs.c_);
        comp_ = rhs.comp_;
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
        return *this;
    }

    priority_queue& operator=(std::initializer_list<value_type> ilist) {
        c_ = ilist;
        tinystl::make_heap(c_.begin(), c_.end(), comp_);
        return *this;
    }

    ~priority_queue() = default;

public:  // 元素相关操作
    const_reference top()   const { return c_.front(); }
    bool            empty() const { return c_.empty(); }
    size_type       size()  const { return c_.size(); }

    template <class... Args>
    void emplace(Args&&... args) {
        c_.emplace_back(tinystl::forward<Args>(args)...);
        tinystl::push_heap(c_.begin(), c_.end(), comp_);
    }

    void push(const value_type& value) {
        c_.push_back(value);
        tinystl::push_heap(c_.begin(), c_.end(), comp_);
    }

    void push(value_type&& value) {
        c_.push_back(tinystl::move(value));
        tinystl::push_heap(c_.begin(), c_.end(), comp_);
    }

    void pop() {
        tinystl::pop_heap(c_.begin(), c_.end(), comp_);
        c_.pop_back();
    }

    void clear() {
        while (!empty()) {
            pop();
        }
    }

    void swap(priority_queue& rhs) noexcept(noexcept(tinystl::swap(c_, rhs.c_)) &&
                                            noexcept(tinystl::swap(comp_, rhs.comp_))) {
        tinystl::swap(c_, rhs.c_);
        tinystl::swap(comp_, rhs.comp_);
    }

public:
    friend bool operator==(const priority_queue& lhs, const priority_queue& rhs) {
        return lhs.c_ == rhs.c_;
    }

    friend bool operator!=(const priority_queue& lhs, const priority_queue& rhs) {
        return !(lhs == rhs);
    }
};


// ============================= 重载比较操作符 ============================= //

template <class T, class Container, class Compare>
bool operator==(const priority_queue<T, Container, Compare>& lhs,
                const priority_queue<T, Container, Compare>& rhs) {
    return lhs == rhs;
}

template <class T, class Container, class Compare>
bool operator!=(const priority_queue<T, Container, Compare>& lhs,
                const priority_queue<T, Container, Compare>& rhs) {
    return !(lhs == rhs);
}

template <class T, class Container, class Compare>
void swap(priority_queue<T, Container, Compare>& lhs,
          priority_queue<T, Container, Compare>& rhs) noexcept(noexcept(lhs.swap(rhs))) {
    lhs.swap(rhs);
}

总结

实际上优先队列本身没有什么好总结的，但考虑到这是序列是容器的最后一部分内容了（SGI-STL 还有一个 slist，但与 list 较为相似，这里不再分析），稍微总结一下序列式容器。

所谓序列式容器，其中的元素都可序 (ordered)，但未必有序( sorted )。序列式用于存储一系列元素，并按照它们被添加的顺序来组织这些元素。这些容器允许元素按照线性顺序访问，通常支持在容器的前端和后端进行元素的插入和删除操作。

C++ 语言本身提供了一个序列式容器 array，STL 另外再提供 vector，list，deque，stack，queue，priority-queue 等等序列式容器。其中 stack 和 queue 只是将 deque 改头换面而成，priority-queue 也只是使用了 heap 算法的 vector 而已，技术上被归类为一种配接器 ( adapter )。

因此序列式容器这部分，重要的就只有 vector、list 与 deque 三部分内容。

  • vector 是 STL 中的一种结构较为简单的容器，vector 内部维护的是一个连续的线性空间，其迭代器为普通指针类型。vector 的特点在于其是动态空间，随着元素的加人，它的内部机制会自行扩充空间以容纳新元素。为了实现这一点，vector 以 begin_、end_、cap_ 三个迭代器分别代表 vector 目前数据的头部、尾部以及可使用空间的尾部。利用这三个迭代器可以很方便地判断当前的数据个数是否超出容量以重新分配更大的空间；

值得注意的是，vector 的重新分配空间并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍（或 1.5 倍）另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。

  • SGI-STL 中的 list 为双向环状链表，只需一个节点便可以遍历整个链表，并且可以轻松维护各种信息（如 begin(), end(), empty() 等）。

相较于 vector，list 的好处是对于任意位置的元素插入与删除，均是常数时间复杂度，且对于空间的使用非常精准，不用像 vector 一样提前分配多余的空间；同时，list 的迭代器也始终有效，不会出现 vector 中的失效情况。但常数时间插入删除元素的代价就是对于任意元素的访问是 O(n) 复杂度。

list 的迭代器为双向迭代器，不支持随机访问，因此也不能使用 STL 中的排序算法对 list 进行排序。为此，list 内部实现了一种十分巧妙的归并排序方法，使用 merge 与 swap 等内部的函数，同时利用了缓存表，实现了时间复杂度 O(nlogn)，空间复杂度 O(n) 的归并排序。