C++ priority queue swapping contents

Question

I am writing a class which has three priority queues as private members.

class Foo {
...
...

private:
  // I am fine with using pointers instead if it helps.
  std::priority_queue<int> first;   // min heap.
  std::priority_queue<int> second;  // max heap.
  std::priority_queue<int> third;  // min heap.
};

Now I require first and third to start as min heaps and second as a max heap. As part of the functionality of my class I need to do the following:

1. Move second to first. Ideally this is achieved through lowest amount of copying. The underlying vector should just be moved. Additionally first should now behave like a max heap.
2. Move third to second. This means second should now behave like a min heap.
3. Since third's contents have been moved to second, it should be empty. I would like to either allocate a new underlying vector or re-use first's underlying vector (it doesn't need it any more. Additionally third should now be a max heap.

I need to perform this cycle (max -> min and min -> max) an unknown number of times.

I am struggling to do this with std::priority_queue since the Comparator is a template argument which means I cannot change it at run time. This is preventing me from turning a min heap into a max heap.

So my questions are:

1. Is there a way I could possibly bend std::priority_queue to do my bidding without making it extremely ugly?
2. If not then could I perhaps re-structure my class to do the same thing, but still use std::priority_queue?
3. Otherwise could I maybe re-use most of the heapify logic in the std library to achieve this?

Answer 1

A comparator with state

Actually, the STL provides facilities for exactly your case: You can pass a comparator to the constructor of the priority queue. The key idea is to give comparator some internal state which determines whether a less than or greater than operation should be applied. The comparator type looks like this:

struct LessOrGreater
{
    explicit LessOrGreater( bool isLess ) : isLess{isLess} {}

    bool operator()( int lhs, int rhs ) const
    {
        return isLess == (lhs<rhs);
    }

    bool isLess;
};

The actual type of the priority queue is

using MinOrMaxQueue =
    std::priority_queue<int,std::vector<int>,LessOrGreater>;

The class implementation

Your class can now be implemented in terms of this special priority queue.

class Foo {
public:
    Foo()
        : first { LessOrGreater{ false } } // initialize as min heap
        , second{ LessOrGreater{ true  } } // initialize as max heap
        , third { LessOrGreater{ false } } // initialize as min heap
    {}

    void op(); // The operation you explained

private:
    MinOrMaxQueue first; 
    MinOrMaxQueue second;
    MinOrMaxQueue third; 
};

Now the operation you described could be implemented like this:

void Foo::op()
{
    first  = std::move(second);
    second = std::move(third);
    third  = MinOrMaxQueue{ LessOrGreater{ true } }; // might throw!
}

Making it exception-safe

However, this code is not exception-safe. Since the default constructor of std::vector<int> might throw (the C++ standard does not guarantee no-fail here!) the third line of the op() function could throw leaving the Foo object in an invalid state. Here's an implementation that is strongly exception-safe and most likely just as efficient:

void Foo::op()
{
    MinOrMaxQueue tmp{ LessOrGreater{ true } };
    first .swap( second );
    second.swap( third );
    third .swap( tmp );
}

The first line is the only line that could possibly throw but it does not modify the Foo object. So throwing does cannot possibly damage anything. The remaining three lines never throw and hence the function is strongly exception-safe.

Answer 2

I think you could use a a plain std::vector as the data storage and then have an adapter to specify the heap property. The adapter internally keeps a std::vector to store the data and stores the current comparator. Let me see if this works with your three requirements:

class Heap
{
    Heap& opertor=(Heap&& h)
    {
        swap(*this, h);
        return *this;
    }

    void setComparator( std::function<bool (int, int)> c)
    {
        comparator = std::move(c);
    }

    void insert(int x)
    {
        // use std::push_heap to insert x with current comparator.
    }

    void swap(Heap& h)
    {
        swap(comparator, h.comparator);
        swap(data, h.data);
    }
private:
    std::function<bool (int,int)> comparator;
    std::vector<int> data_;
};

1. Move second to first. Ideally this is achieved through lowest amount of copying. The underlying vector should just be moved. Additionally first should now behave like a max heap.

That could be done by calling first = std::move(second). Now the data is moved and the comparator will be set to the one from second, making first a max heap in the future.

1. Move third to second. This means second should now behave like a min heap.

Same as above. second = std::move(thid). Comparator gets reset and it will behave like a min heap.

1. Since third's contents have been moved to second, it should be empty. I would like to > either allocate a new underlying vector or re-use first's underlying vector (it doesn't > need it any more. Additionally third should now be a max heap.

After moving, third will be in a valid but undefined state. You can not rely on the memory being there, so you will have to bring it to a valid and defined state. You could use third.clear(); third.resize( n ).

Answer 3

Is there a way I could possibly bend std::priority_queue to do my bidding without making it extremely ugly?

You could write a wrapper that hides the predicate and uses inheritance behind the scenes. However, that seems overkill.

If not then could I perhaps re-structure my class to do the same thing, but still use std::priority_queue?

You could wrap the access to the queues in functions. Then use a bool or integer variable to check which queue needs to be accessed.

Otherwise could I maybe re-use most of the heapify logic in the std library to achieve this?

This sounds like the best option, based on what you explained. Store each priority_queue in a std::vector and use the std::make_heap, std::push_heap and std::pop_heap functions to manage the heap structure. If you keep all priority queues in a std::array<std::vector<int>, 3>, you can use std::rotate to perform the logic you described. In addition, you would need to keep a boolean variable indicating which predicate to use for the heap operations.