set

(data structure)

Definition: An unordered collection of values where each value occurs at most once. A group of elements with three properties: (1) all elements belong to a universe, (2) either each element is a member of the set or it is not, and (3) the elements are unordered.

Formal Definition: As an abstract data type, a set has a single query function, isIn(v, S), which tells whether an element is a member of the set or not, and two modifier functions, add(v, S) and remove(v, S). These may be defined with axiomatic semantics as follows.

1. new() returns a set
2. isIn(v, new()) = false
3. isIn(v, add(v, S)) = true
4. isIn(v, add(u, S)) = isIn(v , S) if v ≠ u
5. remove(v, new()) = new()
6. remove(v, add(v, S)) = remove(v, S)
7. remove(v, add(u, S)) = add(u, remove(v, S)) if v ≠ u

The predicate isEmpty(S) may be defined with the following additional axioms.

8. isEmpty(new()) = true
9. isEmpty(add(v, S)) = false

Generalization (I am a kind of ...)
bag, abstract data type.

See also intersection, union, complement, difference, list, set cover.

Authors: PR,PEB

Implementation

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 22 February 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Patrick Rodgers and Paul E. Black, "set", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 22 February 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/set.html