Chapter 9 Collections

The Microsoft Foundation Class Library provides collection classes to manage groups of objects. A collection class is characterized by its “shape” and by the type of its elements. The shape refers to the way the objects are organized and stored by the collection. The Microsoft Foundation Class Library provides three basic collection shapes: arrays, lists, and maps (also known as dictionaries). You can pick the collection shape most suited to your particular programming problem.

Table 9.1 lists the characteristics of the three collection shapes provided with the Microsoft Foundation Class Library. In the table, the term “ordered” means that the order of the items in the collection is determined by the order in which they were inserted and deleted. It does not mean that the items are sorted based on their contents. The term “indexed” means that the items in the collection can be retrieved by an integer index, much like a typical array structure.

Each of the three provided collection shapes is described briefly below, followed by Table 9.1, which compares the features of the shapes to help you decide which is best for your program.

List

The list class provides an ordered, nonindexed list of elements, implemented as a doubly linked list. Lists have a “head” and a “tail,” and adding or removing elements from the head or tail or inserting or deleting elements in the middle is very fast.

Array

The array class provides a dynamically sized, ordered, and integer-indexed array of objects.

Map (also known as a dictionary)

A map is a collection that associates a key object with a value object.

Table 9.1 Shape Features