slow_hare's blog

Can we change the comparator of set, priority_queue at run time in c++?
By slow_hare, history, 3 years ago, In English

I had a solution to a problem which included priority queue.

I wish to know if we can change the comparator of priority queue at run time like if we initially had the declaration as priority_queue<int> pq which will store no.s in non-increasing order, can I use the same priority queue to store no.s in increasing order after pq.clear()

Thanks

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

AFAIK there is no clear method for priority_queue in C++. What you can do is naively pop elements out or create a new priority_queue:

pq = priority_queue<int>();

Now comeback to your question, I haven't seen anyway to change the comparator. However there is a simple workaround using custom comparator.

int sign = -1;
bool cmp(const int &a, const int &b){
    return a * sign < b * sign;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    priority_queue<int, vector<int>, decltype(&cmp)> q(cmp);
    q.push(1); q.push(2); q.push(3);
    cout << q.top() << '\n';

    sign *= -1;
    q = priority_queue<int, vector<int>, decltype(&cmp)>(cmp);
    q.push(1); q.push(2); q.push(3);
    cout << q.top();
}

Output:

1
3

With sign equal to -1, small numbers will be prioritized and similar for sign equal to 1

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    does the comparator swaps element on the condition being true here?

    as with normal comparators with a = 1 and b = 2 and sign = -1, a*sign < b*sign returns false and swaps them..

    is the thing opposite here? as it seems that the order of the two elements being compared remains same when the condition is false.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Order of elements in a priority_queue is reversed.

      For example

      priority_queue<int, vector<int>, greater<int>>();

      is actually a minheap.

      For the case $$$a = 1$$$, $$$b = 2$$$ and $$$sign = -1$$$, the comparator return false, but it should be reversed so the order remain the same.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is possible but you will have to maintain the priority_queue manually using make_heap, push_heap, and pop_heap.

https://ideone.com/jBJc9w

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To change the comparator of the std::proiority_queue, you may use a type of struct/class called functor. It is a struct/class which has a function operator().

For example, to use a heap that its top element is the smallest one. You can write as follows.

Example

There is already functors in STL called greater<T> and less<T>. Code above can also write as follows:

...
priority_queue<int,vector<int>,greater<int> >q;
...

If you found mistakes in my code, please comment me.

And forgive me for my poor English.

→ Reply