[boost] [Container] Priority Deque - Refinement

Subject: [boost] [Container] Priority Deque - Refinement
From: Nathaniel McClatchey (njmcclatchey1990_at_[hidden])
Date: 2013-11-23 13:20:48

Hi.

I've recently made a double-ended priority queue (priority deque) publicly
available at https://github.com/nmcclatchey/Priority-Deque , with the
intent of submitting it to Boost (more specifically, I wish to make it part
of Boost.Container). I would appreciate any comments, discussion, or
refinements.

Goals of the project:
* Provide an efficient double-ended priority queue, with interface similar
to std::priority_queue.
* Keep requirements to a minimum. In particular, require nothing except
what is already required by std::priority_queue.
* Make it fast. Performance should be competitive with std::priority_queue.

How goals are met:
* The priority deque is implemented as a single class template, mimicking
std::priority_queue
* The interface of priority_deque is a strict superset of the interface of
std::priority_queue. New functions follow the STL naming scheme.
* The underlying container is assumed to be a sequence container supporting
random-access iterators, front(), back(), and push_back(), as in
std::priority_queue. No other assumptions are made.
* The underlying data structure is an interval heap, which allows finding
min/max in O(1) time, and single-element changes in O(log n) time.
* Benchmarks (on queues with 20,000,000+ elements) indicated that the
difference in performance between std::priority_queue and the priority
deque is negligible when compiled by GCC with the O3 option.

A specific question for anyone more experienced with development of
generalized code:
* I added several functions for controlled access to arbitrary elements. Is
this overkill? If so, should they be removed?

Thank-you for your time,
Nate