You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 44.223.0.0/16 has been blocked by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 23:54, 31 July 2024. Your current IP address is 44.223.80.188.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
This IP address range has been globally blocked.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

This block affects editing on all Wikimedia wikis.
The IP address or range 44.223.0.0/16 has been globally blocked by ‪AntiCompositeNumber‬ for the following reason(s):

Open proxy/Webhost: Visit the FAQ if you are affected

This block will expire on 13:57, 18 November 2024. Your current IP address is 44.223.80.188.

Even while globally blocked, you will usually still be able to edit pages on Meta-Wiki.

If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

Other useful links: Global blocks · Help:I have been blocked

You can view and copy the source of this page:

((Short description|Abstract data type for storing unique values))
((more citations needed|date=October 2011))
In [[computer science]], a '''set''' is an [[abstract data type]] that can store unique values, without any particular [[sequence|order]]. It is a computer implementation of the [[mathematics|mathematical]] concept of a [[finite set]]. Unlike most other [[collection (abstract data type)|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.

==Type theory==
In [[type theory]], sets are generally identified with their [[indicator function]] (characteristic function): accordingly, a set of values of type <math>A</math> may be denoted by <math>2^{A}</math> or <math>\mathcal{P}(A)</math>. (Subtypes and subsets may be modeled by [[refinement type]]s, and [[quotient set]]s may be replaced by [[setoid]]s.) The characteristic function <math>F</math> of a set <math>S</math> is defined as:
:<math>F(x) = \begin{cases}
  1, & \mbox{if } x \in S \\
  0,  & \mbox{if } x \not \in S
\end{cases}
</math>

In theory, many other abstract data structures can be viewed as set structures with additional operations and/or additional [[axiom]]s imposed on the standard operations. For example, an abstract [[Heap data structure|heap]] can be viewed as a set structure with a <code>min(''S'')</code> operation that returns the element of smallest value.

==Operations==

=== Core set-theoretical operations ===
One may define the operations of the [[algebra of sets]]:
* <code>union(''S'',''T'')</code>: returns the [[union (set theory)|union]] of sets ''S'' and ''T''.
* <code>intersection(''S'',''T'')</code>: returns the [[intersection (set theory)|intersection]] of  sets ''S'' and ''T''.
* <code>difference(''S'',''T'')</code>: returns the [[difference (set theory)|difference]] of sets ''S'' and ''T''.
* <code>subset(''S'',''T'')</code>: a predicate that tests whether the set ''S'' is a [[subset]] of set ''T''.

=== Static sets ===
Typical operations that may be provided by a static set structure ''S'' are:
* <code>is_element_of(''x'',''S'')</code>: checks whether the value ''x'' is in the set ''S''.
* <code>is_empty(''S'')</code>: checks whether the set ''S'' is empty.
* <code>size(''S'')</code> or <code>[[cardinality]](''S'')</code>: returns the number of elements in ''S''.
* <code>[[iterator|iterate]](''S'')</code>: returns a function that returns one more value of ''S'' at each call, in some arbitrary order.
* <code>enumerate(''S'')</code>: returns a list containing the elements of ''S'' in some arbitrary order.
* <code>build(''x''<sub>1</sub>,''x''<sub>2</sub>,…,''x''<sub>''n''</sub>,)</code>: creates a set structure with values ''x''<sub>1</sub>,''x''<sub>2</sub>,...,''x''<sub>''n''</sub>.
* <code>create_from(''collection'')</code>: creates a new set structure containing all the elements of the given [[collection (abstract data type)|collection]] or all the elements returned by the given [[iterator]].

=== Dynamic sets ===
Dynamic set structures typically add:
* <code>create()</code>: creates a new, initially empty set structure.
** <code>create_with_capacity(''n'')</code>: creates a new set structure, initially empty but capable of holding up to ''n'' elements.
* <code>add(''S'',''x'')</code>: adds the element ''x'' to ''S'', if it is not present already.
* <code>remove(''S'', ''x'')</code>: removes the element ''x'' from ''S'', if it is present.
* <code>capacity(''S'')</code>: 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.

=== Additional operations ===
There are many other operations that can (in principle) be defined in terms of the above, such as:
* <code>pop(''S'')</code>: returns an arbitrary element of ''S'', deleting it from ''S''.<ref>Python: [https://docs.python.org/3/library/stdtypes.html#set.pop pop()]</ref>
* <code>pick(''S'')</code>: returns an arbitrary element of ''S''.<ref>''Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings,'' ed. Kai v. Luck, Heinz Marburger, [https://books.google.com/books?id=ymhoQ3y0vccC&q=pick&pg=PA76 p. 76]</ref><ref>Python [http://bugs.python.org/issue7212 Issue7212]: Retrieve an arbitrary element from a set without removing it; see [http://bugs.python.org/issue7212#msg106593 msg106593] regarding standard name</ref><ref>Ruby [https://bugs.ruby-lang.org/issues/4553 Feature #4553]: Add Set#pick and Set#pop</ref> Functionally, the mutator <code>pop</code> can be interpreted as the pair of selectors <code>(pick, rest),</code> where <code>rest</code> returns the set consisting of all elements except for the arbitrary element.<ref>''Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning,'' [[Ute Schmid]], Springer, Aug 21, 2003, [https://books.google.com/books?id=p-Fy25LE4lMC&q=pick&pg=PA240 p. 240]</ref> Can be interpreted in terms of <code>iterate</code>.((efn|For example, in Python <code>pick</code> can be implemented on a derived class of the built-in <code>set</code> as follows:
<syntaxhighlight lang="python">
class Set(set):
    def pick(self):
        return next(iter(self))</syntaxhighlight>))
* <code>[[Map (higher-order function)|map]](''F'',''S'')</code>: returns the set of distinct values resulting from applying function ''F'' to each element of ''S''.
* <code>[[Filter (higher-order function)|filter]](''P'',''S'')</code>: returns the subset containing all elements of ''S'' that satisfy a given [[predicate (mathematical logic)|predicate]] ''P''.
* <code>[[Fold (higher-order function)|fold]](''A''<sub>0</sub>,''F'',''S'')</code>: returns the value ''A''<sub>|''S''|</sub> after applying <code>''A''<sub>i+1</sub> := ''F''(''A<sub>i</sub>'', ''e'')</code> for each element ''e'' of ''S,'' for some binary operation ''F.'' ''F'' must be associative and commutative for this to be well-defined.
* <code>clear(''S'')</code>: delete all elements of ''S''.
* <code>equal(''S''<sub>1</sub>', ''S''<sub>2</sub>')</code>: checks whether the two given sets are equal (i.e. contain all and only the same elements).
* <code>hash(''S'')</code>: returns a [[hash value]] for the static set ''S'' such that if <code>equal(''S''<sub>1</sub>, ''S''<sub>2</sub>)</code> then <code>hash(''S<sub>1</sub>'') = hash(''S<sub>2</sub>'')</code>

Other operations can be defined for sets with elements of a special type:
* <code>sum(''S'')</code>: returns the sum of all elements of ''S'' for some definition of "sum". For example, over integers or reals, it may be defined as <code>fold(0, add, ''S'')</code>.
* <code>collapse(''S'')</code>: given a set of sets, return the union.<ref>''Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10,'' ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, [https://books.google.com/books?id=LkvQYL23v1sC&q=collapse&pg=PA38 p. 38]</ref> For example, <code>collapse(((1}, {2, 3))) == {1, 2, 3}</code>. May be considered a kind of <code>sum</code>.
* <code>flatten(''S'')</code>: 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 – like <code>collapse,</code> but allow atoms. This can be done a single time, or recursively flattening to obtain a set of only atomic elements.<ref>Ruby: [http://www.ruby-doc.org/stdlib-2.1.2/libdoc/set/rdoc/Set.html#method-i-flatten flatten()]</ref> For example, <code>flatten({1, {2, 3))) == {1, 2, 3}</code>.
* <code>nearest(''S'',''x'')</code>: returns the element of ''S'' that is closest in value to ''x'' (by some [[Metric (mathematics)|metric]]).
* <code>min(''S'')</code>, <code>max(''S'')</code>: returns the minimum/maximum element of ''S''.

==Implementations==
Sets can be implemented using various [[data structure]]s, 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 <code>nearest</code> or <code>union</code>.  Implementations described as "general use" typically strive to optimize the <code>element_of</code>, <code>add</code>, and <code>delete</code> operations. A simple implementation is to use a [[List (abstract data type)|list]], 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 are ''O''(''n''), as they require scanning the entire list.((efn|Element insertion can be done in ''O''(1) time by simply inserting at an end, but if one avoids duplicates this takes ''O''(''n'') time.)) Sets are often instead implemented using more efficient data structures, particularly various flavors of [[tree (data structure)|trees]], [[trie]]s, or [[hash 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 array]]s) – in this case in which the value of each key-value pair has the [[unit type]] or a sentinel value (like 1) – namely, a [[self-balancing binary search tree]] for sorted sets((Definition needed|date=November 2020)) (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<ref>((Citation |title=Sorted Linear Hash Table |first1=Thomas |last1=Wang |url=http://www.concentric.net/~Ttwang/tech/sorthash.htm |year=1997 |url-status=dead |archive-url=https://web.archive.org/web/20060112115812/http://www.concentric.net/~Ttwang/tech/sorthash.htm |archive-date=2006-01-12 ))</ref> may 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 common [[programming idiom]] in [[Perl]] that converts an array to a hash whose values are the sentinel value 1, for use as a set, is:
<syntaxhighlight lang="perl">
my %elements = map { $_ => 1 } @elements;
</syntaxhighlight>

Other popular methods include [[Array data structure|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 (<code>pop</code>, <code>clear</code>, and <code>add</code>), but specialized algorithms may yield lower asymptotic time bounds.  If sets are implemented as sorted lists, for example, the naive algorithm for <code>union(''S'',''T'')</code> will take time proportional to the length ''m'' of ''S'' times the length ''n'' of ''T''; whereas a variant of the [[Merge algorithm|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 algorithm|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 programming language|Pascal]]; many languages now include it, whether in the core language or in a [[standard library]].
* In [[C++]], the [[Standard Template Library]] (STL) provides the <code>[[set (C++)|set]]</code> template class, which is typically implemented using a binary search tree (e.g. [[red–black tree]]); [[Silicon Graphics International|SGI]]'s STL also provides the <code>hash_set</code> template class, which implements a set using a hash table. [[C++11]] has support for the <code>[[unordered_set (C++)|unordered_set]]</code> template 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.
* The [[Rust (programming language)|Rust]] standard library provides the generic <code>[https://doc.rust-lang.org/std/collections/struct.HashSet.html HashSet]</code> and <code>[https://doc.rust-lang.org/std/collections/struct.BTreeSet.html BTreeSet]</code> types.
* [[Java (programming language)|Java]] offers the ((Javadoc:SE|java/util|Set)) [[Interface (computer science)|interface]] to support sets (with the ((Javadoc:SE|java/util|HashSet)) class implementing it using a hash table), and the ((Javadoc:SE|java/util|SortedSet)) sub-interface to support sorted sets (with the ((Javadoc:SE|java/util|TreeSet)) class implementing it using a binary search tree).
* [[Apple Inc.|Apple]]'s [[Foundation Kit|Foundation framework]] (part of [[Cocoa (API)|Cocoa]]) provides the [[Objective-C]] classes <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/ NSSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/ NSMutableSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSCountedSet_Class/ NSCountedSet]</code>, <code>[https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSOrderedSet_Class/Reference/Reference.html NSOrderedSet]</code>, and <code>[https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSMutableOrderedSet_Class/Reference/Reference.html NSMutableOrderedSet]</code>. The [[CoreFoundation]] APIs provide the [https://developer.apple.com/documentation/CoreFoundation/Reference/CFSetRef/ CFSet] and [https://developer.apple.com/documentation/CoreFoundation/Reference/CFMutableSetRef/ CFMutableSet] types for use in [[C (programming language)|C]].
* [[Python (programming language)|Python]] has built-in [https://docs.python.org/library/stdtypes.html#set-types-set-frozenset <code>set</code> and <code>frozenset</code> types] since 2.4, and since Python 3.0 and 2.7, supports non-empty set literals using a curly-bracket syntax, e.g.: <code>{x, y, z}</code>; empty sets must be created using <code>set()</code>, because Python uses <code>{}</code> to represent the empty dictionary.
* The [[.NET Framework]] provides the generic <code>[http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet]</code> and <code>[http://msdn.microsoft.com/en-us/library/dd412070.aspx SortedSet]</code> classes that implement the generic <code>[http://msdn.microsoft.com/en-us/library/dd412081.aspx ISet]</code> interface.
* [[Smalltalk]]'s class library includes <code>Set</code> and <code>IdentitySet</code>, using equality and identity for inclusion test respectively. Many dialects provide variations for compressed storage (<code>NumberSet</code>, <code>CharacterSet</code>), for ordering (<code>OrderedSet</code>, <code>SortedSet</code>, etc.) or for [[weak reference]]s (<code>WeakIdentitySet</code>).
* [[Ruby (programming language)|Ruby]]'s standard library includes a <code>[http://ruby-doc.org/stdlib/libdoc/set/rdoc/index.html set]</code> module which contains <code>Set</code> and <code>SortedSet</code> classes that implement sets using hash tables, the latter allowing iteration in sorted order.
* [[OCaml]]'s standard library contains a <code>Set</code> module, which implements a functional set data structure using binary search trees.
* The [[Glasgow Haskell Compiler|GHC]] implementation of [[Haskell (programming language)|Haskell]] provides a <code>[https://hackage.haskell.org/package/containers/docs/Data-Set.html Data.Set]</code> module, which implements immutable sets using binary search trees.<ref>Stephen Adams, [http://www.swiss.ai.mit.edu/~adams/BB "''Efficient sets: a balancing act''"], Journal of Functional Programming 3(4):553-562, October 1993.  Retrieved on 2015-03-11.</ref>
* The [[Tcl]] [[Tcllib]] package provides a set module which implements a set data structure based upon TCL lists.
* The [[Swift (programming language)|Swift]] standard library contains a <code>Set</code> type, since Swift 1.2.
* [[JavaScript]] introduced <code>[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set Set]</code> as a standard built-in object with the ECMAScript 2015<ref>((Cite web|url=http://www.ecma-international.org/ecma-262/6.0/#sec-set-objects|title=ECMAScript 2015 Language Specification – ECMA-262 6th Edition|website=www.ecma-international.org|language=en-GB|access-date=2017-07-11))</ref> standard.  
* [[Erlang (programming language)|Erlang]]'s standard library has a <code>[http://erlang.org/doc/man/sets.html sets]</code> module.
* [[Clojure]] has literal syntax for hashed sets, and also implements sorted sets.
* [[LabVIEW]] has native support for sets, from version 2019.
* [[Ada (programming language)|Ada]] provides the <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-8.html Ada.Containers.Hashed_Sets]</code> and <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-9.html Ada.Containers.Ordered_Sets]</code> packages.
 
As noted in the previous section, in languages which do not directly support sets but do support [[associative array]]s, 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|Multiset))

A generalization of the notion of a set is that of a '''[[multiset]]''' or '''bag''', which is similar to a set but allows repeated ("equal") values (duplicates). This is used in two distinct senses: either equal values are considered ''identical,'' and are simply counted, or equal values are considered ''equivalent,'' 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 some [[equivalence relation]] but 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 number]]s), 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++'s [[Standard Template Library]] implements both sorted and unsorted multisets. It provides the <code>[[Multiset (C++)|multiset]]</code> class for the sorted multiset, as a kind of [[Associative containers (C++)|associative container]], which implements this multiset using a [[self-balancing binary search tree]]. It provides the <code>unordered_multiset</code> class for the unsorted multiset, as a kind of [[Unordered associative containers (C++)|unordered associative container]], which implements this multiset using a [[hash table]]. The unsorted multiset is standard as of [[C++11]]; previously SGI's STL provides the <code>hash_multiset</code> class, which was copied and eventually standardized.
* For [[Java (programming language)|Java]], third-party libraries provide multiset functionality:
** [[Apache Commons]] Collections provides the <code>[https://web.archive.org/web/20150109083430/https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Bag.html Bag]</code> and <code>SortedBag</code> interfaces, with implementing classes like <code>HashBag</code> and <code>TreeBag</code>.
** [[Google Guava]] provides the <code>[https://google.github.io/guava/releases/20.0/api/docs/com/google/common/collect/Multiset.html Multiset]</code> interface, with implementing classes like <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/HashMultiset.html HashMultiset]</code> and <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/TreeMultiset.html TreeMultiset]</code>.
* Apple provides the <code>[https://developer.apple.com/documentation/foundation/nscountedset NSCountedSet]</code> class as part of [[Cocoa (API)|Cocoa]], and the <code>[https://developer.apple.com/documentation/corefoundation/cfbag-s1l CFBag]</code> and <code>[https://developer.apple.com/documentation/corefoundation/cfmutablebag-rqn CFMutableBag]</code> types as part of [[CoreFoundation]].
* [[Python (programming language)|Python's]] standard library includes <code>[https://docs.python.org/library/collections.html#collections.Counter collections.Counter]</code>, which is similar to a multiset.
* [[Smalltalk]] includes the <code>Bag</code> class, 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 an [[associative array]] mapping the values to their integer multiplicities (this will not be able to distinguish between equal elements at all).

Typical operations on bags:
* <code>contains(''B'', ''x'')</code>: checks whether the element ''x'' is present (at least once) in the bag ''B''
* <code>is_sub_bag(''B''<sub>1</sub>, ''B''<sub>2</sub>)</code>: checks whether each element in the bag ''B''<sub>1</sub> occurs in ''B''<sub>1</sub> no more often than it occurs in the bag ''B''<sub>2</sub>; sometimes denoted as ''B''<sub>1</sub> ⊑ ''B''<sub>2</sub>.
* <code>count(''B'', ''x'')</code>: returns the number of times that the element ''x'' occurs in the bag ''B''; sometimes denoted as ''B'' # ''x''.
* <code>scaled_by(''B'', ''n'')</code>: given a [[natural number]] ''n'', returns a bag which contains the same elements as the bag ''B'', except that every element that occurs ''m'' times in ''B'' occurs ''n'' * ''m'' times in the resulting bag; sometimes denoted as ''n'' ⊗ ''B''.
* <code>union(''B''<sub>1</sub>, ''B''<sub>2</sub>)</code>: returns a bag containing just those values that occur in either the bag ''B''<sub>1</sub> or the bag ''B''<sub>2</sub>, except that the number of times a value ''x'' occurs in the resulting bag is equal to (''B''<sub>1</sub> # x) + (''B''<sub>2</sub> # x); sometimes denoted as ''B''<sub>1</sub> ⊎ ''B''<sub>2</sub>.

===Multisets in SQL===
In [[Relational database management system|relational 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 a [[candidate key]]).

[[SQL]] allows the selection of rows from a relational table: this operation will in general yield a multiset, unless the keyword <code>DISTINCT</code> is used to force the rows to be all different, or the selection includes the primary (or a candidate) key.

In [[SQL#Standardization history|ANSI SQL]] the <code>MULTISET</code> keyword can be used to transform a subquery into a collection expression:

<syntaxhighlight lang="sql">SELECT expression1, expression2... FROM table_name...</syntaxhighlight>

is a general select that can be used as ''[[subquery expression]]'' of another more general query, while

<syntaxhighlight lang="sql">MULTISET(SELECT expression1, expression2... FROM table_name...)</syntaxhighlight>

transforms the subquery into a ''[[collection expression]]'' that can be used in another query, or in assignment to a column of appropriate collection type.

==See also==
*[[Bloom filter]]
*[[Disjoint set (data structure)|Disjoint set]]
*[[Set (mathematics)]]

==Notes==
((Notelist))

==References==
((Reflist))

((Data types))
((Data structures))

[[Category:Data types]]
[[Category:Composite data types]]
[[Category:Abstract data types]]
[[Category:Articles with example Python (programming language) code]]

Pages transcluded onto the current version of this page (help):

Set (abstract data type) (edit)
Template:Ambox (view source) (template editor protected)
Template:Category handler (view source) (protected)
Template:Citation (view source) (protected)
Template:Cite web (view source) (protected)
Template:Data structures (edit)
Template:Data types (edit)
Template:Definition needed (view source) (semi-protected)
Template:Delink (view source) (protected)
Template:Efn (view source) (template editor protected)
Template:Find sources mainspace (view source) (template editor protected)
Template:Fix (view source) (protected)
Template:Fix/category (view source) (protected)
Template:Hlist/styles.css (view source) (protected)
Template:Javadoc:SE (edit)
Template:Javadoc:SE/Home URL (edit)
Template:Main (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:More citations needed (view source) (template editor protected)
Template:Navbox (view source) (template editor protected)
Template:Notelist (view source) (template editor protected)
Template:Pagetype (view source) (protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SDcat (view source) (protected)
Template:Short description (view source) (protected)
Template:Short description/lowercasecheck (view source) (protected)
Module:Arguments (view source) (protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Delink (view source) (protected)
Module:Disambiguation/templates (view source) (protected)
Module:Find sources (view source) (template editor protected)
Module:Find sources/config (view source) (template editor protected)
Module:Find sources/links (view source) (template editor protected)
Module:Find sources/templates/Find sources mainspace (view source) (template editor protected)
Module:Format link (view source) (template editor protected)
Module:Hatnote (view source) (template editor protected)
Module:Hatnote/styles.css (view source) (template editor protected)
Module:Hatnote list (view source) (template editor protected)
Module:Labelled list hatnote (view source) (template editor protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Navbar (view source) (protected)
Module:Navbar/configuration (view source) (protected)
Module:Navbar/styles.css (view source) (protected)
Module:Navbox (view source) (template editor protected)
Module:Navbox/configuration (view source) (template editor protected)
Module:Navbox/styles.css (view source) (template editor protected)
Module:Pagetype (view source) (protected)
Module:Pagetype/config (view source) (protected)
Module:Pagetype/disambiguation (view source) (protected)
Module:Pagetype/rfd (view source) (template editor protected)
Module:Pagetype/setindex (view source) (protected)
Module:Pagetype/softredirect (view source) (protected)
Module:SDcat (view source) (protected)
Module:String (view source) (protected)
Module:Unsubst (view source) (protected)
Module:Wikitext Parsing (view source) (protected)
Module:Yesno (view source) (protected)

Return to Set (abstract data type).

Retrieved from "https://en.wikipedia.org/wiki/Set_(abstract_data_type)"