Tools.h++ Manual

15-16 104011 Tandem Computers Incorporated
15
15.7 A note on how objects are found
Caution – It is important to note that it is the virtual functions of the object
within the collection that gets called when comparing or testing a target for
equality, not that of the target.
For example, consider the following code fragment:
SortedCollection sc;
RWCollectableString member;
sc.insert(&member);
RWCollectableString target;
RWCollectableString* p =
(RWCollectableString*)sc.find(&target);
It is the virtual functions of the objects within the collection, such as member ,
that will get called, not the virtual functions of target :
member.compareTo(&target); // This will get called.
target.compareTo(&member); // Not this.
Hashing
Hashing is an efficient method for finding an object within a collection. All of
the collection classes that use it use the same general strategy. First, member
function hash() of the target is called to find the proper bucket within the
hash table. Buckets are implemented as a singly-linked list. Because all of the
members of a bucket have the same hash value, the bucket must be linearly
searched to find the exact match. This is done by calling member function
isEqual() of the candidate (see above) with each member of the bucket as the
argument. The first argument that returns TRUE is the chosen object.
In general, because of this combination of hashing and linear searching, as well
as the complexity of most hashing algorithms, the ordering of the objects
within a hash collection will not make a lot of sense. Hence, when the
apply() function or an iterator scans through the hashing table, the objects
will not be visited in any particular order.
!