Amount (data structure)

from Wikipedia, the free encyclopedia

The data structure set , also known as a set , is an unordered collection of elements of a certain data type , each of which contains a maximum of one copy. It is modeled on the finite set in mathematics. For reasons of efficiency, it usually makes sense to represent constant quantities differently than dynamic quantities.

The available operations usually include:

  • Create a set from the elements
  • Check whether an element is already included.
  • Checking whether a set is a subset of another.
  • Formation of intersection, union, difference, etc.
  • Enumerate the elements of the set in any order

Dynamic quantities also support the following function:

  • Adding and removing individual elements.

Depending on the application, more or less of the operations mentioned can be implemented.

Implementation

Dynamic sets are usually implemented with data structures such as hash tables or balanced search trees .

If only subsets of a known set are dealt with (e.g. an interval of natural numbers), it can also be represented as an array of bits . For example, a one in place n represents that element n is included in the set. The usual set operations can then be implemented well as binary operations. Inclusion tests can then be carried out in constant time.

If binary coding is available for the elements of a set, sets can also be represented as a binary decision diagram . The set is represented as a Boolean function that results in one for the coding of its elements and zero for all other codings. This can be useful for certain very large, but simply structured quantities, such as those that can occur in model checking .

Some programming languages, such as Modula-2 , Oberon or Python , amounts have integrated the language scope, this type of data typically then "SET" or "BITSET" declared will. However, many programming languages ​​do not have an elementary data type for sets in the scope of their definition, and since set operations with integer data types are often permitted in these cases, assignment compatibility is considerably restricted, which can easily lead to program errors. It is therefore generally much better and safer to implement and use library functions for set operations (see for example the "Bitset" class in Java ).

Individual evidence

  1. ↑ G. Hachtel, F. Somenzi: Logic Synthesis and Verification Algorithms , 1996, p. 219.

literature