Crate vec_collections

This crate provides collections (sets and maps) that wrap SmallVec.

Use cases

Small collections

It happens very frequently that you have collections that have on average just a very small number of elements. If you know the maximum size or even the maximum typical size in advance, you can use this crate to store such collections without allocations. For a larger number of elements, the underlying SmallVec will allocate the elements on the heap as a single allocation.

Read-heavy collections

Another very frequent pattern is that you have a possibly large collection that is being created once and then used readonly for a long time. E.g. lookup tables. In these cases, ease of adding individual new elements is less important than compact in-memory representation and lookup performance. This crate provides succinct collections that have only a very small constant overhead over the contents of the collections.

Performance

Performance for bulk creation as well as lookup is better than BTreeMap/BTreeSet and comparable with HashMap/HashSet for types with a cheap Ord instance, like primitive types, and small to medium sizes. Performance for insertion or removal of individual elements to/from large collections is bad, however. This is not the intended use case.

Collections overview

VecSet

Provides a set backed by a SmallVec of elements.

VecMap

Provides a map backed by a SmallVec of key value pairs.

RadixTree

A RadixTree that comes in different flavours.

TotalVecSet

A VecSet with an additional flag so it can support negation. This way it is possible to represent e.g. the set of all u64 except 1.

TotalVecMap

A VecMap with an additional default value, so lookup is a total function.

Unsafe

The in place operations use unsafe code. If that is a problem for you, let me know and I can hide them behind a feature.

Macros

• vecmap
  Macro to create a vecmap
• vecset
  Macro to create a vecset

Structs

• VecMap
  A map backed by a SmallVec of key value pairs.
• VecSet
  A set backed by a SmallVec of elements.
• VecSetIter
  An interator that is guaranteed to be sorted by item

Enums

• OuterJoinArg

Traits

• AbstractVecMap
  An abstract vec map
• AbstractVecSet
  An abstract vec set
• Array
  Types that can be used as the backing store for a SmallVec
• SortedIterator
  set operations for iterators where the items are sorted according to the natural order
• SortedPairIterator
  relational operations for iterators of pairs where the items are sorted according to the key

Functions

• sort_dedup
  Sort and dedup an interator I into a collection R.
• sort_dedup_by_key
  Sort and dedup an interator I into a collection R, using a key fn.

Type Aliases

• VecMap1
  Type alias for a VecMap with up to 1 mapping with inline storage.
• VecSet2
  Type alias for a VecSet with up to 2 elements with inline storage.