terrencecrowley's comments

FrontPage used an interval tree to represent misnested HTML tags. The browsers would interpret the tags as covering the contained area using ad-hoc parsing techniques (e.g. simply keeping a running character property stack to handle font, b, i tags). Frontpage tried to preserve all the tags and the structure it saw on input while also producing the same visual output so it had a tougher problem. (I wrote that interval tree code.)

Amazing how often just replacing a std::vector with a gap buffer vector implementation will get both the benefits of vector storage combined with good insert/delete behavior (presuming locality of such operations which is often the case, especially when doing something that scans through the array).