This document contains a few notes on how the data structures in this package are implemented. This discussion refers at several points to the classic text in this area: Knuth, The Art of Computer Programming , Vol 3, Hashing. sparsetable For specificity, consider the declaration sparsetable<Foo> t(100); // a sparse array with 100 elements A sparsetable is a random container that implements a sparse array, that is, an array that uses very little memory to store unassigned indices (in this case, between 1-2 bits per unassigned index). For instance, if you allocate an array of size 5 and assign a[2] = [big struct], then a[2] will take up a lot of memory but a[0], a[1], a[3], and a[4] will not. Array elements that have a value are called "assigned". Array elements that have no value yet, or have had their value cleared using erase() or clear(), are called "unassigned". Fo...