Introduction to the Collection Classes
Collection Characteristics
Equality Relation
Overview of Iteration
Iteration with Cursors
Iteration with allElementsDo
Flat Collections
Trees
A flat collection can have an equality relation defined for its elements. The default equality relation is based on the element as a whole, not just on one or more of its data members (for example, the key). For two elements to be equal, all data members of both elements must be equal. The equality relation is needed for functions such as those that locate or remove a given element. A flat collection that has an equality relation has element equality.
Note: For collections containing non-built-in types, you can define your own equality relation to behave differently. For example, your equality relation could test only certain data members of two elements to determine element equality. In such cases, element equality may apply to two elements even when the elements are not exactly equal.
The equality relation for keys may be different than the equality relation for elements. Consider, for example, a job control block that has a priority and a job identifier that defines equality for jobs. You could choose to implement a job collection as unordered, with the job ID as key, or as sorted by priority, with the priority as key. In the first case, you have fast access through the job ID but not through the priority; in the second case, you have fast access through the priority but not through the job ID. The ordering relation on the priority key in the second case does not yield a job equality, because two jobs can have equal priorities without being the same.
typedef unsigned long JobId;
typedef int Priority;
class Job {
JobId ivId; // These are private data members.
Priority ivPriority;
public:
JobId id () const { return ivId; }
Priority priority () { return ivPriority; }
};
// If ivId is the key:
JobId const& key (Job const& t)
{ return t.id (); }
// If ivPriority is the key:
Priority const& key (Job const& t)
{ return t.priority (); }
// ...
Functions like locateElementWithKey use the equality relation on keys to locate elements within a collection. A collection that defines key equality may also define element equality. Functions that are based on equality (such as locate) are only provided for collections that define element equality. Collections that define neither key equality nor element equality, such as heaps and sequences, provide no functions for locating elements by their values or testing for containment. Elements can be added and retrieved from such collections by iteration. For sequences, elements can also be added and retrieved by position.
Introduction
to the Collection Classes
Collection Characteristics
Equality
Relation
Overview
of Iteration
Iteration
with Cursors
Iteration with allElementsDo
Flat
Collections
Trees
Defining Key or Element
Equality
Defining an
Operations Class
Implementing
Element- and Key-Type Functionality
Defining
Member Functions of the Element Object Type
Defining
Separate Global Functions
Using or
Defining an Element Operation Class
Things to
Watch Out For
Choosing the
Appropriate Smart Pointer Class
Constructing Smart
Pointers
Using Element
Pointers
Using Cursors to Locate
and Access Elements
Instantiating the
Collection Classes
