C++映射的优先队列及示例

优先队列（priority queue）是一种按照优先级（权值）处理数据的数据结构，它类似于一个队列，但是每个元素都有一个优先级与之相关联，一般使用堆来实现。

在C++中，优先队列可以通过STL库中的priority_queue类来实现。但是，这个类只能对元素进行排序，不能按照自定义的键（key）来排序。因此，为了解决这个问题，我们可以使用映射（map）来实现带有自定义键的优先队列。

映射的概念

映射（map）是一种关联式容器，它将键（key）和值（value）配对，类似于字典。在C++中，映射可以通过STL库中的map类来实现。

以下是一个简单的例子，展示了如何使用映射：

#include <iostream>
#include <map>
using namespace std;

int main()
{
    //定义一个映射
    map<string, int> m;

    //插入元素
    m["apple"] = 10;
    m["orange"] = 20;

    //查找元素
    cout << m["apple"] << endl;  //输出10
    cout << m["banana"] << endl; //输出0

    //遍历映射
    for (auto it = m.begin(); it != m.end(); it++)
    {
        cout << it->first << " : " << it->second << endl;
    }

    return 0;
}

上面的代码定义了一个string到int的映射，并插入了两个元素。在查找元素时，如果键不存在，会返回默认值0。此外，该代码使用了自动迭代器（auto）对映射进行了遍历。

带映射的优先队列实现

现在，我们来看一下如何利用映射实现带有自定义键的优先队列。

首先，我们需要为映射定义一个自定义比较器。这个比较器需要重载小于运算符（operator<），它将决定队列中元素的优先级。假设我们要定义的优先队列元素类型为Pair，其中first是字符串类型的键，second是数字类型的权值，以下是一个例子：

struct Pair
{
    string first;
    int second;
};

struct cmp
{
    bool operator()(const Pair& x, const Pair& y)
    {
        return x.second < y.second; //按权值排序
    }
};

在这个例子中，我们定义了一个结构体Pair，包含了一个string类型的键first和一个int类型的权值second。接下来，我们定义了一个比较器cmp，它重载了小于运算符，按照元素的权值进行排序。

接着，我们可以使用优先队列（priority_queue）和映射（map）来实现自定义键的优先队列：

#include <iostream>
#include <queue>
#include <map>
using namespace std;

struct Pair
{
    string first;
    int second;
};

struct cmp
{
    bool operator()(const Pair& x, const Pair& y)
    {
        return x.second < y.second; //按权值排序
    }
};

int main()
{
    //定义一个带映射的优先队列
    priority_queue<Pair, vector<Pair>, cmp> pq;
    map<string, int> m;

    //插入元素
    pq.push({"apple", 10});
    m["apple"] = 10;

    pq.push({"orange", 20});
    m["orange"] = 20;

    //按键查找元素
    cout << m["apple"] << endl;  //输出10
    cout << m["banana"] << endl; //输出0

    //遍历映射
    for (auto it = m.begin(); it != m.end(); it{
        cout << it->first << " : " << it->second << endl;
    }

    //遍历优先队列
    while (!pq.empty())
    {
        cout << pq.top().first << " : " << pq.top().second << endl;
        pq.pop();
    }

    return 0;
}

上面的代码定义了一个带映射的优先队列（priority_queue<Pair, vector, cmp>），其中Pair是优先队列的元素类型，vector是底层容器类型，cmp是自定义比较器类型。

在插入元素时，我们既向优先队列中插入了Pair元素，又向映射中插入了键值对。在查找元素时，我们通过键来查找对应的权值。

在最后的遍历中，我们先遍历了映射，然后利用优先队列的top()函数获取队列顶部的元素，输出键和权值后，再将其弹出队列。这里的输出顺序与插入顺序不同，是由比较器的排序决定的。

结论

通过上面的例子，我们学习了带示例的C++映射的优先队列。映射是一种关联式容器，能够将键和值配对，类似于字典。利用映射，我们可以自定义键并方便地实现带有自定义键的优先队列。在使用映射的同时，我们需要定义一个自定义比较器，它将根据元素的键或权值来确定优先级。这里我们以权值为例。最后，我们演示了如何插入元素、查找元素，以及遍历映射和优先队列。