Boost logo

Boost Users :

Subject: Re: [Boost-users] Container using an item's ordinal position in a sorted list
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2009-12-21 19:36:03


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 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.

In Christ,
Steven Watanabe

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at