Set (abstract data type)

Incomputer science,asetis anabstract data typethat can store unique values, without any particularorder.It is a computer implementation of themathematicalconcept of afinite set.Unlike most othercollectiontypes, 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 forstaticorfrozen setsthat 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, calleddynamicormutable sets,allow also the insertion and deletion of elements from the set.

Amultisetis a special kind of set in which an element can appear multiple times in the set.

Type theory

Intype theory,sets are generally identified with theirindicator function(characteristic function): accordingly, a set of values of type$A$may be denoted by$2^{A}$or${\mathcal {P}}(A)$.(Subtypes and subsets may be modeled byrefinement types,andquotient setsmay be replaced bysetoids.) The characteristic function$F$of a set$S$is defined as:

$F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}$

In theory, many other abstract data structures can be viewed as set structures with additional operations and/or additionalaxiomsimposed on the standard operations. For example, an abstractheapcan be viewed as a set structure with amin(S)operation that returns the element of smallest value.

Operations

Core set-theoretical operations

One may define the operations of thealgebra of sets:

• union(S,T):returns theunionof setsSandT.
• intersection(S,T):returns theintersectionof setsSandT.
• difference(S,T):returns thedifferenceof setsSandT.
• subset(S,T):a predicate that tests whether the setSis asubsetof setT.

Static sets

Typical operations that may be provided by a static set structureSare:

• is_element_of(x,S):checks whether the valuexis in the setS.
• is_empty(S):checks whether the setSis empty.
• size(S)orcardinality(S):returns the number of elements inS.
• iterate(S):returns a function that returns one more value ofSat each call, in some arbitrary order.
• enumerate(S):returns a list containing the elements ofSin some arbitrary order.
• build(x1,x2,…,xn,):creates a set structure with valuesx₁,x₂,...,x_n.
• create_from(collection):creates a new set structure containing all the elements of the givencollectionor all the elements returned by the giveniterator.

Dynamic sets

Dynamic set structures typically add:

• create():creates a new, initially empty set structure.
  • create_with_capacity(n):creates a new set structure, initially empty but capable of holding up tonelements.
• add(S,x):adds the elementxtoS,if it is not present already.
• remove(S,x):removes the elementxfromS,if it is present.
• capacity(S):returns the maximum number of values thatScan 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.

Additional operations

There are many other operations that can (in principle) be defined in terms of the above, such as:

• pop(S):returns an arbitrary element ofS,deleting it fromS.
• pick(S):returns an arbitrary element ofS.Functionally, the mutatorpopcan be interpreted as the pair of selectors(pick, rest),whererestreturns the set consisting of all elements except for the arbitrary element.Can be interpreted in terms ofiterate.
• map(F,S):returns the set of distinct values resulting from applying functionFto each element ofS.
• filter(P,S):returns the subset containing all elements ofSthat satisfy a givenpredicateP.
• fold(A0,F,S):returns the valueA_|S|after applyingAi+1:=F(Ai,e)for each elementeofS,for some binary operationF.Fmust be associative and commutative for this to be well-defined.
• clear(S):delete all elements ofS.
• equal(S1',S2'):checks whether the two given sets are equal (i.e. contain all and only the same elements).
• hash(S):returns ahash valuefor the static setSsuch that ifequal(S1,S2)thenhash(S1) = hash(S2)

Other operations can be defined for sets with elements of a special type:

• sum(S):returns the sum of all elements ofSfor some definition of "sum". For example, over integers or reals, it may be defined asfold(0, add,S).
• collapse(S):given a set of sets, return the union.For example,collapse({{1}, {2, 3}}) == {1, 2, 3}.May be considered a kind ofsum.
• flatten(S):given a set consisting of sets and atomic elements (elements that are not sets), returns a set whose elements are the atomic elements of the original top-level set or elements of the sets it contains. In other words, remove a level of nesting – likecollapse,but allow atoms. This can be done a single time, or recursively flattening to obtain a set of only atomic elements.For example,flatten({1, {2, 3}}) == {1, 2, 3}.
• nearest(S,x):returns the element ofSthat is closest in value tox(by somemetric).
• min(S),max(S):returns the minimum/maximum element ofS.

Implementations

