This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: text is clunky(March 2012) (Learn how and when to remove this template message) |

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.

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

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

Single-value containers store each object independently. Objects may be accessed directly 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:

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

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 computer science, an **array data structure**, or simply an **array**, is a data structure consisting of a collection of *elements*, each identified by at least one *array index* or *key*. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called one-dimensional array.

In computer science, an **abstract data type** (**ADT**) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a *user*, of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

In computer science, a **binary search tree** (**BST**), also called an **ordered** or **sorted binary tree**, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree. A binary tree is a type of data structure for storing data such as numbers in an organized way. Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables. The order of nodes in a BST means that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the binary logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables. Several variants of the binary search tree have been studied.

In computer science, a **double-ended queue** is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a **head-tail linked list**, though properly this refers to a specific data structure *implementation* of a deque.

**FIFO** – an acronym for **first in, first out** – in computing and in systems theory, is a method for organising the manipulation of a data structure – often, specifically a data buffer – where the oldest (first) entry, or 'head' of the queue, is processed first.

In computer science, a **heap** is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the **heap property**: in a *max heap*, for any given node C, if P is a parent node of C, then the *key* of P is greater than or equal to the key of C. In a *min heap*, the key of P is less than or equal to the key of C. The node at the "top" of the heap is called the *root* node.

In computer science, a **priority queue** is an abstract data type similar to a regular queue or stack data structure in which each element additionally has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of elements with the same priority is undefined.

In computer science, a **queue** is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services.

In computer science, an **associative array**, **map**, **symbol table**, or **dictionary** is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection.

The **Standard Template Library** (**STL**) is a software library for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called *algorithms*, *containers*, *functions*, and *iterators*.

In object-oriented programming, the **iterator pattern** is a design pattern in which an iterator is used to traverse a container and access the container's elements. The iterator pattern decouples algorithms from containers; in some cases, algorithms are necessarily container-specific and thus cannot be decoupled.

In computer programming, an **iterator** is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterator are fixed, iterators are often implemented in terms of the structures underlying a container implementation and are often tightly coupled to the container to enable the operational semantics of the iterator. An iterator performs traversal and also gives access to data elements in a container, but does not itself perform iteration. An iterator is behaviorally similar to a database cursor. Iterators date to the CLU programming language in 1974.

In computer science, a **list** or **sequence** is an abstract data type that represents a countable number of ordered values, where the same value may occur more than once. An instance of a list is a computer representation of the mathematical concept of a tuple or finite sequence; the (potentially) infinite analog of a list is a stream. Lists are a basic example of containers, as they contain other values. If the same value occurs multiple times, each occurrence is considered a distinct item.

In computer science, a **stack** is an abstract data type that serves as a collection of elements, with two main principal operations:

In computer science, **tree traversal** is a form of graph traversal and refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well.

The **Java collections framework** is a set of classes and interfaces that implement commonly reusable collection data structures.

In computer science, a **collection** or **container** is a grouping of some variable number of data items that have some shared significance to the problem being solved and need to be operated upon together in some controlled fashion. Generally, the data items will be of the same type or, in languages supporting inheritance, derived from some common ancestor type. A collection is a concept applicable to abstract data types, and does not prescribe a specific implementation as a concrete data structure, though often there is a conventional choice.

In computer science, a **purely functional data structure** is a data structure that can be implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongly) immutable. This restriction ensures the data structure possesses the advantages of immutable objects: (full) persistency, quick copy of objects, and thread safety. Efficient purely functional data structures may require the use of lazy evaluation and memoization.

This **Comparison of programming languages ** compares the features of associative array data structures or array-lookup processing for over 40 computer programming languages.

In object-oriented programming, **behavioral subtyping** is the principle that subclasses should satisfy the expectations of clients accessing subclass objects through references of superclass type, not just as regards syntactic safety but also as regards behavioral correctness. Specifically, properties that clients can prove using the specification of an object's presumed type should hold even though the object is actually a member of a subtype of that type.

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

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.