Container (abstract data type)

"Container (computer science)" redirects here. 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 (inherited) implementations of various container types may vary in size and complexity, and provide flexibility in choosing the right implementation for any given scenario.

Overview

Containers can be looked at in three ways:

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

Single value and associative containers

Containers can be divided into two groups.

Single value containers

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

Associative containers

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.

Graphic containers

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

.NET: System.Collections (MSDN)
ActionScript3: AS3Commons Collections Framework
C++: C++ Standard Library (SC++L) or the obsolete Standard Template Library (STL)
- 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.
Java: Java collections framework (JCF)
Objective-C: part of the Foundation Kit
PL/SQL Collections^[3]
Python: has built in containers list, dict, tuple & set and can be further extended by the collections module
Scala Mutable and Immutable Collections in the packages scala.collection.mutable and scala.collection.immutable

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 on Oct 04, 2011.
↑ Entry data structure in the Encyclopædia Britannica (2009) Online entry Accessed on Oct 04, 2011.
↑ "PL/SQL Collections and Records". Retrieved 2013-04-20.

External links

Container Data Structure Declaration and Initialization
Container data structures
Python SortedContainers module A fast implementation of sorted list, sorted dict, and sorted set data types in Python.

Data structures

Types	Collection Container

Abstract	Associative array Multimap 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 array

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

Data types

Uninterpreted	Bit Byte Trit Tryte Word Bit array

Numeric	Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Double precision Extended precision Half precision Long double Minifloat Octuple precision Quadruple precision Single precision Integer signedness Interval Rational

Text	Character String null-terminated

Pointer	Address physical virtual Reference

Composite	Algebraic data type generalized Array Associative array Class Dependent Equality Inductive List Object metaobject Option type Product Record Set Union tagged

Other	Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void

Related topics	Abstract data type Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Protocol interface Subtyping Type constructor Type conversion Type system

See also platform-dependent and independent units of information

This article is issued from Wikipedia - version of the 9/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.