Boost.Intrusive Annotated Trees: Part 1

Thursday, 17 January 2013

Most programming problems can be solved using only standard, well-known data structures. Occasionally, though, there's a problem that needs something special.

I needed a container for a GUI app that would display a large, sorted, scrollable table of data, whilst receiving constant updates to the data being displayed. The result is a set of extensions to boost.intrusive that let you create custom extensions to tree-based data strucutres to do things elegantly that would otherwise be difficult, tedious, inefficient or some combination thereof.

The Problem

To process updates to the table, efficient removal and insertion of items is a must. This is the natural habitat of the balanced binary trees, e.g. the ever-popular red/black tree - both operations are O(log n) worst-case. So far so good.

To draw the visible part of the table, I'd calculate what row numbers should be visible based on the scrollbar position, then retrieve those rows from the container. That's a problem for binary trees, because finding the nth element in binary trees is linear time.

The only standard container that has better-than-linear indexing is an array - but arrays have O(n) insertion/removal, and there's nothing you can do to improve on that. So arrays are out of the running - but there's still hope for the tree-based approach.

A Transient Introductory Aside

So, I now have a blog. It's been online for a while, but until today there's been nothing but test content here. Consider this the official launch of my blog - please try to imagine the sound of a bottle being smashed, or a ribbon being cut, or something like that.

I was originally going to launch this blog a month or two ago using a slightly tweaked stock blogger template. Unfortunately, I wasn't happy with it and set about designing a bespoke template with help from @GrahamSnyder.

As a result, there may be significant rendering bugs in anything other than reasonably recent versions of Chrome and Firefox. Please use the comments of this post to complain about any formatting issues :-)