How to tell a std::priority_queue to refresh its ordering?

Question

I have a priority queue of pointers to a struct city. I modify the objects pointed by these pointers outside the priority queue, and want to tell the priority queue to "reorder" itself according to the new values.

What should I do?

Example:

#include <iostream>
#include <queue>

using namespace std;

struct city {
    int data;
    city *previous;
};

struct Compare {
    bool operator() ( city *lhs, city *rhs )
    {
        return ( ( lhs -> data ) >= ( rhs -> data ) );
    }
};

typedef priority_queue< city *, vector< city * >, Compare > pqueue;

int main()
{
    pqueue cities;

    city *city1 = new city;
    city1 -> data = 5;
    city1 -> previous = NULL;
    cities.push( city1 );

    city *city2 = new city;
    city2 -> data = 3;
    city2 -> previous = NULL;
    cities.push( city2 );

    city1 -> data = 2;
    // Now how do I tell my priority_queue to reorder itself so that city1 is at the top now?

    cout << ( cities.top() -> data ) << "\n";
    // 3 is printed :(

    return 0;
}

Solution 1

This is a bit hackish, but nothing illegal about it, and it gets the job done.

std::make_heap(const_cast<city**>(&cities.top()),
               const_cast<city**>(&cities.top()) + cities.size(),
               Compare());

Update:

Do not use this hack if:

• The underlying container is not vector.
• The Compare functor has behavior that would cause your external copy to order differently than the copy of Compare stored inside the priority_queue.
• You don't fully understand what these warnings mean.

You can always write your own container adaptor which wraps the heap algorithms. priority_queue is nothing but a simple wrapper around make/push/pop_heap.

Solution 2

If you need to keep an ordered collection you may consider the following solution: Use std::set and to update values remove the item, update its value and place it back into the set. This will give you O(log n) complexity for updating one item, which is the best you can in a usual heap structure (Assuming you had access to its internals to mass with the sift-up sift-down procedures). The only downside to std::set will be the time for initializing a set with n items. (O(n log n) instead of O(n)).

Solution 3

This is an old question but I wasn't fully satisfied with any of the answers when I wanted to do this myself. There is no need for any hacks. std::priority_queue contains all the machinery to do this legally and idiomatically.

std::priority_queue has two very helpful data members, c (the underlying container) and comp (the comparison predicate).

Equally helpfully, the standard mandates that the Container template type must be a model of SequenceContainer who's iterators are models of RandomAccessIterator.

This is helpful because the Iter argument type of std::make_heap have the same RandomAccessIterator model requirement.

This is a longwinded way of saying that std::priority_queue is a wrapper around a heap and that therefore std::make_heap(std::begin(c), std::end(c), comp) must be a valid expression.

The 'bad' news is that c and comp are protected. This is actually good news for two reasons:

1. You can't destroy the heap accidentally.

2. If you derive from std::priority_queue you can modify the heap intentionally.

So the trick is to derive your priority queue from std::priority_queue, in a member function, mutate the internal heap c any way you like and then call std::make_heap(std::begin(c), std::end(c), comp); to turn it back into a valid heap.

Is it not, generally, a bad idea to inherit from STL containers

Well, yes, but...

There are two reasons that this could be a bad idea for the young and/or unwary. Lack of polymorphic destructors and the risk of slicing.

1. Polymorphic destructors

There is actually no reasonable use case for owning a std container through a pointer to its base class. Containers are lightweight (when there is nothing in them) and cheaply moveable. You may be able to think of use cases, but I can guarantee that whatever you intended to do can be done better by encapsulating the container in another heap-allocated object. In well-designed code, this should never have become a concern. In any case, inheriting privately from the priority_queue template class removes this risk.

2. Slicing

Certainly there is a risk of slicing when we pass inherited objects around. The answer here is to inherit privately from the priority_queue base class, and then use using in the derived class to export only the parts of the base class's interface that we wish to share.

The example below has been updated to show this.

Below is an example from a real project.

Requirements: Keep a queue of topics that a client must be notified changes to. Order the queue by the timestamp of the earliest time that this topic was notified. Do not allow duplicate topic names.

Here is a working demo:

#include <queue>
#include <string>
#include <chrono>
#include <cassert>
#include <iostream>

using topic_type = std::string;
using timestamp_clock = std::chrono::system_clock;
using timestamp_type = timestamp_clock::time_point;

struct notification {
    topic_type topic;
    timestamp_type timestamp;
};

bool topic_equals(const notification& l, const topic_type& r) {
    return l.topic == r;
}
bool topic_equals(const topic_type& l, const notification& r) {
    return l == r.topic;
}

bool age_after(const notification& l , const notification& r) {
    return l.timestamp > r.timestamp;
}

bool age_after(const notification& l , const timestamp_type& r) {
    return l.timestamp > r;
}

bool age_after(const timestamp_type& l , const notification& r) {
    return l > r.timestamp;
}

struct greater_age
{
    template<class T, class U>
    bool operator()(const T& l, const U& r) const {
        return age_after(l, r);
    }
};

template<class T>
struct pending_queue_traits;

template<>
struct pending_queue_traits<notification>
{
    using container_type = std::vector<notification>;
    using predicate_type = greater_age;
    using type = std::priority_queue<notification, container_type, predicate_type>;
};

