Article in other languages:
In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set.
Some set data structures are designed for static sets that do not change with time, and allow only query operations — 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/or deletion of elements from the set.
A set can be implemented in many ways. For example, one can use a list, ignoring the order of the elements and taking care to avoid repeated values. Sets are often implemented using various flavors of trees, tries, hash tables, and more.
A set can be seen, and implemented, as a (partial) associative array, in which the value of each key-value pair is null (i.e. has the unit type).
In type theory, sets are generally identified with their indicator function: accordingly, a set of values of type A may be denoted by 2A or 
. (Subtypes and subsets may be modeled by refinement types, and quotient sets may be replaced by setoids.)
Contents |
Operations
Typical operations that may be provided by a static set structure S are
element_of(x,S): checks whether the value x is in the set S.empty(S): checks whether the set S is empty.size(S): returns the number of elements in S.enumerate(S): yields the elements of S in some arbitrary order.pick(S): returns an arbitrary element of S.build(x1,x2,…,xn,): creates a set structure with values x1,x2,…,xn.
The enumerate operation may return a list of all the elements, or an iterator, a procedure object that returns one more value of S at each call.
Dynamic set structures typically add:
create(n): creates a new set structure, initially empty but capable of holding up to n elements.add(S,x): adds the element x to S, if it is not there already.delete(S,x): removes the element x from S, if it is there.capacity(S): returns the maximum number of values that S can hold.
Some set structures may allow only some of these operations. The cost of each operation will depend on the implementation, and possibly also on the particular values stored in the set, and the order in which they are inserted.
There are many other operations that can (in principle) be defined in terms of the above, such as:
pop(S): returns an arbitrary element of S, deleting it from S.find(S, P): returns an element of S that satisfies a given predicate P.clear(S): delete all elements of S.
In particular, one may define the Boolean operations of set theory:
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.
Other operations can be defined for sets with elements of a special type:
sum(S): returns the sum of all elements of S (for some definition of "sum").nearest(S,x): returns the element of S that is closest in value to x (by some criterion).
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.
Implementations
Sets can be implemented using various data structures, which provide different time and space trade-offs for various operations. Some implementations are designed to improve the efficiency of very specialized operations, such as nearest or union. Implementations described as "general use" typically strive to optimize the element_of, add, and delete operation.
Sets are commonly implemented in the same way as associative arrays, namely, a self-balancing binary search tree for sorted sets (which has O(log n) for most operations), or a hash table for unsorted sets (which has O(1) average-case, but O(n) worst-case, for most operations). A sorted linear hash table[1] may be used to provide deterministically ordered sets.
Other popular methods include arrays. In particular a subset of the integers 1..n can be implemented efficiently as an n-bit bit array, which also support very efficient union and intersection operations. A Bloom map implements a set probabilistically, using a very compact representation but risking a small chance of false positives on queries.
The Boolean set operations can be implemented in terms of more elementary operations (pop, clear, and add), but specialized algorithms may yield lower asymptotic time bounds. If sets are implemented as sorted lists, for example, the naive algorithm for union(S,T) will take code proportional to the length m of S times the length n of T; whereas a variant of the list merging algorithm will do the job in time proportional to m+n. Moreover, there are specialized set data structures (such as the union-find data structure) that are optimized for one or more of these operations, at the expense of others.
Language support
One of the earliest languages to support sets was Pascal; many languages now include it, whether in the core language or in a standard library. The Java programming language offers the Set interface to support sets (with the HashSet class implementing it using a hash table), and the SortedSet sub-interface to support sorted sets (with the TreeSet class implementing it using a binary search tree). In C++, STL provides the set template class, which implements a sorted set using a binary search tree; and SGI's STL provides the hash_set class, which implements a set using a hash table. Apple's Foundation framework (part of Cocoa) provides the Objective-C classes NSSet, NSMutableSet, and NSCountedSet. Python has a built-in set type, and since Python 3.0, supports non-empty set literals using the curly-bracket syntax, e.g.: { x, y, z }. .NET Framework implements a set in the generic HashSet class. Ruby's library contains a Set class, which implements a set using a hash table. OCaml's standard library contains a Set module, which implements a functional set data structure using binary search trees. The GHC implementation of Haskell provides a Data.Set module, which implements a functional set data structure using binary search trees.
As noted in the previous section, in languages which do not directly support sets but do support associative arrays, sets can be emulated using associative arrays, by using the elements as keys, and using a dummy value as the values, which are ignored.
Multiset
A variation of the set is the multiset or bag, which is the same as a set data structure, but allows repeated values. Formally, a multiset can be thought of as an associative array that maps unique elements to positive integers, indicating the mulplicity of the element, although actual implementation may vary. C++'s Standard Template Library provides the "multiset" class for the sorted multiset, and SGI's STL provides the "hash_multiset" class, which implements a multiset using a hash table. For Java, third-party libraries provide multiset functionality: Apache Commons Collections provides the Bag and SortedBag interfaces, with implementing classes like HashBag and TreeBag, analogous to similarly-named Set implementations; Google Collections provides the Multiset interface, with implementing classes like HashMultiset and TreeMultiset analogous to similarly-named Set implementations.
See also
- Bloom filter
- Disjoint set
- Standard Template Library - contains a C++ set class
References
- ^ Wang, Thomas (1997), Sorted Linear Hash Table, http://www.concentric.net/~Ttwang/tech/sorthash.htm
|
|||||||||||||||||||||||
|
||||||||||||||||||||
Questions for article: