Container (data structure)

Container (data structure)

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.

Contents

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)[3] and in Queues it is done using FIFO (First In First Out)[4][3].

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

Types

There are two types of containers:

  1. Value based containers
  2. 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 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

See also

References

  1. ^ Paul E. Black (ed.), entry for data structure in Dictionary of Algorithms and Data Structures. U.S. 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)

External Links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • 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.[1][2] Different kinds of data structures are suited to different kinds of applications, and some are highly …   Wikipedia

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Stack (data structure) — In computer science, a stack is an abstract data type and data structure based on the principle of Last In First Out (LIFO) . Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the… …   Wikipedia

  • Container — may refer to: Items used to contain, store, and transport products, such as: Carton Bottle Can (disambiguation), several meanings Shipping containers include Crate Wooden box Intermodal container, aka Ship container or Cargo container Twenty foot …   Wikipedia

  • Multimap (data structure) — A multimap is a generalization of a map or associative array abstract data type in which more than one value may be associated with and returned for a given key. Both map and multimap are particular cases of containers (see for example C++… …   Wikipedia

  • Container ship — Two container ships pass in San Francisco Bay Class overview Name: Container ship Subclasses: (1) Geared or gearless …   Wikipedia

  • Container compression test — The container compression test measures the compressive strength of packages such as boxes, drums, and cans. It usually provides a plot of deformation vs compressive force. It is commonly used to evaluate shipping containers made of corrugated… …   Wikipedia

  • Map (C++ container) — The class std::map is a standard C++ container. It is a sorted associative array, which is a data structure which acts like a dynamic one dimensional array that associates values of one type with values of another type (the two types of values… …   Wikipedia

  • Abstract data type — In computing, an abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. Such a data type is abstract in the sense that it is independent of various concrete implementations. The… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”