Crate numerical_multiset

This crate implements an ordered multiset of machine numbers.

Well, that sentence is quite a mouthful. Let’s break it down into more digestible chunks:

• Multiset: The NumericalMultiset container provided by this crate implements a generalization of the mathematical set, the multiset. Unlike a set, a multiset can conceptually hold multiple copies of a value. This is done by tracking how many occurences of each value are present.

• Ordered: Multiset implementations are usually based on associative containers, using distinct multiset elements as keys and integer occurence counts as values. A popular choice is hash maps, which do not provide any meaningful key ordering:

  • Any key insertion may change the order of keys that is exposed by iterators.
  • There is no way to find e.g. the smallest key without iterating over all key.

  In contrast, NumericalMultiset is based on an ordered associative container. This allows it to efficiently answer order-related queries, like in-order iteration over elements or extraction of the minimum/maximum element. The price to pay is that order-insenstive multiset operations, like item insertions and removals, will scale a little less well to larger sets of distinct values than in a hash-based implementation.

• Numbers: The multiset provided by this crate is not general-purpose, but specialized for machine number types (u32, f32…) and newtypes thereof. These types are all Copy, which lets us provide a simplified value-based API, that may also result in slightly improved runtime performance in some scenarios.

Structs

IntoIter

An owning iterator over the contents of an NumericalMultiset, sorted by value.

Iter

An iterator over the contents of an NumericalMultiset, sorted by value.

NumericalMultiset

An ordered multiset of machine numbers.