# "SortedMultiset"(Data Structure) "SortedMultiset"

represents a multiset where the members are general expressions and are kept in a sorted order.

# Details  • A sorted multiset is useful for efficient insertion and removal as well as membership testing where the same element can appear more than once:
•  CreateDataStructure["SortedMultiset"] create a new empty "SortedMultiset" that uses canonical ordering CreateDataStructure["SortedMultiset",elems] create a new "SortedMultiset" with elements elems CreateDataStructure["SortedMultiset",elems,p] create a new "SortedMultiset" with specified elements and ordering function p Typed[x,"SortedMultiset"] give x the type "SortedMultiset"
• For a data structure of type "SortedMultiset", the following operations can be used:
•  ds["Cases",elem] returns members of the multiset that match elem time: O(log n) ds["Count", elem] returns the number of elements that match elem time: O(log n) ds["Elements"] return a list of the elements of ds time: O(n) ds["EmptyQ"] True, if ds has no members time: O(1) ds["Insert",x] add x to the multiset time: O(log n) ds["Length"] returns the number of members stored in ds time: O(1) ds["MemberQ",x] True, if x is a member of ds time: O(1) ds["Remove",x] remove x from ds; return True if x was actually an element time: O(1) ds["RemoveAll"] remove all the elements from ds time: O(n) ds["Visualization"] return a visualization of ds time: O(n)
• The following functions are also supported:
•  dsi===dsj True, if dsi equals dsj FullForm[ds] full form of ds Information[ds] information about ds InputForm[ds] input form of ds Normal[ds] convert ds to a normal expression

# Examples

open allclose all

## Basic Examples(3)

A new "HashSet" can be created with CreateDataStructure:

Insert into the set:

There is one element in the set:

Test if an expression is stored:

If an expression is not stored, False is returned:

Remove an element from the set. If something was actually removed, return True:

Now there are two elements in the set:

Return an expression version of ds:

Insert a number of elements:

A visualization of the data structure can be generated:

This shows how the data is sorted and contains multiple elements.

An ordering function can be given for a sorted multiset:

Insert two elements:

These elements are all equal according to the ordering function:

Remove an element:

## Scope(1)

### Information(1)

A new "SortedMultiset" can be created with CreateDataStructure:

Information about the data structure ds:

## Possible Issues(1)

### Set Membership(1)

If an ordering function is given, this is used to specify set membership:

This returns True because the ordering function only looks at the first element: