### Flat Collections

The following flat collections are provided by the Collection Class Library:

- sets--key sets, sorted sets, key sorted sets
- bags--key bags, sorted bags, key sorted bags
- queues--priority queues
- deques
- heaps
- maps--sorted maps, relations, sorted relations
- sequences and equality sequences
- stacks

#### Combinations of Properties for Flat Collections

The figure below shows the flat collection that results from each combination of properties. For example, Map appears in the Unique, Unordered column for the Key, Element Equality row. This means that a map is unordered, each element is unique, keys are defined, and element equality is defined. This implies that there are no flat collections that have all of the following properties:

- The collection is ordered
- The collection is sequential
- The collection allows an element to appear more than once
- Keys are defined for elements in the collection

The rationale for not implementing collections with these combinations of properties is that there is no reason to choose them over another collection that is already available. For example, for an ordered collection that is sequential and offers access by key, the key access would only have advantages if the elements are stored in a position depending on their key. Because they are not, there is no flat collection with key access that maintains a sequential order.

| Unordered | Ordered
--- | --- | ---
Sorted | Sequential
Unique | Multiple | Unique | Multiple | Multiple
Key (key equality must be defined) | Element Equality | Map | Relation | Sorted map | Sorted relation | N/A
No Element Equality | Key set | Key bag | Key sorted set | Key sorted bag | N/A
No Key | Element Equality | Set | Bag | Sorted set | Sorted bag | Equality sequence
No Element Equality | N/A | Heap | N/A | N/A | Sequence

For example, the default set collection:

- does not allow an item to be added if it is already present in the collection, ensuring that elements are unique
- is not sorted
- cannot locate elements by key

### Trees

Trees can be described either as structures whose elements have a hierarchy or as a special form of recursive structure. Recursively a tree can be described as a node (parent) with pointers to other nodes (children). Every node has a fixed number of pointers, which are set to null at initialization time. Insertion of a new node involves setting a pointer in the parent so that it points to the inserted child. The figure below illustrates the structure of an n-ary tree.

One node is the entry point to the tree. This node is designated as the root. Nodes without any pointers to other nodes are called leaf nodes or terminal nodes.

The Structure of N-ary Trees

Similarly, you can obtain tree-like or recursive structures by implementing the array of children of a node as a flat collection of nodes. This will give you different functionality for the children, for example, the ability to locate a child with a given value.

Trees in general are more useful for searching elements than for adding and deleting elements. For this reason, they are often called search trees. The descriptions of AVL and B* trees explain why trees are well-suited for searching. Generally, you can locate and insert elements in collections implemented as trees faster than you can in collections implemented as lists. However, if you only want to iterate through elements in a collection, it is faster to iterate through the elements of a list.

Introduction to the Collection Classes
Collection Class Hierarchy
Overall Implementation Structure
Element Functions and Key-Type Functions
Collection Class Polymorphism
Collection Characteristics
Ordering of Collection Elements
Access by Key
Equality Relation
Uniqueness of Entries

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
Memory Management with Element Operation Classes
Guard Objects
Instantiating a Guard Object
Using Guard Objects
Class Template Naming Conventions
Possible Implementation Paths
Choosing One of the Provided Implementation Variants
Adding an Element to a Collection
Removing an Element from a Collection
Copying and Referencing Collections
Instantiating the Collection Classes