Re: [boost] [Container] Priority Deque - Refinement

Subject: Re: [boost] [Container] Priority Deque - Refinement
From: Nathaniel McClatchey (njmcclatchey1990_at_[hidden])
Date: 2013-12-12 16:01:23

I have updated the main branch (
https://github.com/nmcclatchey/Priority-Deque ).
- More appropriate names have been chosen. interval_heap.hpp, for example,
provides make_interval_heap, push_interval_heap, etc. In
priority_deque.hpp, the member function "set" was changed to "update" to be
more consistent with the way Boost.Heap names things.
- Exception-safety guarantees have now been documented for both
priority_deque.hpp and interval_heap.hpp. Where possible (push/pop/update
with non-throwing move or copy), the strong guarantee has been provided.
The multiple-element functions, such as make_interval_heap, provide only
the basic guarantee because the strong guarantee would cripple performance.

If you think a guarantee can be strengthened, that a better nomenclature is
available, please let me know. As always, any other comments are also
welcome.

Now that I have more thoroughly examined Boost.Heap, I can conclude that
implementing the following concepts and interfaces would impractical when
mimicking the STL priority_queue interface, which allows the user to
specify the type of underlying container:
- Template options. These would require that I depart from the interface of
std::priority_queue.
- Stability. Adding a stability counter would require modifying the type
stored in the underlying container and would (slightly) decrease
performance.
- Mutability. I'd need to implement handles, which have the same objections
as stability. I have provided a more limited version of Boost.Heap's
mutability, which modifies at an iterator.
- Ordered Iterators. I can think of at least one way to add these, even
without departing from STL's interface, but it is not truly practical
because it would require O(n) additional memory.

Of these concepts, at least mutability can be created with relative ease in
a separate class which does not let the user choose the underlying
container. Stability can be added, with the caveat that if one end is FIFO,
the other is necessarily LIFO. As such, I think Panasyuk's suggestion is
the wisest option in this case.

The project to-do list is currently:
- Tests. I need to write lots and lots of tests for this class, including
tests of exception-safety guarantees.
- A separate priority deque class which fully conforms to the Boost.Heap
interface, rather than STL interface. This class can then provide stability
and mutability.
- See if I can make any functions in interval_heap.hpp more elegant.

> in theory, yes ... though i doubt this is an issue in the real world ...
> especially one can do quite a lot of work before a 64bit counter
> overflows and if this really turns out to be a problem ... just use a
> larger counter ;)

Yes, it's true that a 64-bit counter does effectively solve the problem.
However, using a large counter may decrease performance (especially if it
increases the likelihood of a page fault), and increase required memory.
Thus it may be worthwhile to have the failsafe fix all problems, if for no
reason other than permitting safe use of smaller counters on mobile or
low-memory devices.