Container (data structure)
Encyclopedia
In computer science
, a container is a class
, a data structure
, 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.
1. 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) and in Queues it is done using FIFO (First In First Out).
2. Storage : It includes storing of items of containers. Some containers are finite containers and some are infinite containers.
3. Traversal : It includes how the item can be traversed.
Container classes are expected to implement methods to do the following:
Containers are sometimes implemented in conjunction with iterator
s.
into associative containers and standard sequence containers. Besides this two types, so-called container adaptors exist. Data structures that implement containers include arrays, lists, map
s, queues, set
s, stack
s, table
s, tree
s, and vectors.
s 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.
such as map
, set
, stacks etc.The size of the collection of objects is adjusted automatically in a container class.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a container is a class
Class (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
, a data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
, or an abstract data type
Abstract data type
In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
(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.1. 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) and in Queues it is done using FIFO (First In First Out).
2. Storage : It includes storing of items of containers. Some containers are finite containers and some are infinite containers.
3. 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 iterator
Iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container. Various types of iterators are often provided via a container's interface...
s.
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.Reference 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 LibraryStandard Template Library
The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
into associative containers and standard sequence containers. Besides this two types, so-called container adaptors exist. Data structures that implement containers include arrays, lists, map
Associative array
In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
s, queues, set
Set (computer science)
In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...
s, stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
s, table
Table (information)
A table is a means of arranging data in rows and columns.Production % of goalNorth 4087102%South 4093110% The use of tables is pervasive throughout all communication, research and data analysis. Tables appear in print media, handwritten notes, computer software, architectural...
s, tree
Tree (data structure)
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.Mathematically, it is an ordered directed tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at...
s, and vectors.
Graphic containers
Widget toolkitWidget toolkit
In computing, a widget toolkit, widget library, or GUI toolkit is a set of widgets for use in designing applications with graphical user interfaces...
s use special widgets
Widget (computing)
In computer programming, a widget is an element of a graphical user interface that displays an information arrangement changeable by the user, such as a window or a text box. The defining characteristic of a widget is to provide a single interaction point for the direct manipulation of a given...
also called Containers to group the other widgets together (windows
Window (computing)
In computing, a window is a visual area containing some kind of user interface. It usually has a rectangular shape that can overlap with the area of other windows...
, panels
Panel (computer software)
In graphical computer software a panel is :* A widget commonly packaged as part of a Widget toolkit for a graphical user interface. See toolbar and dialog box...
, ...). Apart from their graphical properties, they have the same type of behavior as container classes, as they keep a list of their child widgets
Widget (computing)
In computer programming, a widget is an element of a graphical user interface that displays an information arrangement changeable by the user, such as a window or a text box. The defining characteristic of a widget is to provide a single interaction point for the direct manipulation of a given...
, and allow to add, remove, or retrieve widgets
Widget (computing)
In computer programming, a widget is an element of a graphical user interface that displays an information arrangement changeable by the user, such as a window or a text box. The defining characteristic of a widget is to provide a single interaction point for the direct manipulation of a given...
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 structureData structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
such as map
Map
A map is a visual representation of an area—a symbolic depiction highlighting relationships between elements of that space such as objects, regions, and themes....
, set
Set
A set is a collection of well defined and distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematics. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from...
, stacks etc.The size of the collection of objects is adjusted automatically in a container class.
Implementations
- Java: Java collections frameworkJava collections frameworkThe Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures.Although it is a framework, it works in a manner of a library...
(JCF) - C++: C++ Standard LibraryC++ standard libraryIn C++, the C++ Standard Library is a collection of classes and functions, which are written in the core language and part of the C++ ISO Standard itself...
(SC++L) or the obsolete Standard Template LibraryStandard Template LibraryThe Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
(STL) - .NET: System.Collections (MSDN)
- ActionScript3: AS3Commons Collections Framework
- Objective-CObjective-CObjective-C is a reflective, object-oriented programming language that adds Smalltalk-style messaging to the C programming language.Today, it is used primarily on Apple's Mac OS X and iOS: two environments derived from the OpenStep standard, though not compliant with it...
: part of the Foundation KitFoundation KitThe Foundation Kit, or just Foundation for short, is an Objective-C framework in the OpenStep specification. It provides basic classes such as wrapper classes and data structure classes. This framework uses the prefix NS .-NSObject:...
See also
- List of data structures
- Standard Template Library#Containers
- Collection (computing)Collection (computing)In computer science, a collection 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...
- Stack data structureStack (data structure)In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...