In many programming languages, a data structure used to contain zero,
one, or more objects. In the Java programming language, for example,
collections are provided through the Collections Framework API in the
java.util package; in C++, they are provided by the
Standard Template Library.
The choice of a suitable collection data structure should be done
with regard to the use of that collection, and usually the choice can
make a noticeable difference in application performance. To this end,
collection frameworks typically provide a variety of data structures;
a set for example is a container that does not support duplicates,
nor imposes a particular sort order. A multiset or "bag" allows
duplication, while algorithms that require searching are
often most efficient using sorted structures. The linked list allows
rapid insertion and deletion of elements, while a flatter structure
such as an array allows random access in constant time, but is
typically more expensive for insertion and deletion. More advanced
collections include the map, hash table, or tree, in which the
data structure not only includes the objects, but also represents some
relationship between them.
Both the STL and the Java Collections Framework also embody common
algorithms, such as sorting and searching, that can be applied to
collections in an abstract fachion without knowledge of the underlying
implementation. There is commonly a requirement for conversion to
and from legacy data structures such as arrays. The simplest algorithm
is the notion of an iterator, which provides a mechanism to return the
elements of the collection, one by one, for use in a loop.