Stabilizing a priority deque is not as simple as stabilizing a priority queue. The priority queue can be stabilized by appending to each element of the heap an integer "tie breaker" such that each new element's tie breaker is greater than that of any previous element. Problems with overflow can be dealt with (in O(n) time) by adjusting all tie breakers simultaneously and reconstructing the heap. The same method will work for priority deques, but with one important difference: if the maximum element is stable (FIFO), the minimum element would have the reverse order (LIFO). Correcting this is likely to require searching through all elements indistinguishable from the minimum, which is potentially linear rather than logarithmic. Personally, I would prefer to create the stabilized priority deque (with notes about the behavior) as a thin wrapper around the unstable deque. This is primarily because the stabilized deque may not be able to offer the same options as the unstable deque (such as choice of underlying container).
I assume that you're referring to begin_mutable, end_mutable, and make_valid?
I was thinking of begin, end, set, and erase actually. Exposing (as protected member functions) the ability to make large-scale changes to the deque has immediately apparent advantages. In particular, it would allow a (mostly) stabilized heap to operate in amortized O(log n) time, O(n) worst case. Editing or removing a single element is highly situational, especially when the iterators used to find that element must be discarded immediately afterward.
Please consider (and document) the exception safety guarantees that you provide. From a brief glance at the code, I suspect that merge and push, at least can leave an invalid heap if they throw.
Good point. I hadn't considered exception-safety until you suggested it. If movement and comparison do not throw, I believe I will be able to offer as strong a guarantee as offered by the operations on the underlying container. If they can throw, I can offer the basic guarantee, but only because an empty heap is a vacuously valid heap. I'll keep working to try to improve these.
You're going to need a lot more tests. In particular, you need to check that pushing and popping values gives the correct results, not just that the priority_deque's invariants hold.
You are correct. I do need more tests. My original plan was to wait to create unit tests until the revision stage was done, because testing preservation of invariants is more sensitive to failures than most other tests, but I can see your point (need to make sure that the elements added are actually in the deque, and that the popped elements are indeed removed from it).
What I'd actually prefer to see is for this to be implemented as algorithms akin to std::push_heap and std::pop_heap. That way priority_deque is just a thin wrapper
If your implementation would have std::make_heap/etc functions (which are desirable on their own, as Steven mentioned) then it is even >possible to have two interfaces: Boost.Heap-like and std::priority_queue-like.
I think it is worth to consider to make it part of Boost.Heap library ( http://www.boost.org/doc/libs/1_55_0/doc/html/heap.html ).
I had considered this possibility previously, but I thought the interfaces of the private functions were too complicated to expose to an average user. There are also some concerns over whether an average user would find my internal design choices to be intuitive. For example, I realized early on that either the minimum or maximum would have a slight performance advantage over the other, depending on how I constructed my intervals. Because the priority deque is so similar to the priority queue, I decided to give the advantage to the maximum; this has resulted in intervals of the form [max, min], rather than the intuitive [min, max]. It would not be difficult to change this, but it is still something to consider. Nevertheless, this is worth revisiting. I will consider ways to simplify, separate, and make intuitive the interval-heap functions.
* mutability
I would appreciate a clarification of what was meant. I included functions for traversing the deque, editing individual elements, and editing large numbers of elements, so I must assume that my intuitive definition of the meaning of "mutability" differs from yours.