Four basic properties are used to differentiate between different flat collections:
The elements of a flat collection class can be ordered in three ways:
A particular element in a sorted collection can be accessed quickly by using the ordering relation to determine its position. Unordered collections can also be implemented to allow fast access to the elements, by using, for example, a hash table or a sorted representation. The Collection Class Library provides a fast locate function that uses this structure for unordered and sorted collections. Even though unordered collections are often implemented by sorting the elements, do not assume that all unordered collections are implemented in this way. If your program requires this assumption to be true, use a sorted collection instead.
For each flat collection, the Collection Class Library provides both unordered and sorted abstractions. For example, the Collection Class Library supports both a set and a sorted set. The ordering property is independent of the other properties of flat collections. You can make a given flat collection unordered or sorted regardless of its other properties.
A given flat collection can have a key defined for its elements. A key is usually a data member of the element, but it can also be calculated from the data members of the element by some arbitrary function. Keys let you:
For collections that have a key defined, an equality relation must be defined for the key type. Thus, a collection with a key is said to have key equality.
The Collection Class Library provides sorted and unsorted versions of maps and relations, for which both key and element equality must be defined. These collections are similar to key set and key bag, except that they define functions based on element equality, namely union and intersection. The add function behaves differently for maps and relations than it does for key set and key bag collections.
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.
The terms unique and multiple relate to the key, in the case of collections with a key. For collections with no key, unique and multiple relate to the element.
In some flat collections, such as map, key set, and set, no two elements are equal or have equal keys. Such collections are called unique collections. Other collections, including relation, key bag, bag, and heap, can have two equal elements or elements with equal keys. Such collections are called multiple collections.
For those multiple collections that have keys with element equality (relation and sorted relation), elements are always unique while keys can occur multiple times. In other words, if element equality is defined for a multiple collection with key, element equality is tested before inserting a new element.
A unique collection with no keys and no element equality is not provided because a containment function cannot be defined for such a collection. A containment function determines whether a collection contains a given element.
The behavior during element insertion (when one of the add... methods is applied to a collection) distinguishes unique and multiple collections. In unique collections, the add function does not add an element that is equal to an element that is already in the collection. In multiple collections, the add function adds elements regardless of whether they are equal to any existing elements or not.
Introduction to the
Collection Classes
Collection Class
Hierarchy
Overall
Implementation Structure
Element
Functions and Key-Type Functions
Collection Class
Polymorphism
Adding Elements
Removing
Elements
Replacing
Elements
Flat Collections
Trees
Exceptions
Defined and Used by the Collection Classes
Exception
Causes
Defining
Equality Relation
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
Adding an
Element to a Collection
Removing an
Element from a Collection
