Now that you have reviewed the list of Smalltalk-like collection classes, their class hierarchy, and an example of how they work, you may be wondering how you can use them. This section gives an overview of the various Smalltalk-like collection classes to help you choose an appropriate one for your problem. You can also see Appendix A, on choosing.
Class RWHashTable is the easiest Smalltalk-like collection class to understand. It uses a simple hashed lookup to find the bucket where a particular object occurs, then does a linear search of the bucket to find the object. A key concept is that multiple objects that test isEqual to each other can be inserted into a hash table.
Class RWBag is similar to RWHashTable, except that it counts occurrences of multiple objects with the same value; that is, it retains only the first occurrence and merely increments an occurrence count for subsequent ones. RWBag is implemented as a dictionary, where the key is the inserted object and the value is the occurrence count. This is the same way the Smalltalk Bag object is implemented. Note that this implementation differs significantly from many other C++ Bag classes which are closer to the RWHashTable class and not true Bags.
Class RWSet is similar to its base class RWHashTable, except that it doesn't allow duplicates. If you try to insert an object that isEqual to an object already in RWSet, the object will be rejected.
Class RWIdentitySet, which inherits from RWSet, retrieves objects on the basis of identity instead of value. Because RWIdentitySet is a Set, it can take only one instance of a given object.
Note that the ordering of objects in any of these classes based on hash tables is not meaningful. If ordering is important, you should choose a sequenceable class.
Classes inheriting from RWSequenceable have an innate ordering. You can speak meaningfully of their first or last object, or of their 6th or ith object.
These classes are implemented generally as either a vector, or a singly-linked or doubly-linked list. Vector-based classes make good stacks and queues, but poor insertions in the middle. If you exceed the capacity of a vector-based collection class, it will automatically resize, but it may exact a significant performance penalty to do so.
Note that the binary and B-tree classes can be considered sequenceable in the sense that they are sorted, and therefore have an innate ordering. However, their ordering is determined internally by the relative value of the collected objects, rather than by an insertion order. In other words, you cannot arbitrarily insert an object into a sorted collection in any position you want because it might not remain sorted. Hence, these classes are subclassed separately.
Sometimes referred to as maps, dictionaries use an external key to find a value. The key and value may be of different types, and in fact usually are. You can think of dictionaries 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 approach would contrast with your approach for 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. For these classes, both keys and values must inherit from the abstract base class RWCollectable.