c++ - 如何在优先队列中找到价值？

Question

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

谢谢帮助。

Answer 1

如果您确实需要搜索 astd::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;
    }
};

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;

---

为了更高效，例如通过某些键查找数据，您可以使用pointers to data.

假设该类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;}
};

使用 apriority_queue和另一个数据结构支持搜索binary search tree，即hash. 我在这里使用multimap.

同时保持a priority_queueofNode和a multimapof Node。

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]));
}

然后您可以pointer使用 multimap 按键获取数据d。使用 priority_queue 也满足了对 priority_queue 的需求q。

以上所有只是使用指针。