Container (abstract data type)

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. 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.

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). Modern programming languages offer various approaches to help solve the problem:

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.