C++ 容器适配器priority_queue的使用及实现代码

下面我将详细讲解“C++ 容器适配器priority_queue的使用及实现代码”的完整攻略，包括定义与使用、成员函数及示例说明。

定义与使用

priority_queue 是一个容器适配器，它提供了队列的功能，但是元素被自动排序（默认为按元素值从大到小）。

在使用 priority_queue 之前，需要引用头文件 <queue> ，并使用命名空间 std。

定义 priority_queue 的语法如下：

priority_queue <type, container, functional>

其中，type 为存储在队列中的元素类型；container 为存储元素的底层容器，默认为 vector<type>；functional 为比较元素的方法，默认为 less<type>，即按元素值从大到小排序。如果要按元素值从小到大排序，可以使用 greater<type>。

priority_queue 支持以下成员函数：

• push()：在队尾插入一个元素；
• pop()：移除队首元素；
• top()：返回队首元素；
• empty()：判断队列是否为空；
• size()：返回队列中元素的个数。

下面是一个简单的示例：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

示例输出：

3 2 1

成员函数说明

push()

void push(const value_type& val)

在队尾插入一个元素，插入完成后将自动排序。

示例代码：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

示例输出：

3 2 1

pop()

void pop()

移除队首元素。

示例代码：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    pq.pop();
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

示例输出：

2 1

top()

const_reference top() const

返回队首元素。

示例代码：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    cout << pq.top() << endl;
    return 0;
}

示例输出：

3

empty()

bool empty() const

判断队列是否为空。

示例代码：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    cout << pq.empty() << endl;
    pq.pop();
    cout << pq.empty() << endl;
    return 0;
}

示例输出：

0
1

size()

size_type size() const

返回队列中元素的个数。

示例代码：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(3);
    pq.push(2);
    cout << pq.size() << endl;
    return 0;
}

示例输出：

3

示例说明

下面是另一个示例，演示如何将 priority_queue 的排序规则改为按照长度从小到大排序。

#include <iostream>
#include <queue>
#include <string>

using namespace std;

struct cmp {
    bool operator()(const string& a, const string& b) {
        return a.length() > b.length();
    }
};

int main() {
    priority_queue<string, vector<string>, cmp> pq;
    pq.push("hello");
    pq.push("world");
    pq.push("C++");
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

示例输出：

C++ hello world

在这个示例中，我们在定义 priority_queue 时使用了自定义比较方法 cmp，cmp 重载了 () 操作符，使得排序规则变为按照元素长度从小到大排序。