Sets can be implemented using variousdata 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 asnearestorunion.Implementations described as "general use" typically strive to optimize theelement_of,add,anddeleteoperations. A simple implementation is to use alist,ignoring the order of the elements and taking care to avoid repeated values. This is simple but inefficient, as operations like set membership or element deletion areO(n), as they require scanning the entire list.Sets are often instead implemented using more efficient data structures, particularly various flavors oftrees,tries,orhash tables.

As sets can be interpreted as a kind of map (by the indicator function), sets are commonly implemented in the same way as (partial) maps (associative arrays) – in this case in which the value of each key-value pair has theunit typeor a sentinel value (like 1) – namely, aself-balancing binary search treefor sorted sets(which has O(log n) for most operations), or ahash tablefor unsorted sets (which has O(1) average-case, but O(n) worst-case, for most operations). A sorted linear hash tablemay be used to provide deterministically ordered sets.

Further, in languages that support maps but not sets, sets can be implemented in terms of maps. For example, a commonprogramming idiominPerlthat converts an array to a hash whose values are the sentinel value 1, for use as a set, is:

my%elements=map{$_=>1}@elements;

Other popular methods includearrays.In particular a subset of the integers 1..ncan be implemented efficiently as ann-bitbit array,which also support very efficient union and intersection operations. ABloom mapimplements 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,andadd), but specialized algorithms may yield lower asymptotic time bounds. If sets are implemented as sorted lists, for example, the naive algorithm forunion(S,T)will take time proportional to the lengthmofStimes the lengthnofT;whereas a variant of thelist merging algorithmwill do the job in time proportional tom+n.Moreover, there are specialized set data structures (such as theunion-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 wasPascal;many languages now include it, whether in the core language or in astandard library.

• InC++,theStandard Template Library(STL) provides thesettemplate class, which is typically implemented using a binary search tree (e.g.red–black tree);SGI's STL also provides thehash_settemplate class, which implements a set using a hash table.C++11has support for theunordered_settemplate class, which is implemented using a hash table. In sets, the elements themselves are the keys, in contrast to sequenced containers, where elements are accessed using their (relative or absolute) position. Set elements must have a strict weak ordering.
• TheRuststandard library provides the genericHashSetandBTreeSettypes.
• Javaoffers theSetinterfaceto support sets (with theHashSetclass implementing it using a hash table), and theSortedSetsub-interface to support sorted sets (with theTreeSetclass implementing it using a binary search tree).
• Apple'sFoundation framework(part ofCocoa) provides theObjective-CclassesNSSet,NSMutableSet,NSCountedSet,NSOrderedSet,andNSMutableOrderedSet.TheCoreFoundationAPIs provide theCFSetandCFMutableSettypes for use inC.
• Pythonhas built-insetandfrozensettypessince 2.4, and since Python 3.0 and 2.7, supports non-empty set literals using a curly-bracket syntax, e.g.:{x, y, z};empty sets must be created usingset(),because Python uses{}to represent the empty dictionary.
• The.NET Frameworkprovides the genericHashSetandSortedSetclasses that implement the genericISetinterface.
• Smalltalk's class library includesSetandIdentitySet,using equality and identity for inclusion test respectively. Many dialects provide variations for compressed storage (NumberSet,CharacterSet), for ordering (OrderedSet,SortedSet,etc.) or forweak references(WeakIdentitySet).
• Ruby's standard library includes asetmodule which containsSetandSortedSetclasses that implement sets using hash tables, the latter allowing iteration in sorted order.
• OCaml's standard library contains aSetmodule, which implements a functional set data structure using binary search trees.
• TheGHCimplementation ofHaskellprovides aData.Setmodule, which implements immutable sets using binary search trees.
• TheTclTcllibpackage provides a set module which implements a set data structure based upon TCL lists.
• TheSwiftstandard library contains aSettype, since Swift 1.2.
• JavaScriptintroducedSetas a standard built-in object with the ECMAScript 2015standard.
• Erlang's standard library has asetsmodule.
• Clojurehas literal syntax for hashed sets, and also implements sorted sets.
• LabVIEWhas native support for sets, from version 2019.
• Adaprovides theAda.Containers.Hashed_SetsandAda.Containers.Ordered_Setspackages.

As noted in the previous section, in languages which do not directly support sets but do supportassociative 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

Main article:Multiset

A generalization of the notion of a set is that of amultisetorbag,which is similar to a set but allows repeated ( "equal" ) values (duplicates). This is used in two distinct senses: either equal values are consideredidentical,and are simply counted, or equal values are consideredequivalent,and are stored as distinct items. For example, given a list of people (by name) and ages (in years), one could construct a multiset of ages, which simply counts the number of people of a given age. Alternatively, one can construct a multiset of people, where two people are considered equivalent if their ages are the same (but may be different people and have different names), in which case each pair (name, age) must be stored, and selecting on a given age gives all the people of a given age.

Formally, it is possible for objects in computer science to be considered "equal" under someequivalence relationbut still distinct under another relation. Some types of multiset implementations will store distinct equal objects as separate items in the data structure; while others will collapse it down to one version (the first one encountered) and keep a positive integer count of the multiplicity of the element.

As with sets, multisets can naturally be implemented using hash table or trees, which yield different performance characteristics.

The set of all bags over type T is given by the expression bag T. If by multiset one considers equal items identical and simply counts them, then a multiset can be interpreted as a function from the input domain to the non-negative integers (natural numbers), generalizing the identification of a set with its indicator function. In some cases a multiset in this counting sense may be generalized to allow negative values, as in Python.

• C++'sStandard Template Libraryimplements both sorted and unsorted multisets. It provides themultisetclass for the sorted multiset, as a kind ofassociative container,which implements this multiset using aself-balancing binary search tree.It provides theunordered_multisetclass for the unsorted multiset, as a kind ofunordered associative container,which implements this multiset using ahash table.The unsorted multiset is standard as ofC++11;previously SGI's STL provides thehash_multisetclass, which was copied and eventually standardized.
• ForJava,third-party libraries provide multiset functionality:
  • Apache CommonsCollections provides theBagandSortedBaginterfaces, with implementing classes likeHashBagandTreeBag.
  • Google Guavaprovides theMultisetinterface, with implementing classes likeHashMultisetandTreeMultiset.
• Apple provides theNSCountedSetclass as part ofCocoa,and theCFBagandCFMutableBagtypes as part ofCoreFoundation.
• Python'sstandard library includescollections.Counter,which is similar to a multiset.
• Smalltalkincludes theBagclass, which can be instantiated to use either identity or equality as predicate for inclusion test.

Where a multiset data structure is not available, a workaround is to use a regular set, but override the equality predicate of its items to always return "not equal" on distinct objects (however, such will still not be able to store multiple occurrences of the same object) or use anassociative arraymapping the values to their integer multiplicities (this will not be able to distinguish between equal elements at all).

Typical operations on bags:

• contains(B,x):checks whether the elementxis present (at least once) in the bagB
• is_sub_bag(B1,B2):checks whether each element in the bagB₁occurs inB₁no more often than it occurs in the bagB₂;sometimes denoted asB₁⊑B₂.
• count(B,x):returns the number of times that the elementxoccurs in the bagB;sometimes denoted asB#x.
• scaled_by(B,n):given anatural numbern,returns a bag which contains the same elements as the bagB,except that every element that occursmtimes inBoccursn*mtimes in the resulting bag; sometimes denoted asn⊗B.
• union(B1,B2):returns a bag containing just those values that occur in either the bagB₁or the bagB₂,except that the number of times a valuexoccurs in the resulting bag is equal to (B₁# x) + (B₂# x); sometimes denoted asB₁⊎B₂.

Multisets in SQL

Inrelational databases,a table can be a (mathematical) set or a multiset, depending on the presence of unicity constraints on some columns (which turns it into acandidate key).

SQLallows the selection of rows from a relational table: this operation will in general yield a multiset, unless the keywordDISTINCTis used to force the rows to be all different, or the selection includes the primary (or a candidate) key.

InANSI SQLtheMULTISETkeyword can be used to transform a subquery into a collection expression:

SELECTexpression1,expression2...FROMtable_name...

is a general select that can be used assubquery expressionof another more general query, while

MULTISET(SELECTexpression1,expression2...FROMtable_name...)

transforms the subquery into acollection expressionthat can be used in another query, or in assignment to a column of appropriate collection type.

See also

• Bloom filter
• Disjoint set
• Set (mathematics)