The jtools library has many collection classes. This section provides suggestions and information to help you select the most appropriate collection for a given programming task.
Choosing the most appropriate collection class is not a trivial task. First you must consider the data in your collection. Does your collection need to store the data in order? Will there be duplicate data? How do you find or insert data in your collection? The first part of this section includes a decision tree diagram that lets you consider specific questions about your data and, through your answers, quickly focus on the collections that best fit your data requirements. A preface to the decision tree discusses questions you'll see in the tree and some additional selection criteria.
The questions that appear on the decision tree are brief, to make the diagram easy to read. The following questions expand upon the questions in the decision tree.
Is the order of data in the collection meaningful? Some collections allow you to control the location of data within the collection. For example, arrays and linked lists present data in order. If you need to access data in a particular order, or based on a numeric index, then order is meaningful.
Are duplicate entries allowed? Some collections will not allow you to insert an item equal to an item that is already in the collection. Other collections do permit duplicates, and have various ways to hold multiple matching items. The jtools collections provide mechanisms for both checking for duplication and holding the duplicates.
Is the order determined internally or externally? If data within the collection is controlled by the way you insert it, we say that the order is determined externally. For example, a vector or a linked list is ordered externally. If the data is stored at a place determined by an algorithm used by the collection, then the ordering is internal. For example, a balanced tree has internal ordering.
Is data accessed by an external key? If you access a value based on a key that is not the same as the value, we say that data is accessed by an external key. For example, a phone list associates data, in the form of telephone numbers with keys in the form of names. Conversely, a list of committee members is simply a set of data in the form of names. You do not need a key to get at the information.
Is data accessed by "comparison with self?" To find data that is stored with neither an explicit index nor an explicit key, look for a match between what you need to find and what is contained. The list of committee members mentioned in item 4 is an example of this type of data. Sets or bags are examples of collections that are accessed by comparison with self.
When data is accessed by comparison with self, it is also necessary to know what kind of match is used. Matching based on equality directly compares one object to another; matching based on identity compares object references to see if the objects are the same.
Is the best method of access by following linked nodes? Collections that make use of linked nodes are usually called lists. Lists provide quick access to data at each end of the collection, and allow you to insert data efficiently into the middle of the collection. However, if you need repeated access to data in the middle of the collection, lists are not as efficient as some other collections.
Will most of your access to data be at the ends of a collection? There are many occasions when you need to handle an unknown amount of data, but most of that data handling applies to data that was most recently or least recently put into the collection. A collection that is particularly efficient at handling data that was most recently added is said to have a last in, first out policy. A last in, first out (LIFO) container is a stack. A collection that handles the data in a first in first out (FIFO) manner is called a queue.
For linked lists-Do you need to access the data from only one end of the list, or from both ends? Singly-linked lists are smaller, but they allow efficient access only from the front of the list. Doubly-linked lists have a more flexible access policy, but at the cost of requiring an additional pointer for every stored object.
©Copyright 2000, Rogue Wave Software, Inc.
Contact Rogue Wave about documentation or support issues.