How I can find value in priority queue?

Question

I would like to find a node in my priority queue but I did not find a solution :( If you have a solution, I'm interested.

Thx for help.

Answer 1

If you really need to search through a std::priority_queue and want to do it efficiently you can derive a new class and add a find member function. Since you are not adding any additional state you do not have to worry about slicing or other issues since std::priority_queue is not polymorphic.

#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

If you do not care about the performance, you can declare an iterator to traverse the priority_queue's container. But in C++, the underlying container is been declared as protected, and can not be accessed directly.

One of my solution to get the iterator of the container is declaring a new class inheriting from 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;

Then you can get the iterator of the container.

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

---

In order to be more efficient, for example looking for data by certain keys, you can use pointers to data.

Suppose the class Data holds each item of your data. Data.key is the key for search and Data.value is the priority in priority_queue.

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

Store all your data in a separate collection, for example an array or an link list.

Data data[MAX]; 

Define a new struct which stores the pointer for certain one data[i]

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

Use a priority_queue and another data structure support search i.e. binary search tree, hash. Here I use multimap.

Maintain a priority_queue of Node and a multimap of Node at the same time.

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

Then you can get data's pointer by key using multimap d. The need for priority_queue is also satisfied by using priority_queue q.

All of the above is just using pointers.