Tools.h++ Manual

104011 Tandem Computers Incorporated 15-7
15
Sequenceable classes
Classes inheriting from RWSequenceable have an inate ordering. That is, it is
meaningful to speak of the "6'th object", or the "first" or "last" object.
These classes are generally implemented either as a vector or as a singly- or
doubly-linked list. You should be aware of the differences: vector based classes
make good stacks and queues, but are poor at insertions in the middle. If you
exceed the capacity of a vector-based collection class it will automatically
resize, but there may be a very significant performance penalty for it to do so.
Note – The binary and B-Tree classes could be considered "sequenceable" in the
sense that they are sorted and, therefore, have an inate ordering. However, the
ordering is determined internally, by the relative value of the collected objects,
rather than by an insertion order. That is, you cannot arbitrarily insert an
object into a sorted collection in any position you wish: it might not remain
sorted. Hence, these classes are subclassed separately.
Dictionaries
Dictionaries (sometimes called “maps”) use an external key to find a value. The
key and value may be (and usually are) of different types. You can think of
them as associating a given key with a given value. For example, if you were
building a symbol table in a compiler, you might use the symbol name as the
key, and its relocation address as the value. This contrasts with the approach
one might make using a Set, where the name and address would have to be
encapsulated into one object.
Tools.h++ provides two dictionary classes: RWHashDictionary (implemented
as a hash table) and RWBTreeDictionary (implemented as a B-Tree). Both
keys and values must inherit from the abstract base class RWCollectable .