Set (abstract data type)

The data structure quantity, also called set is an unordered collection of elements of a specific data type, of which a maximum of one copy each contain. It is the finite set modeled in mathematics. It is mostly for reasons of efficiency makes sense, constant amounts otherwise to represent a dynamic quantities.

Among the available operations usually include:

• Generating a set of elements
• Test whether an element is already included.
• Testing whether a set is a subset of another.
• Formation of intersection, union, difference, etc.
• Enumerating the elements of the set in any order

Dynamic sets support the following function:

• Adding and removing individual elements.

Depending on the application, more or less in each of the above operations can be implemented.

Implementation

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

Be treated when only subsets of a known amount (for example, an interval of the natural numbers ), a representation of a field of bits is also possible. This represents a one at point n, the element N is contained in the set. The usual set operations can then be well implemented as binary operations. Inclusion tests can then be carried out in constant time.

When a binary code is available for the members of a set, sets can also be represented as a binary decision diagram. The amount is represented as a Boolean function that results for encoding one of its elements, for all other codes is zero. This can be useful for certain very large, but simply structured amounts as may occur for example when model checking.

Some programming languages ​​, such as Modula -2 or Oberon have integrated quantities in the language scope, this data type is then typically declared with " SET" or " BITSET ". However, many programming languages ​​have no elementary data type for sets in the definition of scope, and because in these cases often set operations are allowed integer data types, the assignment compatibility is significantly restricted, which can easily lead to program errors. Therefore, it is generally much better and safer to implement library functions for set operations and use (see, for example, in Java the class " bitset ").