Ensemble (informatique)

In computer science, a set is an abstract data type that can store unique values, without any particular order. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set. Some set data structures are designed for static or frozen sets that do not change after they are constructed. Static sets allow only query operations on their elements — such as checking whether a given value is in the set, or enumerating the values in some arbitrary order. Other variants, called dynamic or mutable sets, allow also the insertion and deletion of elements from the set. A multiset is a special kind of set in which an element can appear multiple times in the set. In type theory, sets are generally identified with their indicator function (characteristic function): accordingly, a set of values of type may be denoted by or . (Subtypes and subsets may be modeled by refinement types, and quotient sets may be replaced by setoids.) The characteristic function of a set is defined as: In theory, many other abstract data structures can be viewed as set structures with additional operations and/or additional axioms imposed on the standard operations. For example, an abstract heap can be viewed as a set structure with a min(S) operation that returns the element of smallest value. One may define the operations of the algebra of sets: union(S,T): returns the union of sets S and T. intersection(S,T): returns the intersection of sets S and T. difference(S,T): returns the difference of sets S and T. subset(S,T): a predicate that tests whether the set S is a subset of set T. Typical operations that may be provided by a static set structure S are: is_element_of(x,S): checks whether the value x is in the set S. is_empty(S): checks whether the set S is empty. size(S) or cardinality(S): returns the number of elements in S. iterate(S): returns a function that returns one more value of S at each call, in some arbitrary order.