In computer science, a set is an abstract data type that can store unique values, without any particular order.
(Subtypes and subsets may be modeled by refinement types, and quotient sets may be replaced by setoids.)
For example, an abstract heap can be viewed as a set structure with a min(S) operation that returns the element of smallest value.
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.
A simple implementation is to use a 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.
A Bloom map implements a set probabilistically, using a very compact representation but risking a small chance of false positives on queries.
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.
Typical operations on bags: In 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).