Expand description
Safe, fallible, embedded-friendly ordered map.
Fallible APIs
TryFrom
isn’t implemented because it would collide with the blanket implementation.
See this open GitHub issue from 2018,
this is a known Rust limitation that should be fixed via specialization in the future.
Attribution Note
The majority of API examples and descriptions are adapted or directly copied from the standard library’s BTreeMap
.
The goal is to offer embedded developers familiar, ergonomic APIs on resource constrained systems that otherwise don’t get the luxury of dynamic collections.
Implementations
sourceimpl<K: Ord + Default, V: Default, const N: usize> SgMap<K, V, N>
impl<K: Ord + Default, V: Default, const N: usize> SgMap<K, V, N>
sourcepub fn new() -> Self
pub fn new() -> Self
Makes a new, empty SgMap
.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
sourcepub fn set_rebal_param(
&mut self,
alpha_num: f32,
alpha_denom: f32
) -> Result<(), SgError>
pub fn set_rebal_param(
&mut self,
alpha_num: f32,
alpha_denom: f32
) -> Result<(), SgError>
The original scapegoat tree paper’s alpha, a
, can be chosen in the range 0.5 <= a < 1.0
.
a
tunes how “aggressively” the data structure self-balances.
It controls the trade-off between total rebuild time and maximum height guarantees.
-
As
a
approaches0.5
, the tree will rebalance more often. Ths means slower insertions, but faster lookups and deletions.- An
a
equal to0.5
means a tree that always maintains a perfect balance (e.g.“complete” binary tree, at all times).
- An
-
As
a
approaches1.0
, the tree will rebalance less often. This means quicker insertions, but slower lookups and deletions.- If
a
reached1.0
, it’d mean a tree that never rebalances.
- If
Returns Err
if 0.5 <= alpha_num / alpha_denom < 1.0
isn’t true
(invalid a
, out of range).
Examples
use scapegoat::SgMap;
let mut map: SgMap<isize, isize, 10> = SgMap::new();
// Set 2/3, e.g. `a = 0.666...` (it's default value).
assert!(map.set_rebal_param(2.0, 3.0).is_ok());
sourcepub fn rebal_param(&self) -> (f32, f32)
pub fn rebal_param(&self) -> (f32, f32)
Get the current rebalance parameter, alpha, as a tuple of (alpha_numerator, alpha_denominator)
.
See the corresponding setter method for more details.
Examples
use scapegoat::SgMap;
let mut map: SgMap<isize, isize, 10> = SgMap::new();
// Set 2/3, e.g. `a = 0.666...` (it's default value).
assert!(map.set_rebal_param(2.0, 3.0).is_ok());
// Get the currently set value
assert_eq!(map.rebal_param(), (2.0, 3.0));
sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
Total capacity, e.g. maximum number of map pairs.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<usize, &str, 10>::new();
assert!(map.capacity() == 10);
sourcepub fn keys(&self) -> Keys<'_, K, V, N>ⓘNotable traits for Keys<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Keys<'a, K, V, N> type Item = &'a K;
pub fn keys(&self) -> Keys<'_, K, V, N>ⓘNotable traits for Keys<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Keys<'a, K, V, N> type Item = &'a K;
Gets an iterator over the keys of the map, in sorted order.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(2, "b");
a.insert(1, "a");
let keys: Vec<_> = a.keys().cloned().collect();
assert_eq!(keys, [1, 2]);
sourcepub fn into_keys(self) -> IntoKeys<K, V, N>ⓘNotable traits for IntoKeys<K, V, N>impl<K: Ord + Default, V: Default, const N: usize> Iterator for IntoKeys<K, V, N> type Item = K;
pub fn into_keys(self) -> IntoKeys<K, V, N>ⓘNotable traits for IntoKeys<K, V, N>impl<K: Ord + Default, V: Default, const N: usize> Iterator for IntoKeys<K, V, N> type Item = K;
Creates a consuming iterator visiting all the keys, in sorted order.
The map cannot be used after calling this.
The iterator element type is K
.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(2, "b");
a.insert(1, "a");
let keys: Vec<i32> = a.into_keys().collect();
assert_eq!(keys, [1, 2]);
sourcepub fn values(&self) -> Values<'_, K, V, N>ⓘNotable traits for Values<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Values<'a, K, V, N> type Item = &'a V;
pub fn values(&self) -> Values<'_, K, V, N>ⓘNotable traits for Values<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Values<'a, K, V, N> type Item = &'a V;
Gets an iterator over the values of the map, in order by key.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(1, "hello");
a.insert(2, "goodbye");
let values: Vec<&str> = a.values().cloned().collect();
assert_eq!(values, ["hello", "goodbye"]);
sourcepub fn into_values(self) -> IntoValues<K, V, N>ⓘNotable traits for IntoValues<K, V, N>impl<K: Ord + Default, V: Default, const N: usize> Iterator for IntoValues<K, V, N> type Item = V;
pub fn into_values(self) -> IntoValues<K, V, N>ⓘNotable traits for IntoValues<K, V, N>impl<K: Ord + Default, V: Default, const N: usize> Iterator for IntoValues<K, V, N> type Item = V;
Creates a consuming iterator visiting all the values, in order by key.
The map cannot be used after calling this.
The iterator element type is V
.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(1, "hello");
a.insert(2, "goodbye");
let values: Vec<&str> = a.into_values().collect();
assert_eq!(values, ["hello", "goodbye"]);
sourcepub fn values_mut(&mut self) -> ValuesMut<'_, K, V, N>ⓘNotable traits for ValuesMut<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for ValuesMut<'a, K, V, N> type Item = &'a mut V;
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, N>ⓘNotable traits for ValuesMut<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for ValuesMut<'a, K, V, N> type Item = &'a mut V;
Gets a mutable iterator over the values of the map, in order by key.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(1, String::from("hello"));
a.insert(2, String::from("goodbye"));
for value in a.values_mut() {
value.push_str("!");
}
let values: Vec<String> = a.values().cloned().collect();
assert_eq!(values, [String::from("hello!"),
String::from("goodbye!")]);
sourcepub fn append(&mut self, other: &mut SgMap<K, V, N>)
pub fn append(&mut self, other: &mut SgMap<K, V, N>)
Moves all elements from other
into self
, leaving other
empty.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
let mut b = SgMap::<_, _, 10>::new();
b.insert(3, "d");
b.insert(4, "e");
b.insert(5, "f");
a.append(&mut b);
assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);
assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");
assert_eq!(a[&3], "d");
assert_eq!(a[&4], "e");
assert_eq!(a[&5], "f");
sourcepub fn try_append(&mut self, other: &mut SgMap<K, V, N>) -> Result<(), SgError>
pub fn try_append(&mut self, other: &mut SgMap<K, V, N>) -> Result<(), SgError>
Attempts to move all elements from other
into self
, leaving other
empty.
Examples
use core::iter::FromIterator;
use scapegoat::{SgMap, SgError};
let mut a = SgMap::<_, _, 10>::new();
a.try_insert(1, "a").is_ok();
a.try_insert(2, "b").is_ok();
a.try_insert(3, "c").is_ok();
let mut b = SgMap::<_, _, 10>::new();
b.try_insert(3, "d").is_ok(); // Overwrite previous
b.try_insert(4, "e").is_ok();
b.try_insert(5, "f").is_ok();
// Successful append
assert!(a.try_append(&mut b).is_ok());
// Elements moved
assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);
assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");
assert_eq!(a[&3], "d");
assert_eq!(a[&4], "e");
assert_eq!(a[&5], "f");
// Fill remaining capacity
let mut key = 6;
while a.len() < a.capacity() {
assert!(a.try_insert(key, "filler").is_ok());
key += 1;
}
// Full
assert!(a.is_full());
// More data
let mut c = SgMap::<_, _, 10>::from_iter([(11, "k"), (12, "l")]);
let mut d = SgMap::<_, _, 10>::from_iter([(1, "a2"), (2, "b2")]);
// Cannot append new pairs
assert_eq!(a.try_append(&mut c), Err(SgError::StackCapacityExceeded));
// Can still replace existing pairs
assert!(a.try_append(&mut d).is_ok());
sourcepub fn insert(&mut self, key: K, val: V) -> Option<V> where
K: Ord,
pub fn insert(&mut self, key: K, val: V) -> Option<V> where
K: Ord,
Insert 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, the old value is returned,
and the key is updated. This accommodates types that can be ==
without being identical.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
assert_eq!(map.insert(37, "a"), None);
assert_eq!(map.is_empty(), false);
map.insert(37, "b");
assert_eq!(map.insert(37, "c"), Some("b"));
assert_eq!(map[&37], "c");
sourcepub fn try_insert(&mut self, key: K, val: V) -> Result<Option<V>, SgError> where
K: Ord,
pub fn try_insert(&mut self, key: K, val: V) -> Result<Option<V>, SgError> where
K: Ord,
Insert a key-value pair into the map.
Returns Err
if the operation can’t be completed, else the Ok
contains:
None
if the map did not have this key present.- The old value if the map did have this key present (both the value and key are updated,
this accommodates types that can be
==
without being identical).
Warning
Unlike other APIs in this crate, the semantics and return type of this API are NOT the same as BTreeMap
’s nightly try_insert
.
For an equivalent, use try_insert_std
.
Examples
use scapegoat::{SgMap, SgError};
let mut map = SgMap::<_, _, 10>::new();
// Add a new pair
assert_eq!(map.try_insert(37, "a"), Ok(None));
assert_eq!(map.is_empty(), false);
// Replace existing pair
map.insert(37, "b");
assert_eq!(map.try_insert(37, "c"), Ok(Some("b")));
assert_eq!(map[&37], "c");
// Fill remaining capacity
let mut key = 38;
while map.len() < map.capacity() {
assert!(map.try_insert(key, "filler").is_ok());
key += 1;
}
// Full
assert!(map.is_full());
// Cannot insert new pair
assert_eq!(map.try_insert(key, "out of bounds"), Err(SgError::StackCapacityExceeded));
// Can still replace existing pair
assert_eq!(map.try_insert(key - 1, "overwrite filler"), Ok(Some("filler")));
sourcepub fn try_insert_std(
&mut self,
key: K,
value: V
) -> Result<&mut V, OccupiedError<'_, K, V, N>> where
K: Ord,
pub fn try_insert_std(
&mut self,
key: K,
value: V
) -> Result<&mut V, OccupiedError<'_, K, V, N>> where
K: Ord,
Tries to insert a key-value pair into the map, and returns a mutable reference to the value in the entry.
If the map already had this key present, nothing is updated, and an error containing the occupied entry and the value is returned.
Warning
The semantics and return type of this API match BTreeMap
’s nightly try_insert
, NOT the other try_*
APIs in this crate.
For a fallible insert, use try_insert
.
Examples
Basic usage:
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
assert_eq!(map.try_insert_std(37, "a").unwrap(), &"a");
let err = map.try_insert_std(37, "b").unwrap_err();
assert_eq!(err.entry.key(), &37);
assert_eq!(err.entry.get(), &"a");
assert_eq!(err.value, "b");
sourcepub fn try_extend<I: ExactSizeIterator + IntoIterator<Item = (K, V)>>(
&mut self,
iter: I
) -> Result<(), SgError>
pub fn try_extend<I: ExactSizeIterator + IntoIterator<Item = (K, V)>>(
&mut self,
iter: I
) -> Result<(), SgError>
Attempt to extend a collection with the contents of an iterator.
Examples
use core::iter::FromIterator;
use scapegoat::{SgMap, SgError};
let mut a = SgMap::<_, _, 2>::new();
let mut b = SgMap::<_, _, 3>::from_iter([(1, "a"), (2, "b"), (3, "c")]);
let mut c = SgMap::<_, _, 2>::from_iter([(1, "a"), (2, "b")]);
// Too big
assert_eq!(a.try_extend(b.into_iter()), Err(SgError::StackCapacityExceeded));
// Fits
assert!(a.try_extend(c.into_iter()).is_ok());
Note
There is no TryExtend
trait in core
/std
.
sourcepub fn try_from_iter<I: ExactSizeIterator + IntoIterator<Item = (K, V)>>(
iter: I
) -> Result<Self, SgError>
pub fn try_from_iter<I: ExactSizeIterator + IntoIterator<Item = (K, V)>>(
iter: I
) -> Result<Self, SgError>
Attempt conversion from an iterator.
Will fail if iterator length exceeds u16::MAX
.
Examples
use scapegoat::{SgMap, SgError};
const CAPACITY_1: usize = 1_000;
let vec: Vec<(usize, usize)> = (0..CAPACITY_1).map(|n|(n, n)).collect();
assert!(SgMap::<usize, usize, CAPACITY_1>::try_from_iter(vec.into_iter()).is_ok());
const CAPACITY_2: usize = (u16::MAX as usize) + 1;
let vec: Vec<(usize, usize)> = (0..CAPACITY_2).map(|n|(n, n)).collect();
assert_eq!(
SgMap::<usize, usize, CAPACITY_2>::try_from_iter(vec.into_iter()),
Err(SgError::MaximumCapacityExceeded)
);
Note
There is no TryFromIterator
trait in core
/std
.
sourcepub fn iter(&self) -> Iter<'_, K, V, N>ⓘNotable traits for Iter<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Iter<'a, K, V, N> type Item = (&'a K, &'a V);
pub fn iter(&self) -> Iter<'_, K, V, N>ⓘNotable traits for Iter<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Iter<'a, K, V, N> type Item = (&'a K, &'a V);
Gets an iterator over the entries of the map, sorted by key.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(3, "c");
map.insert(2, "b");
map.insert(1, "a");
for (key, value) in map.iter() {
println!("{}: {}", key, value);
}
let (first_key, first_value) = map.iter().next().unwrap();
assert_eq!((*first_key, *first_value), (1, "a"));
sourcepub fn iter_mut(&mut self) -> IterMut<'_, K, V, N>ⓘNotable traits for IterMut<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for IterMut<'a, K, V, N> type Item = (&'a K, &'a mut V);
pub fn iter_mut(&mut self) -> IterMut<'_, K, V, N>ⓘNotable traits for IterMut<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for IterMut<'a, K, V, N> type Item = (&'a K, &'a mut V);
Gets a mutable iterator over the entries of the map, sorted by key.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
// Add 10 to the value if the key isn't "a"
for (key, value) in map.iter_mut() {
if key != &"a" {
*value += 10;
}
}
let (second_key, second_value) = map.iter().skip(1).next().unwrap();
assert_eq!((*second_key, *second_value), ("b", 12));
sourcepub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Removes a key from the map, returning the stored key and value if the key was previously in the map.
The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
assert_eq!(map.remove_entry(&1), Some((1, "a")));
assert_eq!(map.remove_entry(&1), None);
sourcepub fn retain<F>(&mut self, f: F) where
K: Ord,
F: FnMut(&K, &mut V) -> bool,
pub fn retain<F>(&mut self, f: F) where
K: Ord,
F: FnMut(&K, &mut V) -> bool,
Retains only the elements specified by the predicate.
In other words, remove all pairs (k, v)
such that f(&k, &mut v)
returns false
.
The elements are visited in ascending key order.
Examples
use scapegoat::SgMap;
let mut map: SgMap<i32, i32, 10> = (0..8).map(|x| (x, x*10)).collect();
// Keep only the elements with even-numbered keys.
map.retain(|&k, _| k % 2 == 0);
assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));
sourcepub fn split_off<Q>(&mut self, key: &Q) -> SgMap<K, V, N> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn split_off<Q>(&mut self, key: &Q) -> SgMap<K, V, N> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Splits the collection into two at the given key. Returns everything after the given key, including the key.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
a.insert(17, "d");
a.insert(41, "e");
let b = a.split_off(&3);
assert_eq!(a.len(), 2);
assert_eq!(b.len(), 3);
assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");
assert_eq!(b[&3], "c");
assert_eq!(b[&17], "d");
assert_eq!(b[&41], "e");
sourcepub fn remove<Q>(&mut self, key: &Q) -> Option<V> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn remove<Q>(&mut self, key: &Q) -> Option<V> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Removes a key from the map, returning the value at the key if the key was previously in the map.
The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);
sourcepub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Returns the key-value pair corresponding to the supplied key.
The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);
sourcepub fn get<Q>(&self, key: &Q) -> Option<&V> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn get<Q>(&self, key: &Q) -> Option<&V> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Returns a reference to the value corresponding to the key.
The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);
sourcepub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
if let Some(x) = map.get_mut(&1) {
*x = "b";
}
assert_eq!(map[&1], "b");
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clears the map, removing all elements.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
a.insert(1, "a");
a.clear();
assert!(a.is_empty());
sourcepub fn contains_key<Q>(&self, key: &Q) -> bool where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn contains_key<Q>(&self, key: &Q) -> bool where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Returns true
if the map contains a value for the specified key.
The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);
sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true
if the map contains no elements.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());
sourcepub fn is_full(&self) -> bool
pub fn is_full(&self) -> bool
Returns true
if the map’s capacity is filled.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 2>::new();
a.insert(1, "a");
assert!(!a.is_full());
a.insert(2, "b");
assert!(a.is_full());
sourcepub fn first_key_value(&self) -> Option<(&K, &V)> where
K: Ord,
pub fn first_key_value(&self) -> Option<(&K, &V)> where
K: Ord,
Returns a reference to the first key-value pair in the map. The key in this pair is the minimum key in the map.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
assert_eq!(map.first_key_value(), None);
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.first_key_value(), Some((&1, &"b")));
sourcepub fn first_key(&self) -> Option<&K> where
K: Ord,
pub fn first_key(&self) -> Option<&K> where
K: Ord,
Returns a reference to the first/minium key in the map, if any.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
assert_eq!(map.first_key_value(), None);
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.first_key(), Some(&1));
sourcepub fn pop_first(&mut self) -> Option<(K, V)> where
K: Ord,
pub fn pop_first(&mut self) -> Option<(K, V)> where
K: Ord,
Removes and returns the first element in the map. The key of this element is the minimum key that was in the map.
Examples
Draining elements in ascending order, while keeping a usable map each iteration.
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
map.insert(2, "b");
while let Some((key, _val)) = map.pop_first() {
assert!((&map).into_iter().all(|(k, _v)| *k > key));
}
assert!(map.is_empty());
sourcepub fn last_key_value(&self) -> Option<(&K, &V)> where
K: Ord,
pub fn last_key_value(&self) -> Option<(&K, &V)> where
K: Ord,
Returns a reference to the last key-value pair in the map. The key in this pair is the maximum key in the map.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.last_key_value(), Some((&2, &"a")));
sourcepub fn last_key(&self) -> Option<&K> where
K: Ord,
pub fn last_key(&self) -> Option<&K> where
K: Ord,
Returns a reference to the last/maximum key in the map, if any.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.last_key(), Some(&2));
sourcepub fn pop_last(&mut self) -> Option<(K, V)> where
K: Ord,
pub fn pop_last(&mut self) -> Option<(K, V)> where
K: Ord,
Removes and returns the last element in the map. The key of this element is the maximum key that was in the map.
Examples
Draining elements in descending order, while keeping a usable map each iteration.
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
map.insert(2, "b");
while let Some((key, _val)) = map.pop_last() {
assert!((&map).into_iter().all(|(k, _v)| *k < key));
}
assert!(map.is_empty());
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the number of elements in the map.
Examples
use scapegoat::SgMap;
let mut a = SgMap::<_, _, 10>::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);
sourcepub fn entry(&mut self, key: K) -> Entry<'_, K, V, N>
pub fn entry(&mut self, key: K) -> Entry<'_, K, V, N>
Gets the given key’s corresponding entry in the map for in-place manipulation.
Examples
Basic usage:
use scapegoat::SgMap;
let mut count = SgMap::<&str, usize, 10>::new();
// count the number of occurrences of letters in the vec
for x in vec!["a", "b", "a", "c", "a", "b"] {
*count.entry(x).or_insert(0) += 1;
}
assert_eq!(count["a"], 3);
sourcepub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, N>>
pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, N>>
Returns the first entry in the map for in-place manipulation. The key of this entry is the minimum key in the map.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
map.insert(2, "b");
if let Some(mut entry) = map.first_entry() {
if *entry.key() > 0 {
entry.insert("first");
}
}
assert_eq!(*map.get(&1).unwrap(), "first");
assert_eq!(*map.get(&2).unwrap(), "b");
sourcepub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, N>>
pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, N>>
Returns the last entry in the map for in-place manipulation. The key of this entry is the maximum key in the map.
Examples
use scapegoat::SgMap;
let mut map = SgMap::<_, _, 10>::new();
map.insert(1, "a");
map.insert(2, "b");
if let Some(mut entry) = map.last_entry() {
if *entry.key() > 0 {
entry.insert("last");
}
}
assert_eq!(*map.get(&1).unwrap(), "a");
assert_eq!(*map.get(&2).unwrap(), "last");
sourcepub fn range<T, R>(&self, range: R) -> Range<'_, K, V, N>ⓘNotable traits for Range<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Range<'a, K, V, N> type Item = (&'a K, &'a V);
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
pub fn range<T, R>(&self, range: R) -> Range<'_, K, V, N>ⓘNotable traits for Range<'a, K, V, N>impl<'a, K: Ord + Default, V: Default, const N: usize> Iterator for Range<'a, K, V, N> type Item = (&'a K, &'a V);
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
Constructs a double-ended iterator over a sub-range of elements in the map.
The simplest way is to use the range syntax min..max
, thus range(min..max)
will
yield elements from min (inclusive) to max (exclusive).
The range may also be entered as (Bound<T>, Bound<T>)
, so for example
range((Excluded(4), Included(10)))
will yield a left-exclusive, right-inclusive
range from 4 to 10.
Panics
Panics if range start > end
.
Panics if range start == end
and both bounds are Excluded
.
Examples
Basic usage:
use scapegoat::SgMap;
use core::ops::Bound::Included;
let mut map = SgMap::<_, _, 10>::new();
map.insert(3, "a");
map.insert(5, "b");
map.insert(8, "c");
for (&key, &value) in map.range((Included(&4), Included(&8))) {
println!("{}: {}", key, value);
}
assert_eq!(Some((&5, &"b")), map.range(4..).next());
sourcepub fn range_mut<T, R>(&mut self, range: R) -> RangeMut<'_, K, V, N>ⓘNotable traits for RangeMut<'a, K, V, N>impl<'a, K, V, const N: usize> Iterator for RangeMut<'a, K, V, N> where
K: Ord + Default,
V: Default, type Item = (&'a K, &'a mut V);
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
pub fn range_mut<T, R>(&mut self, range: R) -> RangeMut<'_, K, V, N>ⓘNotable traits for RangeMut<'a, K, V, N>impl<'a, K, V, const N: usize> Iterator for RangeMut<'a, K, V, N> where
K: Ord + Default,
V: Default, type Item = (&'a K, &'a mut V);
where
T: Ord + ?Sized,
K: Borrow<T> + Ord,
R: RangeBounds<T>,
K: Ord + Default,
V: Default, type Item = (&'a K, &'a mut V);
Constructs a mutable single-ended iterator over a sub-range of elements in the map.
The simplest way is to use the range syntax min..max
, thus range(min..max)
will
yield elements from min (inclusive) to max (exclusive).
The range may also be entered as (Bound<T>, Bound<T>)
, so for example
range((Excluded(4), Included(10)))
will yield a left-exclusive, right-inclusive
range from 4 to 10.
Panics
Panics if range start > end
.
Panics if range start == end
and both bounds are Excluded
.
Examples
Basic usage:
use scapegoat::SgMap;
let mut map: SgMap<_, _, 10> = ["Alice", "Bob", "Carol", "Cheryl"]
.iter()
.map(|&s| (s, 0))
.collect();
for (_, balance) in map.range_mut("B".."Cheryl") {
*balance += 100;
}
for (name, balance) in &map {
println!("{} => {}", name, balance);
}
assert_eq!(map["Alice"], 0);
assert_eq!(map["Bob"], 100);
Trait Implementations
sourceimpl<K: Default, V: Default, const N: usize> Debug for SgMap<K, V, N> where
K: Ord + Debug,
V: Debug,
impl<K: Default, V: Default, const N: usize> Debug for SgMap<K, V, N> where
K: Ord + Debug,
V: Debug,
sourceimpl<K: Default + Ord + Default, V: Default + Default, const N: usize> Default for SgMap<K, V, N>
impl<K: Default + Ord + Default, V: Default + Default, const N: usize> Default for SgMap<K, V, N>
sourceimpl<'a, K: Default, V: Default, const N: usize> Extend<(&'a K, &'a V)> for SgMap<K, V, N> where
K: Ord + Copy,
V: Copy,
impl<'a, K: Default, V: Default, const N: usize> Extend<(&'a K, &'a V)> for SgMap<K, V, N> where
K: Ord + Copy,
V: Copy,
sourcefn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: I)
Extends a collection with the contents of an iterator. Read more
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Extends a collection with exactly one element.
sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
sourceimpl<K: Default, V: Default, const N: usize> Extend<(K, V)> for SgMap<K, V, N> where
K: Ord,
impl<K: Default, V: Default, const N: usize> Extend<(K, V)> for SgMap<K, V, N> where
K: Ord,
sourcefn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)
Extends a collection with the contents of an iterator. Read more
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Extends a collection with exactly one element.
sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
sourceimpl<K: Default, V: Default, const N: usize> From<[(K, V); N]> for SgMap<K, V, N> where
K: Ord,
impl<K: Default, V: Default, const N: usize> From<[(K, V); N]> for SgMap<K, V, N> where
K: Ord,
sourcefn from(arr: [(K, V); N]) -> Self
fn from(arr: [(K, V); N]) -> Self
use scapegoat::SgMap;
let map1 = SgMap::from([(1, 2), (3, 4)]);
let map2: SgMap<_, _, 2> = [(1, 2), (3, 4)].into();
assert_eq!(map1, map2);
Warning
TryFrom
isn’t implemented because it would collide with the blanket implementation.
See this open GitHub issue from 2018,
this is a known Rust limitation that should be fixed via specialization in the future.
sourceimpl<K: Default, V: Default, const N: usize> FromIterator<(K, V)> for SgMap<K, V, N> where
K: Ord,
impl<K: Default, V: Default, const N: usize> FromIterator<(K, V)> for SgMap<K, V, N> where
K: Ord,
sourceimpl<K: Default, V: Default, Q, const N: usize> Index<&'_ Q> for SgMap<K, V, N> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
impl<K: Default, V: Default, Q, const N: usize> Index<&'_ Q> for SgMap<K, V, N> where
K: Borrow<Q> + Ord,
Q: Ord + ?Sized,
sourceimpl<K: Ord + Ord + Default, V: Ord + Default, const N: usize> Ord for SgMap<K, V, N>
impl<K: Ord + Ord + Default, V: Ord + Default, const N: usize> Ord for SgMap<K, V, N>
sourceimpl<K: PartialEq + Ord + Default, V: PartialEq + Default, const N: usize> PartialEq<SgMap<K, V, N>> for SgMap<K, V, N>
impl<K: PartialEq + Ord + Default, V: PartialEq + Default, const N: usize> PartialEq<SgMap<K, V, N>> for SgMap<K, V, N>
sourceimpl<K: PartialOrd + Ord + Default, V: PartialOrd + Default, const N: usize> PartialOrd<SgMap<K, V, N>> for SgMap<K, V, N>
impl<K: PartialOrd + Ord + Default, V: PartialOrd + Default, const N: usize> PartialOrd<SgMap<K, V, N>> for SgMap<K, V, N>
sourcefn partial_cmp(&self, other: &SgMap<K, V, N>) -> Option<Ordering>
fn partial_cmp(&self, other: &SgMap<K, V, N>) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
1.0.0 · sourcefn lt(&self, other: &Rhs) -> bool
fn lt(&self, other: &Rhs) -> bool
This method tests less than (for self
and other
) and is used by the <
operator. Read more
1.0.0 · sourcefn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
impl<K: Eq + Ord + Default, V: Eq + Default, const N: usize> Eq for SgMap<K, V, N>
impl<K: Ord + Default, V: Default, const N: usize> StructuralEq for SgMap<K, V, N>
impl<K: Ord + Default, V: Default, const N: usize> StructuralPartialEq for SgMap<K, V, N>
Auto Trait Implementations
impl<K, V, const N: usize> RefUnwindSafe for SgMap<K, V, N> where
K: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V, const N: usize> Send for SgMap<K, V, N> where
K: Send,
V: Send,
impl<K, V, const N: usize> Sync for SgMap<K, V, N> where
K: Sync,
V: Sync,
impl<K, V, const N: usize> Unpin for SgMap<K, V, N> where
K: Unpin,
V: Unpin,
impl<K, V, const N: usize> UnwindSafe for SgMap<K, V, N> where
K: UnwindSafe,
V: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcepub fn borrow_mut(&mut self) -> &mut T
pub fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more