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