如何在优先队列中查找值？

Question

我想在我的优先队列中找到一个节点，但我没有找到解决方案:( 如果你有解决方案，我很感兴趣。

谢谢帮助。

- Marc Lamberti

---

一个priority_queue只有两个操作：按给定优先级插入元素和检索具有最高优先级的元素。如果你需要其他操作，那么priority_queue不是正确的容器选择。 - syam

知道你需要这个的原因会有所帮助 - 通常优先队列的整个目的就是你不需要这个操作。 - Konrad Rudolph

@syam 如果您需要知道特定元素的当前优先级是多少，该怎么办呢？ int priority = pq.find() - pg.begin(); - Captain Obvlious

你能提供更多关于你需求的信息吗？ - konjac

@helock 通常在 SO 上提问时，您会提供一个小的可编译示例，以说明您想要实现的内容。这样我们就知道您已经尝试过什么，建议的解决方案更有可能奏效。 - Captain Obvlious

Answer 1

如果您确实需要有效地搜索 std::priority_queue，并希望做到高效率，您可以派生一个新类并添加一个 find 成员函数。由于您没有添加任何额外的状态，所以不必担心切片或其他问题，因为 std::priority_queue 不是多态的。

#include <queue>
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class MyQueue : public std::priority_queue<T, Container, Compare>
{
public:
    typedef typename
        std::priority_queue<
        T,
        Container,
        Compare>::container_type::const_iterator const_iterator;

    const_iterator find(const T&val) const
    {
        auto first = this->c.cbegin();
        auto last = this->c.cend();
        while (first!=last) {
            if (*first==val) return first;
            ++first;
        }
        return last;
    }
};

- Captain Obvlious

---

只是一个问题，这个->c是什么？ - Marc Lamberti

c 是底层容器。它是作为模板参数传递的类型 Container，并在 C++ 语言标准中指定，因此保证始终存在。 - Captain Obvlious

CCPReference.com 是一个非常好的 C++ 和标准库的参考网站。这里是 std::priority_queue 的文档。 - Captain Obvlious

我立刻看到了，谢谢你。 - Marc Lamberti

Answer 2

如果您不关心性能，可以声明一个iterator来遍历priority_queue的容器。但在C++中，底层容器被声明为protected，不能直接访问。

我得到容器迭代器的一种解决方案是声明一个继承自std::priority_queue的新类。

typedef int Val_TYPE;
typedef vector<Val_TYPE> Container_TYPE;
typedef priority_queue<Val_TYPE, Container_TYPE> pri_queue;

class Queue: public pri_queue{
public:
    Container_TYPE::iterator begin(){
        return pri_queue::c.begin();
    }
    Container_TYPE::iterator end(){
        return pri_queue::c.end();
    }
}Q;

然后您可以获取容器的迭代器。

Q.push(4);
Q.push(3);
Q.push(35);
for(vector<int>::iterator p=Q.begin(); p!=Q.end(); p++)
cout << *p << endl;

---

为了提高效率，例如通过某些关键字查找数据，您可以使用 数据指针。

假设类 Data 持有您的每个数据项。 Data.key 是搜索的关键字，Data.value 是在 priority_queue 中的优先级。

struct Data{
    VALUE_TYPE value;
    KEY_TYPE key;
    ...
    ...
};

将所有数据存储在单独的集合中，例如数组或链表。

Data data[MAX]; 

定义一个新的结构体，该结构体存储某个data[i]的指针。

struct Node{
    Data* data;
    Node(Data* ptr){data=ptr;}
};

使用一个 priority_queue 和另一个支持搜索的数据结构，例如 binary search tree、hash。这里我使用了 multimap。

同时维护一个 Node 的 priority_queue 和一个 multimap。

struct cmp1{
    bool operator(Node a, Node b){ return a.data->value < b.data->value; }
};

struct cmp2{
    bool operator(Node a, Node b){ return a.data->key < b.data->key; }
};

priority_queue<Node, vector<Node>, cmp1> q;

multimap <KEY_TYPE, Node, cmp2> d;

for(int i = 0; i < n; ++i){
    q.push(Node(&a[i]));
    d.insert(a[i].key, Node(&a[i]));
}

你可以使用 multimap d 按键获取数据的 指针。通过使用 priority_queue q，还可以满足对优先级队列的需求。

以上所有内容都是使用指针完成的。

- konjac

---

您不需要包含比较函数。对于map和priority_queue，模板参数默认为std::less。 - Captain Obvlious

@CaptainObvlious 或许你没有理解我的意思。我是指使用 priority_queue 和 multimap 存储数据的 指针。因此，我需要编写自己的比较函数。 - konjac

使用两个容器是不必要的，即使你这样做了，你的比较函数也会导致它们被排序得不同。将比较函数移动到“节点”中，就可以少处理一个显式依赖项。在“数据”中存储键和值都是不必要的，因为它们已经由容器管理了。最好编写自己的容器适配器。 - Captain Obvlious

不需要定义一个新类然后迭代它。可以通过将其传递给一个函数来完成相同的操作，该函数弹出并搜索队列中的元素。 - Manjunath Bhadrannavar