Tools.h++ Manual

15-6 104011 Tandem Computers Incorporated
15
15.3 Overview
This section gives a general overview of the various Smalltalk-like collection
classes to help you chose an appropriate one for your problem.
Bags versus Sets versus Hash Tables
Class RWHashTable is the simplest to understand. It uses a simple hashed
lookup to find the "bucket" that a particular object occurs in, then does a linear
search of the bucket to find the object. A key concept is that more than one
object with the same value (that is, that tests "isEqual") 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. Subsequent occurrences merely increment an "occurrence" count.
It is implemented as a dictionary where the key is the inserted object and the
value is the occurrence count. This is how 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 are not
true Bags.
Class RWSet inherits from RWHashTable . It is similar except that duplicates
are not allowed. That is, if you try to insert more than one object with a given
value, duplicates are rejected.
Class RWIdentitySet inherits from RWSet . It retrieves objects on the basis of
identity instead of value. Because it is a Set, only one instance of a given object
can be inserted.
Note – The ordering of objects in any of these hash-table based classes is not
meaningful. If ordering is important, then you should chose a sequenceable
class.