Container (abstract data type)

From Wikipedia, the free encyclopedia
  (Redirected from Container (data structure))
Jump to: navigation, search
For the abstract notion of containers in type theory, see Container (type theory).

In computer science, a container is a class, a data structure,[1][2] or an abstract data type (ADT) 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 implementation of various container types may vary in space and time complexity, which provides flexibility in choosing the right implementation for a given scenario.

Overview[edit]

Containers can be looked at in three ways:

  • Access : Accessing the container elements. In the case of arrays, accessing is done with the array index. For stacks, access of elements is done using LIFO (Last In First Out) [3] (alternative name FILO (First In Last Out) and in queues it is done using FIFO (First In First Out)).[3][4]
  • Storage : Storage includes storing items in containers. Some containers are finite and some are infinite.
  • Traversal : This describes how the item can be traversed.

Container classes are expected to implement methods to do the following:

  • create a new empty container,
  • report the number of objects it stores (size),
  • delete all the objects in the container (clear),
  • insert new objects into the container,
  • remove objects from it,
  • provide access to the stored objects.

Containers are sometimes implemented in conjunction with iterators.

Types[edit]

Containers can be divided into two groups:

  1. Value based containers
  2. Reference based containers

Value based containers[edit]

Value based containers store copies of objects. If we access an object, the object returns a copy of it. If an external object changes after it has been inserted in the container, it does not affect the container's content.

Reference based containers[edit]

Reference based containers store pointers or references to the object. If we access an object, the object returns a reference to it. If an external object is changed after it has been inserted in the container, it affects the content of the container.

Single or associative[edit]

A container may be:

  1. Single value
  2. Associative

Single value containers[edit]

Each object is stored independently in the container and it is accessed directly or with an iterator.

Associative containers[edit]

An associative array, map, or dictionary is a container 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.

Examples of containers[edit]

Containers are divided in the Standard Template Library into associative containers and standard sequence containers. Besides these two types, so-called container adaptors exist. Data structures that are implemented by containers include arrays, lists, maps, queues, sets, stacks, tables, trees, and vectors.

Graphic containers[edit]

Widget toolkits use special widgets also called Containers to group the other widgets together (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 to add, remove, or retrieve widgets amongst their children.

Implementations[edit]

See also[edit]

References[edit]

  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 on Oct 04, 2011.
  2. ^ Entry data structure in the Encyclopædia Britannica (2009) Online entry Accessed on Oct 04, 2011.
  3. ^ a b LIFO(investopedia.com)
  4. ^ FIFO(businessdictionary.com)
  5. ^ "PL/SQL Collections and Records". Retrieved 2013-04-20. 

External links[edit]