Container (abstract data type)

In computer science, a container is a class or a data structure^[1]^[2] whose instances are collections of other objects. In other words, they store objects in an organized way that follows specific access rules.

The size of the container depends on the number of objects (elements) it contains. Underlying (inherited) implementations of various container types may vary in size, complexity and type of language, but in many cases they provide flexibility in choosing the right implementation for any given scenario.

Container data structures are commonly used in many types of programming languages.

Function and properties

Containers can be characterized by the following three properties:

access, that is the way of accessing the objects of the container. In the case of arrays, access is done with the array index. In the case of stacks, access is done according to the LIFO (last in, first out) order and in the case of queues it is done according to the FIFO (first in, first out) order;
storage, that is the way of storing the objects of the container;
traversal, that is the way of traversing the objects of the container.

Container classes are expected to implement CRUD-like methods to do the following:

create an empty container (constructor);
insert objects into the container;
delete objects from the container;
delete all the objects in the container (clear);
access the objects in the container;
access the number of objects in the container (count).

Containers are sometimes implemented in conjunction with iterators.

Types

Containers may be classified as either single-value containers or associative containers.

Single-value containers store each object independently. Objects may be accessed directly, by a language loop construct (e.g. for loop) or with an iterator.

An associative container uses an associative array, map, or dictionary, composed of key-value pairs, such that each key appears at most once in the container. The key is used to find the value, the object, if it is stored in the container. Associative containers are used in programming languages as class templates.

Container abstract data types include:

FIFO queues
LIFO stacks
Priority queues
Lookup tables (LUTs)
Key-associated data structures
- Sets, containing and indexing objects by value or by specific property;
- Maps, associating to each key a "value" for lookup

Common data structures used to implement these abstract types include:

Arrays and their derivatives
Linked lists
Binary search trees (BSTs), particularly self-balancing BSTs
Hash tables

Graphic containers

Widget toolkits also use containers, which are special widgets to group other widgets, such as windows, panels. Apart from their graphical properties, they have the same type of behavior as container classes, as they keep a list of their child widgets, and allow adding, removing, or retrieving widgets among their children.

In statically-typed languages

Container abstractions can be written in virtually any programming language, regardless of its type system.^[3]^: 273 However, in strongly-typed object-oriented programming languages it may be somewhat complicated for a developer to write reusable homogeneous containers.

Because of differences in element types this results in a tedious process of writing and keeping a collection of containers for every elemental type.^[3]^{: 274–276}

Many elemental types (e.g. integers or floating numbers) are inherently incompatible with each other because of the memory size they occupy and their semantic meaning and therefore require different containers (unless of course, they are mutually compatible or convertible).^[3]^{: 274–276} Modern programming languages offer various approaches to help solve the problem:^[3]^{: 274–281}

Universal basic type: A type that is universally assignable by any other (e.g. root Object class).
Downcasting;
Class substitution: Previous three approaches above are used for weakly typed languages; these usually imply inheritance and polymorphism shared by types.
Union types (C/C++ language): Permits storing types of different data sizes; it is hard to ensure which type is stored in a union upon retrieval however and should be carefully followed.
Type conversion
Templates or Generics: Ensures reusability and type safety; may be thought as a reverse inheritance. However, this approach may require implementing a template specialization which is reputedly a time-consuming process given that types differ in their methods.^[3]^: 281

References

^ Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. US National Institute of Standards and Technology.15 December 2004. Accessed 4 Oct 2011.
^ Entry data structure in the Encyclopædia Britannica (2009) Online entry Accessed 4 Oct 2011.
^ ^a ^b ^c ^d ^e Budd, Timothy (1997). An introduction to object-oriented programming (2nd ed.). Reading, Mass.: Addison-Wesley. ISBN 0-201-82419-1. OCLC 34788238.

External links

Container Data Structure Declaration and Initialization

[1] Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. US National Institute of Standards and Technology.15 December 2004. Accessed 4 Oct 2011.

[2] Entry data structure in the Encyclopædia Britannica (2009) Online entry Accessed 4 Oct 2011.

[Budd1997-3] Budd, Timothy (1997). An introduction to object-oriented programming (2nd ed.). Reading, Mass.: Addison-Wesley. ISBN 0-201-82419-1. OCLC 34788238.

[1]

[2]

[3]

v t e Data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

v t e Data types
Uninterpreted	Bit Byte Trit Tryte Word Bit array
Numeric	Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Reduced precision Minifloat Half precision bfloat16 Single precision Double precision Quadruple precision Octuple precision Extended precision Long double Integer signedness Interval Rational
Pointer	Address physical virtual Reference
Text	Character String null-terminated
Composite	Algebraic data type generalized Array Associative array Class Dependent Equality Inductive Intersection List Object metaobject Option type Product Record or Struct Refinement Set Union tagged
Other	Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Strongly typed identifier Top type Type class Empty type Unit type Void
Related topics	Abstract data type Boxing Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Interface Subtyping Type constructor Type conversion Type system Type theory Variable