AMDG Hans Joseph Solbrig wrote:
First, could you confirm my belief that there is no STL or Boost container that can sort a list of values such that one can insert arbitrary values in O(log n) and also find the nth highest value in O(log n) time (see http://stackoverflow.com/questions/1746402/whats-a-qt-or-open-source-c-templ... for some discussion)?
Second, I'm implementing such a container on top of a simple b-tree template. Would there be any interest in my cleaning it up and contributing it to boost?
(I'd mostly have to add smart pointers for copy-on-write compatibility).
I believe that the data structure for this is called a rank tree. I don't think there's an implementation in Boost, although there might be something in a SOC project from a few years ago. https://svn.boost.org/trac/boost/browser/sandbox/SOC/2006/tree In Christ, Steven Watanabe