A collection is an object that stores other objects called elements. Typically, a collection provides methods for accessing, adding, and removing elements. An implementation of a collection will often target one of these methods for optimization.
Collections (also called containers, stores, or data structures) are abstractions of main memory—a static array of bytes.
A generic collection doesn't care about the type of objects it is asked to store. A generic algorithm doesn't care about the type of objects it is asked to processes. There are two approaches to generic collections and algorithms, parametric and polymorphic.
The Standard Template Library (STL) that accompanies C++ provides parametric collections and algorithms, while the Java Collections Framework provides polymorphic collections and algorithms.
In STL, the type of objects a collection stores is specified by a type argument at the time the collection is created. For example:
list<Account> accounts;
list<Customer> customers;
list<int> scores;
In Java, all collections store objects. Since all classes are subclasses of the Object class, then the exact type of object doesn't need to be specified. For example:
List stuff = new LinkedList();
stuff.add(new Customer());
stuff.add(new Account());
stuff.add(new Integer(42));
The only purpose of a collection is to store objects. The stored objects are independent of any collections that store them. For example, references to the same person object may be contained in several collections:
List employees = new LinkedList();
List customers = new LinkedList();
List suppliers = new LinkedList();
Person smith = new Person("Joe Smith");
employees.add(Smith);
customers.add(smith);
supliers.add(smith);
An assembly might use a collection to store its components, but the assembly has a purpose beyond storing components. A component belongs to at most one assembly.
class GUI {
private List components = new
LinkedList();
public void addComponent() {
components.add(new GUIComponent());
}
// etc.
}
An Abstract Data Type (ADT) specifies the operations that can be performed on a data type. Typically, an ADT includes specification for constructors and selectors for a type. An implementation of an ADT includes at least one representation for members of the type as well as implementations for the required operations.
The concept of an ADT comes very close to the concept of an interface. An implementation of an ADT doesn't have to be a class. In other words, ADTs are appropriate for non-object-oriented languages, like C. An ADT might also include axioms that specify the relationships between the operations. For example, an ADT for a Scalar type might specify two special scalars 0 and 1 plus four operations, +, *, -, and / satisfying the axioms:
a + b = b + a
a * b = b * a
a + (b + c) = (a + b) + c
a * (b * c) = (a * b) * c
a * (b + c) = (a * b) + (a * c)
a – b = 0 if and only if b = 0 - a
a + b = a if and only if b = 0
a * b = 1 if and only if b = 1
a * b = a if and only if b = 1/a
etc.
Clearly, any field (Rationals, Reals, Complex numbers) can implement this ADT.
The problem with axioms is that they are difficult to enforce. How does a compiler verify that a particular implementation of an ADT satisfies all of these axioms?