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

- new() returns a set
- isIn(v, new()) = false
- isIn(v, add(v, S)) = true
- isIn(v, add(u, S)) = isIn(v , S) if v ≠ u
- remove(v, new()) = new()
- remove(v, add(v, S)) = remove(v, S)
- 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.

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

Go to the
Dictionary of Algorithms and Data
Structures home page.

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

Entry modified 2 September 2014.

HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:

Patrick Rodgers and Paul E. Black, "set", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/set.html