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.