[boost] Augmented trees

Subject: [boost] Augmented trees
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-10-11 10:23:30

Dear Experts,

I find myself in need of an augmented tree.  My problem is something 
like [but not exactly] this:

- Say I have a line of text, i.e. a sequence of characters, in a 
variable-width font; each character stores its width in pixels.

- I need to efficiently insert and remove characters.

- I need to efficiently find the range of characters that spans a given 
range of pixels.

It seems to me that an augmented tree lets me do all of those 
operations in log(N) time - and no other data structure offers the same performance.

I'm aware of two augmented trees that have been proposed here.  
Francisco Jose Tapia has proposed "Countertree", but this only stores 
the count of elements not the sum of a property of the elements (i.e. 
the widths in my example).  Vadim Stadnik has proposed stl_ext_adv, 
which is a doubly-augmented B+ tree.  Has anyone looked at Vadim's code 
since it was proposed last year?  I have a couple of concerns about 
Vadim's proposal:

1. It uses B+ trees, and in the discussion it was suggested that these 
are inferior to red-black trees in some way.

2. In order to get the property to be accumulated (i.e. the widths in 
my case) it requires that arithmetic can be done on the stored type 
itself; this is fine for e.g. a sequence of ints, but if the stored 
type is a struct it is necessary to add various "unnatural" operator 
overloads.  I think I would prefer it to have some sort of 
user-supplied accessor to get the property to be accumulated.

Is there any other work that I've overlooked?

Is there a "friendly" red-black tree implementation somewhere that 
could be augmented relatively easily?

Regards,  Phil.