Multi Set

A DataStructure in which elements can occur a nonnegative integer number of times. Also called a "bag".

A multiset x is characterised by a "count" operation, so that "x count y" is the number of times y occurs in x. There is no other structure; multisets are unordered.

Not necessarily true. The C++ library type multi_set<T> does require that its elements be ordered (by default it invokes operator < on the element type T; you can provide your own comparison FunctorObject if you want.

That's because multi_set<T> is an implementation of a multiset. Implementations of a DataStructure can impose structure that is not present in the underlying concept (as an early example, the implementation of sets in SetlLanguage was also ordered).

Elements are stored in sorted order (not sure how equal elements are handled); and traversal of the container is guaranteed to visit elements in order. By comparison, the STL type hash_multiset<T> (not part of the C++ standard library but part of the STL itself) does not sort its elements; traversal of a hash_multiset is not done in any particular (useful) order.

Both, however, are MultiSets.

Both are MultiSet implementations.

Like a set, the mathematical concept of a multiset is:

immutable
extensional -- two multisets are the same iff they have identical counts for any element
well-founded -- no multiset can directly or indirectly contain itself. (More precisely: if a system of multisets is viewed as a DirectedGraph in which x points to y iff x count y > 0, then it is a DirectedAcyclicGraph with no infinite chains.)