我怎样才能在优先队列中找到价值？

Question

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

谢谢你的帮助.

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

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

使用一个priority_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。

以上所有内容都只是使用指针。