nset is a C++ class for storing sets of natural numbers. Determining set membership is constant time. It is very space efficient for dense sets and roughly as space efficient as a tree for sets whose density (N / (max - min)) is greater than ~.6%.
The set is implemented as a heirarchy of bitmaps. You can think of it as a typical bit set with the added bonus that you can find all the 1's in O(log n) time. It is a cousin to the prefix tree.
ohash is a C++ class implementing a hash table that uses open-addressing and double-hashing. This means that, rather than using linked lists inside each of the hash buckets, elements are stored directly in the hash. When a collision occurs, other buckets in the hash are searched to see if they are available. The buckets searched are determined using a second hashing algorithm in order to avoid clustering.
This kind of hashing is useful when you know the desired size of your hash table in advance and need ordinal access to the elements -- that is, you wish to be able to access them using array indices.
The hash does not grow automatically (as this invalidates all those ndices that we were so delighted to have), so this is a poor choice of data structure if you don't have any sense of how large your hash may need to be.
Another anti-feature of this hash is that erasure cannot feasibly be provided due to the nature of the collision resolution.
To reduce memory usage and enable fast sequential walk of the hash, ohash uses nset to keep track of which slots are occupied.
oslist was an experiment, rather than a data structure that I knew to be useful.
oslist is a C++ class that represents a list (implemented as a red-black tree) which keeps order statistics, enabling one to fetch items by ordinal value in O(lg N) time rather than O(N) time. The trade-off is that insertion and removal also take O(lg N) time, rather than O(1).
Light experimentation shows that, assuming a random access pattern, a few hundred thousand items need to be involved before oslist provides a performance advantage over an ordinary linked list. The higher constants and O(lg N) insertion and removal go a long way toward offsetting the gains of O(lg N) rather than O(N) seeks. Less than random access patternns, unless they favor the middle of the list (or any area except the beginning, for a singly linked list), will further negate the advantage of oslist. Ditto if iterators into the needed parts of the list can be kept around, thus avoiding the seek cost that oslist ameliorates.
The interface is STL-like. Seeking based on ordinal values is performed with the nth method, rather than square brackets. I chose a method since square brackets tend to imply different semantics than oslist exhibits: removing item #0 will cause all items in the list to shift down, and access via ordinal value is not a constant time operation.
Optimization has not been performed. I have observed a notable difference in the performance of std::set class and the RB-tree code in oslist.h. I believe that most oslist operations could be sped up by no less than a factor of ten.