Struct BTree

pub struct BTree<K: BTreeKey, V, A: Allocator = Global> { /* private fields */ }

An ordered map based on a B+ Tree.

This is similar to the standard library’s BTreeMap but differs in several ways:

• Lookups and insertions are 2-4x faster than BTreeMap.
• BTree can optionally be used as a multi-map and hold duplicate keys.
• Keys must be Copy and convertible to and from integers via the BTreeKey trait.
• The maximum integer value is reserved for internal use and cannot be used by keys.
• Elements in the tree are ordered by the integer value of the key instead of the Ord implementation of the keys.
• Cursor and CursorMut can be used to seek back-and-forth in the tree while inserting or removing elements.
• Iterators only support forward iteration.

The data structure design is based on the B- Tree by Sergey Slotin, but has been significantly extended.

Implementations

impl<K: BTreeKey, V, A: Allocator> BTree<K, V, A>

pub fn cursor(&self) -> Cursor<'_, K, V, A>

Returns a Cursor pointing at the first element of the tree.

pub fn cursor_at(&self, bound: Bound<K>) -> Cursor<'_, K, V, A>

Returns a Cursor pointing at the first element with key greater than bound.

pub fn cursor_mut(&mut self) -> CursorMut<'_, K, V, A>

Returns a CursorMut pointing at the first element of the tree.

pub fn cursor_mut_at(&mut self, bound: Bound<K>) -> CursorMut<'_, K, V, A>

Returns a CursorMut pointing at the first element with key greater than bound.

impl<K: BTreeKey, V, A: Allocator> BTree<K, V, A>

pub fn iter(&self) -> Iter<'_, K, V, A>

Gets an iterator over the entries of the map, sorted by key.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V, A>

Gets a mutable iterator over the entries of the map, sorted by key.

pub fn iter_from(&self, bound: Bound<K>) -> Iter<'_, K, V, A>

Gets an iterator over the entries of the map starting from the given bound.

pub fn iter_mut_from(&mut self, bound: Bound<K>) -> IterMut<'_, K, V, A>

Gets a mutable iterator over the entries of the map starting from the given bound.

pub fn keys(&self) -> Keys<'_, K, V, A>

Gets an iterator over the keys of the map, in sorted order.

pub fn values(&self) -> Values<'_, K, V, A>

Gets an iterator over the values of the map, in order by key.

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, A>

Gets a mutable iterator over the values of the map, in order by key.

pub fn range(&self, range: impl RangeBounds<K>) -> Range<'_, K, V, A>

Constructs an iterator over a sub-range of elements in the map.

Unlike BTreeMap, this is not a DoubleEndedIterator: it only allows forward iteration.

pub fn range_mut(&mut self, range: impl RangeBounds<K>) -> RangeMut<'_, K, V, A>

Constructs a mutable iterator over a sub-range of elements in the map.

Unlike BTreeMap, this is not a DoubleEndedIterator: it only allows forward iteration.

impl<K: BTreeKey, V> BTree<K, V, Global>

pub fn new() -> Self

Creates a new, empty BTree.

This requires an initial memory allocation on creation.

impl<K: BTreeKey, V, A: Allocator> BTree<K, V, A>

pub fn new_in(alloc: A) -> Self

Creates a new, empty BTree with the given allocator.

This requires an initial memory allocation on creation.

pub fn clear(&mut self)

Clears the map, removing all elements.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn get(&self, key: K) -> Option<&V>

Returns a reference to the value corresponding to the key.

pub fn get_mut(&mut self, key: K) -> Option<&mut V>

Returns a mutable reference to the value corresponding to the key.

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated, and the old value is returned.

pub fn insert_multi(&mut self, key: K, value: V)

Inserts a key-value pair into the map while allowing for multiple identical keys.

This allows the BTree to be used as a multi-map where each key can have multiple values. In this case BTree::get, BTree::get_mut and BTree::remove will only operate on one of the associated values (arbitrarily chosen).

pub fn remove(&mut self, key: K) -> Option<V>

Removes a key from the map, returning the value at the key if the key was previously in the map.

Trait Implementations

impl<K: BTreeKey, V: Clone, A: Allocator + Clone> Clone for BTree<K, V, A>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: BTreeKey, V, A: Default + Allocator> Default for BTree<K, V, A>

fn default() -> Self

Returns the “default value” for a type.

impl<K: BTreeKey, V, A: Allocator> Drop for BTree<K, V, A>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K: BTreeKey, V: Clone, A: Allocator> Extend<(K, &'a V)> for BTree<K, V, A>

fn extend<T: IntoIterator<Item = (K, &'a V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K: BTreeKey, V, A: Allocator> Extend<(K, V)> for BTree<K, V, A>

fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K: BTreeKey, V> FromIterator<(K, V)> for BTree<K, V>

fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self

Creates a value from an iterator.

impl<'a, K: BTreeKey, V, A: Allocator> IntoIterator for &'a BTree<K, V, A>

type Item = (K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K: BTreeKey, V, A: Allocator> IntoIterator for &'a mut BTree<K, V, A>

type Item = (K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: BTreeKey, V, A: Allocator> IntoIterator for BTree<K, V, A>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V, A>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.