NIST

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
where S is a set and u and v are elements.

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

  1. isEmpty(new()) = true
  2. 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

(C++ and Pascal). Darius Bacon's functional implementation (Scheme).
Go to the Dictionary of Algorithms and Data Structures home page.

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

Entry modified 11 January 2005.
HTML page formatted Mon Sep 11 09:46:07 2006.

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. 11 January 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/set.html

to NIST home page