### Introduction to the Collection Classes

Collections are used to store and manage elements (or objects) of a user-defined type. Different collections have different internal structures, performance characteristics, and access methods for storage and retrieval of objects. The Collection Classes implement the common collection types, such as trees, relations and ordered lists. They provide a framework of properties to help you decide which abstract collection type is appropriate in a given situation, and allow you to choose how the abstract data type you have chosen is implemented.

The Collection Classes let you choose the appropriate collection type for a given situation by providing collection classes which have a systematic and consistent combination of basic properties. These properties help you to select the appropriate level of abstraction. For example, you may have the choice between using a bag and a key sorted set. The properties of these two collections will help you decide which one is more appropriate.

The Collection Classes offer you a choice of implementations for each type of collection. Each abstract collection class has a common interface with all of its possible implementations. It is easy to replace one implementation with another for performance reasons or if the requirements of your application change.

#### Types of Classes

The Collection Classes are divided into three types:

- Trees--recursive collections of nodes, where each node holds an element and has a given number of nodes as children
- Flat collections--the most common types of collections, include abstractions such as sequence, set, bag, and map. Unlike trees, flat collections have no hierarchy of elements or recursive structure.
- Auxiliary classes--support other classes and include classes for cursors, iterators, and simple and managed pointers.

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
Adding Elements
Removing Elements
Replacing Elements
Overview of Iteration
Iteration with Cursors
Iteration with allElementsDo
Flat Collections
Trees

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
Class Template Naming Conventions
Possible Implementation Paths
Choosing One of the Provided Implementation Variants
Copying and Referencing Collections
Choosing the Appropriate Smart Pointer Class
Replacing the Default Implementation
Taking Advantage of the Abstract Class Hierarchy
Instantiating the Collection Classes