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.

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

Solution 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.

Comments

[Captain Obvlious]

You don't need to include comparison functions. The template parameter defaults to std::less for both map and priority_queue

[konjac]

@CaptainObvlious Maybe you didn't understand me. I mean to use a priority_queue and multimap to store the pointer of data. So I need to write my own comparison functions.

[Marc Lamberti]

Just a question, what is this->c ?

[Captain Obvlious]

Using two containers is unnecessary and even if you do your comparison functions will cause them to be ordered differently. Move the comparison function into Node and you have one less explicit dependency to deal with. Storing both the key and the value in Data is unnecessary, it's already managed by the containers. You would be better off writing your own container adapter.

[Captain Obvlious]

c is the underlying container. It's of type Container passed as a template parameter and is specified in the C++ language standard so it'a guaranteed to always be there.

[Captain Obvlious]

CCPReference.com is a wonderful for C++ and the Standard Library. Here is the documentation for std::priority_queue.

[Marc Lamberti]

Yeah I saw at once, thx you

[Manjunath Bhadrannavar]

there is no need to define a new class and then iterate through it. The same can be done passing it to a function which pops and searches for elements in the queue.