Container (abstract data type): Difference between revisions
Copyedit. Date formats Correct caps in section header. |
m Fixed header Reference based containers => References based containers Dated {{Cleanup}}. (Build J3) |
||
| Line 1: | Line 1: | ||
{{Merge|Collection (abstract data type)|discuss=Talk:Container (abstract data type)#Merging "Container" and "Collection"|date=December 2011}} |
{{Merge|Collection (abstract data type)|discuss=Talk:Container (abstract data type)#Merging "Container" and "Collection"|date=December 2011}} |
||
{{For|the abstract notion of containers in [[type theory]]|Container (type theory)}} |
{{For|the abstract notion of containers in [[type theory]]|Container (type theory)}} |
||
{{Cleanup|reason=text is clunky}} |
{{Cleanup|reason=text is clunky|date=March 2012}} |
||
In [[computer science]], a '''container''' is a [[Class (computer science)|class]], a [[data structure]]<ref>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.</ref><ref>Entry ''data structure'' in the [[Encyclopædia Britannica]] (2009) [http://www.britannica.com/EBchecked/topic/152190/data-structure Online entry] Accessed on Oct 04, 2011.</ref>, or an [[abstract data type]] (ADT) whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules. The size of the container depends on the number of the objects (elements) it contains.The underlying implementation of various types of containers may vary in space and time complexity allowing for flexibility in choosing the right implementation for a given scenario. |
In [[computer science]], a '''container''' is a [[Class (computer science)|class]], a [[data structure]]<ref>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.</ref><ref>Entry ''data structure'' in the [[Encyclopædia Britannica]] (2009) [http://www.britannica.com/EBchecked/topic/152190/data-structure Online entry] Accessed on Oct 04, 2011.</ref>, or an [[abstract data type]] (ADT) whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules. The size of the container depends on the number of the objects (elements) it contains.The underlying implementation of various types of containers may vary in space and time complexity allowing for flexibility in choosing the right implementation for a given scenario. |
||
| Line 29: | Line 29: | ||
store copies of objects.If we access an object, an object returns a copy of it. If external object is changed after it has been inserted in container will not affect the content of the container. |
store copies of objects.If we access an object, an object returns a copy of it. If external object is changed after it has been inserted in container will not affect the content of the container. |
||
=== |
===References based containers=== |
||
store pointers and references to the object. If we access an object, an object returns reference to it.If external object is changed after it has been inserted in container, affect the content of the container. |
store pointers and references to the object. If we access an object, an object returns reference to it.If external object is changed after it has been inserted in container, affect the content of the container. |
||
Revision as of 00:32, 14 March 2012
 | It has been suggested that this article be merged with Collection (abstract data type). (Discuss) Proposed since December 2011. |
 | This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: text is clunky. (March 2012) |
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 are used for storing objects in an organized way following specific access rules. The size of the container depends on the number of the objects (elements) it contains.The underlying implementation of various types of containers may vary in space and time complexity allowing for flexibility in choosing the right implementation for a given scenario.
Overview
Container can be studied under three points of views.
- Access : It means accessing the container elements. In case of arrays accessing is done using array index. For stacks, access of elements is done using LIFO (Last In First Out)[3] and in queues it is done using FIFO (First In First Out)[4][3].
- Storage : It includes storing of items of containers. Some containers are finite containers and some are infinite containers.
- Traversal : It includes how the item can be traversed.
Container classes are expected to implement methods to do the following:
- create a new empty container (constructor),
- 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
There are two types of containers:
- Value based containers
- Reference based containers
Value based containers
store copies of objects.If we access an object, an object returns a copy of it. If external object is changed after it has been inserted in container will not affect the content of the container.
References based containers
store pointers and references to the object. If we access an object, an object returns reference to it.If external object is changed after it has been inserted in container, affect the content of the container.
Examples of containers
Containers are divided in the Standard Template Library into associative containers and standard sequence containers. Besides this two types, so-called container adaptors exist. Data structures that implement containers include arrays, lists, maps, queues, sets, stacks, tables, trees, and vectors.
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.
Containers in object oriented programming
In object oriented programming, we define a container class as class capable of storing other objects.These classes usually implement some kind of data structure such as map, set, stacks etc.The size of the collection of objects is adjusted automatically in a container class.
Implementations
![[icon]](/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | This section needs expansion. You can help by adding to it. (May 2007) |
- Java: Java collections framework (JCF)
- C++: C++ Standard Library (SC++L) or the obsolete Standard Template Library (STL)
- .NET: System.Collections (MSDN)
- ActionScript3: AS3Commons Collections Framework
- Objective-C: part of the Foundation Kit
See also
- List of data structures
- Standard Template Library#Containers
- Collection (computing)
- Stack data structure
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.
- ^ a b LIFO(investopedia.com) Cite error: The named reference "investopedia" was defined multiple times with different content (see the help page).
- ^ FIFO(businessdictionary.com)
External links