How to Use the Priority Queue Stl for Objects

How to use the priority queue STL for objects?

You need to provide a valid strict weak ordering comparison for the type stored in the queue, Person in this case. The default is to use std::less<T>, which resolves to something equivalent to operator<. This relies on it's own stored type having one. So if you were to implement

bool operator<(const Person& lhs, const Person& rhs); 

it should work without any further changes. The implementation could be

bool operator<(const Person& lhs, const Person& rhs)
{
  return lhs.age < rhs.age;
}

If the the type does not have a natural "less than" comparison, it would make more sense to provide your own predicate, instead of the default std::less<Person>. For example,

struct LessThanByAge
{
  bool operator()(const Person& lhs, const Person& rhs) const
  {
    return lhs.age < rhs.age;
  }
};

then instantiate the queue like this:

std::priority_queue<Person, std::vector<Person>, LessThanByAge> pq;

Concerning the use of std::greater<Person> as comparator, this would use the equivalent of operator> and have the effect of creating a queue with the priority inverted WRT the default case. It would require the presence of an operator> that can operate on two Person instances.

printing a priority queue of objects in c++

std::priority_queue::top() returns a const &, which means you can only call const functions on this reference. Since print does not change the state of the object you should make it const:

//           VVVVV
void print() const {
    std::cout << "name: " << horseName << std::endl;
}

---

Some unrelated hints:

• Code like if(someCondition) return true; else return false; can be simplified to return someCondition;
• operator < should take it's parameter by const & to avoid copying.
• Check for typos Horse/horse

C++ Priority queue to find and modify objects

"but the the stl::priority_queue doesn't work for me because I need to find whether an element(a Node object) is in the priority_queue or not, to access its data and to modify it if necessary."

You can well do this for any kind of class providing an appropriate Compare class parameter.

std::priority_queue<T> requires the underlying Container to comply with the concept of a SequenceContainer.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

you can take the address of the std::priority_queue<T>::front() reference, and iterate through the queue, to find certain instances.

---

If you really need to have uniquely existent instances of objects, that should be managed additionally by some priority algorithm, it could be a good idea to store smart pointers (e.g. std::shared_ptr<T>), rather than values or raw pointers. The Compare class needs to be adapted appropriately of course.

---

struct CompareNodes {
    bool operator
        ( const std::shared_ptr<Node>& lhs
        , const std::shared_ptr<Node>& rhs
        ) {
        // Provide some operation to compare lhs < rhs (less) results in true
        // This function is meant to determine the actual priority of your Node
        // instances, when referenced in the priority_queue<> in question.
    }
};

std::priority_queue
    < std::shared_ptr<Node>
    , std::vector<std::shared_ptr<Node>>
    , CompareNodes
    > myQueue;

---

"to access its data and to modify it if necessary."

Using the priority queue with std::shared_ptr as shown in the above sample, may also release you from even need to find instances in the queue, and synchronize data modifications from the original instance.

STL Priority Queue on custom class

less<vector<Node*>::value_type> Means that your comparator compares the pointers to each other, meaning your vector will be sorted by the layout in memory of the nodes.

You want to do something like this:

#include <functional>
struct DereferenceCompareNode : public std::binary_function<Node*, Node*, bool>
{
    bool operator()(const Node* lhs, const Node* rhs) const
    {
        return lhs->getTotalCost() < rhs->getTotalCost();
    }
};

// later...
priority_queue<Node*, vector<Node*>, DereferenceCompareNode> nodesToCheck;

Note that you need to be const-correct in your definition of totalCost.

EDIT: Now that C++11 is here, you don't need to inherit from std::binary_function anymore (which means you don't need to #include functional)

How to move elements out of STL priority queue

std::priority_queue is basically a thin layer on top of the heap algorithms. You can easily create your own priority queue with:

• std::vector
• std::push_heap
• std::pop_heap

Using these building blocks, the implementation is trivial, and you can easily implement a moving pop operation. The following listing contains a minimal, working implementation:

