[boost] Priority Deque Container Adaptor

Subject: [boost] Priority Deque Container Adaptor
From: Nathaniel McClatchey (njmcclatchey1990_at_[hidden])
Date: 2012-07-03 01:06:23

Greetings.
I have written a container adaptor implementing efficient double-ended
priority queues. This preliminary submission is made to determine
if/when a formal submission should be made and in the hope that it
will be improved by your comments and reviews.

The library (a single header file) is publicly available on mediafire:

http://www.mediafire.com/download.php?gq8qjpgdoecgqq2

All files are distributed under the Boost Software License, Version 1.0.

An explanation of what it does:
This library replicates all functions of the STL priority_queue and
adds functions for efficient access to the other end of the queue.
Where the STL priority_queue uses a max-heap, I use a max-min heap
(see article on Wikipedia). This leads to O(log n) complexity for
single-element operations, and O(n) complexity for initialization and
merging.

TL;DR: Double-ended priority queue with algorithmic complexity
equaling the STL single-ended priority queue.

The current revision has been tested on:
GCC 4.7.0 (MinGW on Windows 7 x64)
Microsoft Visual C++ 2010 (on Windows 7 x64)

Documentation may be generated by Doxygen.

Any comments, criticisms, or compatibility information will be appreciated.

I currently have one decision to make that requires experience beyond
mine. Some const functions require calling operator() in a comparison
class; should I make the class mutable, make a non-cost copy of the
comparison class when needed, or require that operator() be a const
function? So far, I have avoided the last option because it would make
the class prerequisites more strict.

Thanks,
Nathaniel McClatchey