nmcclatchey / priority-deque

A double-ended priority queue in STL style.

Priority-Deque

This project is my implementation of a priority deque (double-ended priority queue) as a C++ class template.

Goals:

• Interface similar to STL.
  • Status: Complete.
  • priority_deque implements the std::priority_queue interface.
  • Additional functions, for double-ended access and random-access among others, are in STL style.
• Interface in Boost style.
  • Status: Incomplete.
• Performance competitive with STL's priority_queue.
  • Status: Close.
  • Benchmarks indicate ~20% slower performance in push, ~15% slower in pop. (GCC, -O3)
  • Bulk-loading is optionally threaded, with the following benchmarked performance ratios (deque time : queue time, smaller is better):
    • 1.228 : 1 (1 CPU core)
    • 0.874 : 1 (2 CPU cores)
    • 0.545 : 1 (4 CPU cores)
• Provide the strongest exception-safety guarantee possible without compromising performance.
  • Status: Complete.
  • Most operations, including provide the strong (rollback) exception-safety guarantee if comparison throws.
  • Bulk-loading operations such as merge cannot provide this guarantee without compromising performance.
  • The random-access update method can only provide the strong guarantee by copying an element or using move semantics.
• Provide thread safety comparable to that of STL structures.
  • Status: Complete.
  • Functions have no side-effects besides the obvious (deque or interval heap may be altered), and can safely be called in threads, though a single queue should not be accessed by multiple threads simultaneously. Multiple reads are okay; simultaneous read-write and write-write may cause race conditions.

priority-deque's Issues

Is this free for commercial use?

I see it's a boost candidate, but I thought I should check since there's no license included.

And would you say it's production ready?

Thanks!

Self move assign issue.

On interval_heap.hpp:273

The swap(*first, *last); can do a self swap which fails in older gcc's before 11.2 when using debug mode because it was undefined behavior. It would say something like "Error: attempt to self move assign."

Simply add if (first != last) before the swap to fix it.

This issue is because of the following behavior:
gcc-mirror/gcc@c2fb0a1