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.
The predicate isEmpty(S) may be defined with the following additional axioms.
Generalization (I am a kind of ...)
bag, abstract data type.
Specialization (... is a kind of me.)
poset suggested by Norman T. Thornton 25 January 2016.
See also intersection, union, complement, difference, list, set cover.
Note: Sets may be implemented with an array of bits. A set that is many ranges may be efficiently implemented as an inversion list.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 1 October 2019.
HTML page formatted Tue Oct 1 16:35:30 2019.
Cite this as:
Patrick Rodgers and Paul E. Black, "set", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 1 October 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/set.html