The incentive to write a nested, heterogeneous container in C++ surfaced during the SUCHTHAT project [11]. Therein we are working on the implementation of a SuchThat compiler. The first prototype's back-end [14], as well as many of the other components, were implemented in Scheme [8]. One of Scheme's main advantages is the powerful list data structure, which can hold arbitrary data types1. This allows the user to build nested lists, e.g. to represent a parse tree or symbol table. Our current focus is on merging Tecton [7] with SuchThat. Due to severe performance problems with our first prototype we have switched to C++ as implementation language. The STL provides basic containers that suit most simple needs and exhibit very good runtime behavior. The containers' major drawback for our purposes is the inability to hold objects of different types and that they do not support nesting. We will show that exploitation of C++'s newest technologies, like templates and run-time type information (RTTI), leads to a powerful data structure based on the STL. We think that the different paradigms of generic, object oriented and functional programming, which often are seen as adversaries, can instead complement each other.
...
Postscript Version (537kb), gziped Postscript Version (156kb), Online Version

The source code presented in the paper is available for download: nseq-0.1.tgz