class pending_notification_queue
: private pending_queue_traits<notification>::type
{
    using traits_type = pending_queue_traits<notification>;
    using base_class = traits_type::type;

public:


    // export the constructor
    using base_class::base_class;

    // and any other members our clients will need
    using base_class::top;
    using base_class::pop;
    using base_class::size;

    bool conditional_add(topic_type topic, timestamp_type timestamp = timestamp_clock::now())
    {
        auto same_topic = [&topic](auto& x) { return topic_equals(topic, x); };
        auto i = std::find_if(std::begin(c), std::end(c), same_topic);
        if (i == std::end(c)) {
            this->push(notification{std::move(topic), std::move(timestamp)});
            return true;
        }
        else {
            if (timestamp < i->timestamp) {
                i->timestamp = std::move(timestamp);
                reorder();
                return true;
            }
        }
        return false;
    }

private:
    void reorder() {
        std::make_heap(std::begin(c), std::end(c), comp);
    }
};

// attempt to steal only the base class...
void try_to_slice(pending_queue_traits<notification>::type naughty_slice)
{
    // danger lurks here
}
int main()
{
    using namespace std::literals;

    auto pn = pending_notification_queue();

    auto now = timestamp_clock::now();
    pn.conditional_add("bar.baz", now);
    pn.conditional_add("foo.bar", now + 5ms);
    pn.conditional_add("foo.bar", now + 10ms);
    pn.conditional_add("foo.bar", now - 10ms);

    // assert that there are only 2 notifications
    assert(pn.size() == 2);
    assert(pn.top().topic == "foo.bar");
    pn.pop();
    assert(pn.top().topic == "bar.baz");
    pn.pop();

    // try to slice the container. these expressions won't compile.
//    try_to_slice(pn);
//    try_to_slice(std::move(pn));

}

Solution 4

The stl's containers don't provide as fast as possible updatable priority queues.

@Richard Hodges: make_heap takes O(n) complexity, and the push_heap function doesn't tell you where the provided element was stored, making a quick update of a single element impossible (you need O(n) to find it).

I have implemented a high-performance updatable priority queue (an update costs O(log n), twice as fast as using an std::set) and made it available on github.

This is how you would typically use it :

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

View more solutions

Comments

[Khushman Patel]

But in a set I can't have two elements with the same data, can I? :(

[Fred Foo]

+1 for this solution, which is much more efficient than Moron's. @Skkard: in an std::multiset, you can.

[Admin]

btw, +1 for this :-) I presume any balanced binary tree would do too (which is what I am guessing std:set is implemented as). Does std::set/multiset guarantee O(log n) insert/delete and access to max/min?

[Admin]

@lars: I deleted my earlier comment as I misread this answer. You are right, this is likely better.

[Fred Foo]

@Moron: std::set and multiset guarantee O(lg n) insert/delete as well as max and min (via begin and rbegin), which makes them pretty good, but not excellent, double-ended priority queues.

[Admin]

@lars: And if getting O(1) max/min is an absolute requirement (like a heap), one can cache it...

[Howard Hinnant]

This solution costs an allocation + deallocation per modification. Without the 2009-09-19 recommendation to LWG 839: open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839 , the cost of this can be too much depending on the application.

[Dennis Zickefoose]

std::priority_queue does not guarantee it's elements are contiguous unless the underlying container provides that guarantee.

[Howard Hinnant]

Agreed. That's part of the "hackishness". The underlying container in this example is vector which guarantees a contiguous buffer. Another part of the "hackishness" is that the comparator should be stateless. And then there's the const_cast which will scare many code reviewers off, but actually do exactly the right thing in this example. This example works. But don't change the container to deque, don't supply a stateful comparator, and don't abuse it by calling make_heap "too often", lest the performance will degrade. Used judiciously, this hack just works.

[Khushman Patel]

This worked in my case, thanks :). For future reference, what do you mean by a stateful comparator? Sorry if the question is stupid.

[Fred Foo]

I'm not sure priority_queue is even guaranteed to interoperate with make_heap and friends. Hacky, indeed.

[Howard Hinnant]

@Skkard: I've updated my answer with warnings about the sharp edges of this hack. I've replaced the words "stateful comparator" with bullet two above, which is hopefully clear.

[Howard Hinnant]

@larsmans: priority_queue is specified to call make/push/pop_heap.

[Khushman Patel]

@Howard Hinnant - Thanks. I got it now. :)

[sjrowlinson]

Is it not, generally, a bad idea to inherit from STL containers (even container adapters as is the case with std::priority_queue) due to issues with destruction? (i.e. STL containers have non-virtual destructors)

[Richard Hodges]

In general, I would agree. People should be wary of inheriting from containers, And relying on their polymorphic destruction is certainly an error. However, those protected members are there in priority_queue specifically for this use case. We could go further actually and argue that there is not a valid use case for allocating a container directly on the heap with new, in which case polymorphic destruction will never be needed.

[Richard Hodges]

@ArchbishopOfBanterbury great comment - I have addressed it in the updated answer. Its interesting to see how often in the c++ community the idea of doing this has some caveats becomes never, ever do this, ever!. Senior developers can sometimes be lazy when explaining things to junior ones :)

[sjrowlinson]

I see, that makes sense, +1

[Mo Aboulmagd]

This is quiet the hack, but please do tell me the runtime is O(log(n))...It seems as though it is linear, as opposed to truly being logarithmic.