CODEWITHSUNDEEP
c++vectorqueuecontainers
Tyson
Tyson

Reputation: 1238

How to maintain a reference to a std::priority_queue's container?

I'm creating a std::priority_queue using std::vector as container.

It seems like the priority queue creates a copy of the container passed to it in its constructor, since changes made to the container after constructing the queue aren't reflected in the queue's container.

For example, if I call clear() on my container, the priority queue remains full.

Is there a way to maintain a reference to the priority queue's internal container after construction?

Upvotes: 1

Views: 362

Answers (2)

Richard Hodges
Richard Hodges

Reputation: 69892

std::priority_queue is one of the few standard containers designed to be derived from.

It has a protected member c which is the container.

You can derived from the queue and use c in your derived class.

If you mutate the container, remember that it's actually a heap and needs to have the appropriate heap functions applied to it before you leave your method.

#include <queue>
#include <algorithm>

struct my_special_queue : std::priority_queue<int>
{
    using underlying_queue = std::priority_queue<int>;

    // re-use all constructors
    using underlying_queue::underlying_queue;

    // add a clear method

    void clear()
    {
        underlying_queue::c.clear();
    }

    void remove_all_odd_numbers()
    {
        c.erase(std::remove_if(c.begin(), c.end(), 
                                [](auto&&x) { return (x % 2) == 1; }), 
                                c.end());
        std::make_heap(c.begin(), c.end(), 
                        underlying_queue::comp);
    }

};

int main()
{
    my_special_queue q;

    // standard priority_queue methods
    q.push(1);
    q.push(2);
    q.push(9);
    q.push(6);
    q.push(4);
    q.push(7);

    if (not q.empty()) {
        q.top();
        q.pop();
    }

    // apply our custom functions    
    q.clear();
    q.remove_all_odd_numbers();
}

Upvotes: 2

Rakete1111
Rakete1111

Reputation: 48958

No, there is no way of doing that. The reason being is that if you had access to the underlying container, you could access it and modify it like it wasn't a priority queue, which would be very confusing and against the wanted use case of std::priority_queue, which is to provide a queue.

This is from the Standards point of view, maybe your implementation has an extension that allows that access, but that would be very surprising, and I know no implementation that does this. You should consult the appropriate documentation to be sure.

Having said that, you can always provide a wrapper around std::priority_queue, which stores the container. But I would not recommend it, (as said above) you would be able to change it without the queue semantics.

Upvotes: 5

Related Questions