### Collection Characteristics

Four basic properties are used to differentiate between different flat collections:

- Ordering--Whether a next or previous relationship exists between elements.
- Access by key--Whether a part of the element (a key) is relevant for accessing an element in the collection. When keys are used, they are compared using relational operators.
- Equality for elements--Whether equality is defined for the element.
- Uniqueness of entries--Whether any given element or key is unique, or whether multiple occurrences of the same element or key are allowed.

### Ordering of Collection Elements

The elements of a flat collection class can be ordered in three ways:

- Unordered collections have elements that are not ordered.
- Sorted collections have their elements sorted by an ordering relation defined for the element type. For example, integers can be sorted in ascending order, and strings can be ordered alphabetically. The ordering relation is determined by the instantiations for the collection class. For elements where the ordering relation returns the same position, elements are added in chronological order.
- Sequential collections have their ordering determined by an explicit qualifier to the add function, for example, addAtPosition.

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.

### Access by Key

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:

- Organize the elements in a collection
- Access a particular element in a collection

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.

### Equality Relation

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.

### Uniqueness of Entries

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