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.