Selecting an Essential Tools Module Collection Class
These decision tree diagrams include questions about the data you plan to store in your collection. By traversing the trees, you can quickly see which Essential Tools Module collection classes will best suit your data and programming project.
Using the Decision Trees
The decision trees start with an initial set of questions to determine whether you will use the container types set, map, list, or vector. Depending on your choice, additional decision trees help to further refine the type of collection you should use, depending on whether you are using collectable classes or templates.
Additional Selection Criteria
Which collection you choose will depend of many things (not the least of which will be your experience and intuition). In addition to the decision trees, the following questions will also influence your choice of container.
1. Do I need to maintain a single object in multiple collections? Use a pointer-based collection.
2. Am I collecting objects that are very expensive to copy? Use a pointer-based collection.
3. Is there no compelling reason to use a pointer-based collection? Use a value-based collection.
4. Do I want to control the order of the objects within the collection externally? Use a sequential collection such as a vector or list.
5. Should the items within the collection be mutable (not fixed) after they are inserted? Use a sequential or mapping (dictionary) collection. Maps and dictionaries have immutable keys but mutable values.
6. Would I prefer that the collection maintain its own order based on object comparison? Use a set, map, or sorted collection.
7. Do I wish to access objects within the collection based on a numerical index? Use a sequential or sorted collection.
8. Do I need to find values based on non-numeric keys? Use a map or dictionary.
9. Would I prefer to access objects within the collection by supplying an object for comparison? Use a set, map or hash-based collection.
10. Am I willing to forego meaningful ordering, and use some extra memory in return for constant-time look-up by key? Use a hash-based collection.
11. Do I need fast lookup and insertion in a collection that grows or shrinks to meet the current need? Use a b-tree, or an associative container based on the Standard C++ Library.
12. Do I need to access the data without bringing it all into memory? Use
RWBTreeOnDisk.
Decision 1: Determine the Collection Type
First, determine the general collection type.
1. Is the data accessed by key or position? Data access by position is either numerical or in relation to the beginning or end of a container. Data access by key normally finds the item based on its key.
2. Is the key also the value? The key can either be a value that is associated with the item or the item itself.
3. Do references to data need to be preserved after insertion or deletion? If the references to data become invalid after an insertion or deletion operation, the references must be obtained again from the container.
Based on these questions, you’ll have chosen either a set, map, list, or vector.
Now, choose either a collectable class or a template class. If your container type is
RWCollectable, you will usually use one of the
“RWCollectable Classes” ; otherwise, use a template class.
Choose:
Set
1. Are duplicates allowed? Some collections disallow the insertion of an item equal to an item already in the collection. Other collections do permit duplicates, and have various ways to hold multiple matching items. The Essential Tools Module collections provide mechanisms for both checking for duplication and holding the duplicates.
2. Is the order of data meaningful? Some collections allow you to control the location of data within the collection. If you need to access data in a particular order, or based on a numeric index, then order is meaningful.
3. What is the storage method for duplicates? Duplicate items can be stored in a collection either as individual items or by a count of duplicates.
4. What is the comparison method when duplicates are not allowed? Key comparison uses either key equality in which the key must be equal, or key identity in which the key must reference the same address.
1. Are duplicates allowed? Some collections disallow the insertion of 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 Essential Tools Module collections provide mechanisms for both checking for duplication and holding the duplicates.
2. Is the order of data meaningful? Some collections allow you to control the location of data within the collection. If you need to access data in a particular order, or based on a numeric index, then order is meaningful.
3. Use some extra memory in return for constant-time lookup by key? Achieve faster access by increasing each item’s memory requirement.
Map
1. Is the order of data meaningful? Some collections allow you to control the location of data within the collection. If you need to access data in a particular order, or based on a numeric index, then order is meaningful.
2. Are objects stored on disk file? Storing on disk allows access to the data without bringing it all into memory.
3. What is the comparison method? Key comparison uses either key equality in which the key must be equal, or key identity in which the key must reference the same address.
1. Are duplicates allowed? Some collections disallow the insertion of 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 Essential Tools Module collections provide mechanisms for both checking for duplication and holding the duplicates.
2. Is the order of data meaningful? Some collections allow you to control the location of data within the collection. If you need to access data in a particular order, or based on a numeric index, then order is meaningful.
3. Use some extra memory in return for constant-time lookup by key? Achieve faster access by increasing each item’s memory requirement.
Vector
1. Is the order intrinsic or external? If the data within the collection is controlled by how it is inserted, the order is determined externally. If the data is stored in a location based on an algorithm used by the collection, then the ordering is intrinsic.
1. Is the order intrinsic or external? If the data within the collection is controlled by how it is inserted, the order is determined externally. If the data is stored in a location based on an algorithm used by the collection, then the ordering is intrinsic.
2. Is the number of items in the collection fixed? The size of the collection is fixed on construction and will not resize automatically.
List
1. Is bi-directional access needed? If needed, the collection can be iterated forwards and backwards.
2. What is the primary access method? The linked-nodes method allows data access in the middle of the collection, whereas the at-ends method allows data access only at the start or end of the collection.
1. Is bi-directional access needed? If needed, the collection can be iterated forwards and backwards.
2. What is the primary access method? The linked-nodes method allows data access in the middle of the collection, whereas the at-ends method allows data access only at the start or end of the collection.
3. Is the order intrinsic or external? If the data within the collection is controlled by how it is inserted, the order is determined externally. If the data is stored in a location based on an algorithm used by the collection, then the ordering is intrinsic.
4. Are items implicitly linked-list nodes? Each item is a linked-list node managed by the user.