15

How can I configure std::priority_queue to ignore duplicates?

When I add a key that is already contained then this new one should be ignored. (In my case, the priority for the old and the new one will always be exactly the same.)

Complexity-wise it should not make a difference: It will try to insert at the appropriate location, find the existing one there and do nothing. The question is just if std::priority_queue is configurable in that way.

4
  • 2
    I don't think a heap supports "find an existing one" in O(log N).
    – kennytm
    May 10, 2011 at 18:10
  • @KennyTM, luckily, the pqueue doesn't have to be a heap ;-)
    – ltjax
    May 10, 2011 at 18:18
  • @KennyTM: To find the existing one (note: same priority as new one) we first find the insert location in O(log N) time, then identify the existing key at that location (binary search in O(log N)). Or what am I missing?
    – Frank
    May 10, 2011 at 19:56
  • 3
    You are missing the fact that std::priority_queue is likely implemented as a max-heap binary tree, which doesn't have a fixed "appropriate insert location" for any value. New values are inserted at the end, then percolated up to the first place where all its children have lower values. Multiple insertions of keys with the same priority might end up in completely different branches of the tree.
    – AShelly
    May 13, 2011 at 3:48

2 Answers 2

10

You can implement a priority_queue out of an STL set.

Implementing a priority queue that can be iterated over in C++

0

As Aater mentioned you could use an stl set as a priority queue.

Another option is to add duplicates to the priority queue, but when popping items off the queue, keep track of the previous value and ignore repeated values. For example, here's processing all values on a priority queue while ignoring duplicates

    priority_queue<int> pq = /* values */;
    
    int curr = 0;
    int prev = 0;
    bool first = true;
    while(isplit < target) {
        prev = curr;
        curr = pq.top();
        pq.pop();
        if (!first && prev == curr) {
            continue;
        }
        first = false;
        // do something with curr
    }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.