Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 133

not get at a record of the dictionary that he didn't already know the key value for.
With the removeAny method, the user can process all records in the dictionary as
shown in the following code fragment.
while(dict.size()>0){
it=dict.removeAny();
doSomething(it);
}
There are other approaches that might seem more natural for iterating though a
dictionary, such as using a “first” and a “next” function. But not all data structures
that we want to use to implement a dictionary are able to do “first” efficiently. For
example, a hash table implementation cannot efficiently locate the record in the
table with the smallest key value. By using RemoveAny , we have a mechanism
that provides generic access.
Given a database storing records of a particular type, we might want to search
for records in multiple ways. For example, we might want to store payroll records
in one dictionary that allows us to search by ID, and also store those same records
in a second dictionary that allows us to search by name.
Figure 4.30 shows an implementation for a payroll record. Class Payroll has
multiple fields, each of which might be used as a search key. Simply by varying
the type for the key, and using the appropriate field in each record as the key value,
we can define a dictionary whose search key is the ID field, another whose search
key is the name field, and a third whose search key is the address field. Figure 4.31
shows an example where Payroll objects are stored in two separate dictionaries,
one using the ID field as the key and the other using the name field as the key.
The fundamental operation for a dictionary is finding a record that matches a
given key. This raises the issue of how to extract the key from a record. We would
like any given dictionary implementation to support arbitrary record types, so we
need some mechanism for extracting keys that is sufficiently general. One approach
is to require all record types to support some particular method that returns the key
value. For example, in Java the Comparable interface can be used to provide this
effect. Unfortunately, this approach does not work when the same record type is
meant to be stored in multiple dictionaries, each keyed by a different field of the
record. This is typical in database applications. Another, more general approach
is to supply a class whose job is to extract the key from the record. Unfortunately,
this solution also does not work in all situations, because there are record types for
which it is not possible to write a key extraction method. 2
2 One example of such a situation occurs when we have a collection of records that describe topics
in a library. One of the fields for such a record might be a list of subject keywords, where the typical
record stores a few keywords. Our dictionary might be implemented as a list of records sorted by
keyword. If a book contains three keywords, it would appear three times on the list, once for each
associated keyword. However, given the record, there is no simple way to determine which keyword