template <typename Type, typename Compare = std::less<Type>>
class queue
{
private:
    std::vector<Type> _elements;
    Compare _compare;
public:
    explicit queue(const Compare& compare = Compare())
        : _compare{compare}
    { }
    void push(Type element)
    {
        _elements.push_back(std::move(element));
        std::push_heap(_elements.begin(), _elements.end(), _compare);
    }
    Type pop()
    {
        std::pop_heap(_elements.begin(), _elements.end(), _compare);
        Type result = std::move(_elements.back());
        _elements.pop_back();
        return std::move(result);
    }
};

Why is STL priority queue incorrectly sorrting my class objects

priority_queue<Node*> my_q; will compare elements of type Node* to sort, it will not dereference those pointers for you and call your overloaded operator. And comparison of unrelated pointers has undefined behaviour, but will yield no useful result in your case.

When you fixed this one, there will be another bug: You never initialize decimal_value, so it's value is undefined/random.

One solution would be to explicitly specify an comparator:

struct MyComparator {
    bool operator()(const Node*l, const Node*r) const {
        return l->decimal_value < r->decimal_value;
    }
};

std::priority_queue<Node*, std::vector<Node*>, MyComparator> q;

STL Priority queue with custom comparator not working as expected

You are modifying the item after it was put into the queue and still is part of that queue. This is not supported by the priority queue and yields unspecified results. C++ STL does not offer updatable priority queue.

But, seeing your use case I suspect this is competitive algorithmic programming. There are decent alternetives for this use case. I wouldn't recommend them for production code (at least not without proper abstractions.

The first, "proper" alternative is to use std::set<std::pair<...>> instead. Your code will stay very similar, but there are some important differences:

• You won't need custom comparator, instead relying on pair comparison (you will need to use std::greater as comparator to have largest items "on top",
• You will put {a[index], index} as elements of this set,
• You will use .begin() instead of .top(),
• You will need to .erase() items before updating their values, and insert them again with new values.

I believe above has same complexities as the standard implementation of priority queue. Even though updates seem slow, we are doing just two O(log n) operations - which is same complexity as an actual update in a heap structure.

You could implement it with an indirect comparator as in your example. In general it would work, but you still need the erase and insert flow around update. Additionally you would need to compare indices in your comparator as well, in order to make items with same priority different, so that the correct item is removed.

Moreover, there is another trick we can do in many common cases, like Dijkstra or Prim's algorithms. In these cases we only update priority to higher (lower values). In such case we can ignore erasing items, and instead just add duplicates. This works because time complexity of a single query/update becomes O(log n^2) = O(2 log n) = O(log n). Memory complexity increases, but this often is not a problem.

In this last case you can use other containers to fit your preferences, both std::priority_queue<std::pair<...>> or std::multimap<...> will work nicely. But in all of them you need to keep priority as part of item you insert, and not use it via indirect comparator.

As an appendix, this is your code with changes to work as intended:

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int arr[100], visited[100];
int sizeOfArray;

int main(){
    cin>>sizeOfArray;
    priority_queue<std::pair<int, int>> priorityQue;
    for(int i = 0; i < sizeOfArray; i++) {
        cin>>arr[i];
        priorityQue.push({arr[i], i});
        visited[i]=0;
    }
    while(!priorityQue.empty()) {
        int index = priorityQue.top().second;
        priorityQue.pop();
        if(visited[index])   
            continue;
        visited[index]=1;

        cout<<"Currently at index: "<<index<<endl;

        int currentElement = arr[index];
        int dx[] = {-1, 1};    // left and right neighbours
        for(int k = 0; k < 2; k++) {
            int nextIndex = index + dx[k];
            if( nextIndex >= 0 && nextIndex < sizeOfArray && 
                (currentElement - arr[nextIndex]) > 1 ) 
            {
                arr[nextIndex] = currentElement - 1;
                cout<<"Modifying index :"<<nextIndex<<endl;
                cout<<"New Array is: ";
                // print array 
                for(int z=0;z<sizeOfArray;z++)
                    cout<<arr[z]<<" ";
                cout<<endl;
                
                priorityQue.push({arr[nextIndex], nextIndex});
                cout<<"Pushing index "<<nextIndex<<" to queue"<<endl;
            }
        }
    }
    return 0;
}

---

Related Topics