Struct splay_tree::SplayMap
source · pub struct SplayMap<K, V> { /* private fields */ }
Expand description
A map based on a splay tree.
A splay tree based map is a self-adjusting data structure.
It performs insertion, removal and look-up in O(log n)
amortized time.
It is a logic error for a key to be modified in such a way that
the key’s ordering relative to any other key,
as determined by the Ord
trait, changes while it is in the map.
This is normally only possible through Cell
, RefCell
, global state, I/O, or unsafe code.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
map.insert("bar", 2);
map.insert("baz", 3);
assert_eq!(map.get("foo"), Some(&1));
assert_eq!(map.remove("foo"), Some(1));
assert_eq!(map.get("foo"), None);
for (k, v) in &map {
println!("{}: {}", k, v);
}
SplayMap
implements an Entry API which allows for
more complex methods of getting, setting, updating and removing keys and their values:
use splay_tree::SplayMap;
let mut count = SplayMap::new();
for _ in 0..1000 {
let k = rand::random::<u8>();
*count.entry(k).or_insert(0) += 1;
}
for k in 0..=255 {
println!("{}: {}", k, count.get(&k).unwrap_or(&0));
}
Implementations§
source§impl<K, V> SplayMap<K, V>where
K: Ord,
impl<K, V> SplayMap<K, V>where
K: Ord,
sourcepub fn new() -> Self
pub fn new() -> Self
Makes a new empty SplayMap
.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
assert_eq!(map.len(), 1);
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clears the map, removing all values.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
map.clear();
assert!(map.is_empty());
sourcepub fn contains_key<Q: ?Sized>(&mut self, key: &Q) -> boolwhere
K: Borrow<Q>,
Q: Ord,
pub fn contains_key<Q: ?Sized>(&mut self, key: &Q) -> boolwhere
K: Borrow<Q>,
Q: Ord,
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.
Notice
Because SplayMap
is a self-adjusting amortized data structure,
this function requires the mut
qualifier for self
.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
assert!(map.contains_key("foo"));
assert!(!map.contains_key("bar"));
sourcepub fn contains_key_immut<Q: ?Sized>(&self, key: &Q) -> boolwhere
K: Borrow<Q>,
Q: Ord,
pub fn contains_key_immut<Q: ?Sized>(&self, key: &Q) -> boolwhere
K: Borrow<Q>,
Q: Ord,
Immutable version of SplayMap::contains_key()
.
Note that this method could be less efficient than the mutable version.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
assert!(map.contains_key_immut("foo"));
assert!(!map.contains_key_immut("bar"));
sourcepub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Ord,
pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Ord,
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.
Notice
Because SplayMap
is a self-adjusting amortized data structure,
this function requires the mut
qualifier for self
.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
assert_eq!(map.get("foo"), Some(&1));
assert_eq!(map.get("bar"), None);
sourcepub fn get_immut<Q: ?Sized>(&self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Ord,
pub fn get_immut<Q: ?Sized>(&self, key: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: Ord,
Immutable version of SplayMap::get()
.
Note that this method could be less efficient than the mutable version.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
assert_eq!(map.get_immut("foo"), Some(&1));
assert_eq!(map.get_immut("bar"), None);
sourcepub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: Ord,
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: Ord,
Returns a mutable 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 splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
map.get_mut("foo").map(|v| *v = 2);
assert_eq!(map.get("foo"), Some(&2));
sourcepub fn find_lower_bound_key<Q: ?Sized>(&mut self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
pub fn find_lower_bound_key<Q: ?Sized>(&mut self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
Finds a minimum key which satisfies “greater than or equal to key
” condition in the map.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.find_lower_bound_key(&0), Some(&1));
assert_eq!(map.find_lower_bound_key(&1), Some(&1));
assert_eq!(map.find_lower_bound_key(&4), None);
sourcepub fn find_lower_bound_key_immut<Q: ?Sized>(&self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
pub fn find_lower_bound_key_immut<Q: ?Sized>(&self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
Immutable version of SplayMap::find_lower_bound_key()
.
Note that this method could be less efficient than the mutable version.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.find_lower_bound_key_immut(&0), Some(&1));
assert_eq!(map.find_lower_bound_key_immut(&1), Some(&1));
assert_eq!(map.find_lower_bound_key_immut(&4), None);
sourcepub fn find_upper_bound_key<Q: ?Sized>(&mut self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
pub fn find_upper_bound_key<Q: ?Sized>(&mut self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
Finds a minimum key which satisfies “greater than key
” condition in the map.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.find_upper_bound_key(&0), Some(&1));
assert_eq!(map.find_upper_bound_key(&1), Some(&3));
assert_eq!(map.find_upper_bound_key(&4), None);
sourcepub fn find_upper_bound_key_immut<Q: ?Sized>(&self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
pub fn find_upper_bound_key_immut<Q: ?Sized>(&self, key: &Q) -> Option<&K>where
K: Borrow<Q>,
Q: Ord,
Immutable version of SplayMap::find_upper_bound_key()
.
Note that this method could be less efficient than the mutable version.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.find_upper_bound_key_immut(&0), Some(&1));
assert_eq!(map.find_upper_bound_key_immut(&1), Some(&3));
assert_eq!(map.find_upper_bound_key_immut(&4), None);
sourcepub fn smallest(&mut self) -> Option<(&K, &V)>
pub fn smallest(&mut self) -> Option<(&K, &V)>
Gets the entry which have the minimum key in the map.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.smallest(), Some((&1, &())));
sourcepub fn smallest_immut(&self) -> Option<(&K, &V)>
pub fn smallest_immut(&self) -> Option<(&K, &V)>
Immutable version of SplayMap::smallest()
.
Note that this method could be less efficient than the mutable version.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.smallest_immut(), Some((&1, &())));
sourcepub fn take_smallest(&mut self) -> Option<(K, V)>
pub fn take_smallest(&mut self) -> Option<(K, V)>
Takes the entry which have the minimum key in the map.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.take_smallest(), Some((1, ())));
assert_eq!(map.take_smallest(), Some((3, ())));
assert_eq!(map.take_smallest(), None);
sourcepub fn largest(&mut self) -> Option<(&K, &V)>
pub fn largest(&mut self) -> Option<(&K, &V)>
Gets the entry which have the maximum key in the map.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.largest(), Some((&3, &())));
sourcepub fn largest_immut(&self) -> Option<(&K, &V)>
pub fn largest_immut(&self) -> Option<(&K, &V)>
Immutable version of SplayMap::largest()
.
Note that this method could be less efficient than the mutable version.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.largest_immut(), Some((&3, &())));
sourcepub fn take_largest(&mut self) -> Option<(K, V)>
pub fn take_largest(&mut self) -> Option<(K, V)>
Takes the entry which have the maximum key in the map.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert(1, ());
map.insert(3, ());
assert_eq!(map.take_largest(), Some((3, ())));
assert_eq!(map.take_largest(), Some((1, ())));
assert_eq!(map.take_largest(), None);
sourcepub fn insert(&mut self, key: K, value: V) -> Option<V>
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.
The key is not updated, though;
this matters for types that can be ==
without being identical.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
assert_eq!(map.insert("foo", 1), None);
assert_eq!(map.get("foo"), Some(&1));
assert_eq!(map.insert("foo", 2), Some(1));
assert_eq!(map.get("foo"), Some(&2));
sourcepub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>where
K: Borrow<Q>,
Q: Ord,
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>where
K: Borrow<Q>,
Q: Ord,
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 splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
assert_eq!(map.remove("foo"), Some(1));
assert_eq!(map.remove("foo"), None);
sourcepub fn entry(&mut self, key: K) -> Entry<'_, K, V>
pub fn entry(&mut self, key: K) -> Entry<'_, K, V>
Gets the given key’s corresponding entry in the map for in-place manipulation.
Examples
use splay_tree::SplayMap;
let mut count = SplayMap::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.get("a"), Some(&3));
source§impl<K, V> SplayMap<K, V>
impl<K, V> SplayMap<K, V>
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the number of elements in the map.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
map.insert("foo", 1);
map.insert("bar", 2);
assert_eq!(map.len(), 2);
sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true if the map contains no elements.
Examples
use splay_tree::SplayMap;
let mut map = SplayMap::new();
assert!(map.is_empty());
map.insert("foo", 1);
assert!(!map.is_empty());
map.clear();
assert!(map.is_empty());
sourcepub fn iter(&self) -> Iter<'_, K, V> ⓘ
pub fn iter(&self) -> Iter<'_, K, V> ⓘ
Gets an iterator over the entries of the map, sorted by key.
Examples
use splay_tree::SplayMap;
let map: SplayMap<_, _> =
vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
assert_eq!(vec![(&"bar", &2), (&"baz", &3), (&"foo", &1)],
map.iter().collect::<Vec<_>>());
sourcepub fn iter_mut(&mut self) -> IterMut<'_, K, V> ⓘ
pub fn iter_mut(&mut self) -> IterMut<'_, K, V> ⓘ
Gets a mutable iterator over the entries of the map, soretd by key.
Examples
use splay_tree::SplayMap;
let mut map: SplayMap<_, _> =
vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
for (_, v) in map.iter_mut() {
*v += 10;
}
assert_eq!(map.get("bar"), Some(&12));
sourcepub fn keys(&self) -> Keys<'_, K, V> ⓘ
pub fn keys(&self) -> Keys<'_, K, V> ⓘ
Gets an iterator over the keys of the map, in sorted order.
Examples
use splay_tree::SplayMap;
let map: SplayMap<_, _> =
vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
assert_eq!(vec!["bar", "baz", "foo"],
map.keys().cloned().collect::<Vec<_>>());
sourcepub fn values(&self) -> Values<'_, K, V> ⓘ
pub fn values(&self) -> Values<'_, K, V> ⓘ
Gets an iterator over the values of the map, in order by key.
Examples
use splay_tree::SplayMap;
let map: SplayMap<_, _> =
vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
assert_eq!(vec![2, 3, 1],
map.values().cloned().collect::<Vec<_>>());
sourcepub fn values_mut(&mut self) -> ValuesMut<'_, K, V> ⓘ
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> ⓘ
Gets a mutable iterator over the values of the map, in order by key.
Examples
use splay_tree::SplayMap;
let mut map: SplayMap<_, _> =
vec![("foo", 1), ("bar", 2), ("baz", 3)].into_iter().collect();
for v in map.values_mut() {
*v += 10;
}
assert_eq!(vec![12, 13, 11],
map.values().cloned().collect::<Vec<_>>());
Trait Implementations§
source§impl<'a, K, V> Extend<(&'a K, &'a V)> for SplayMap<K, V>where
K: 'a + Copy + Ord,
V: 'a + Copy,
impl<'a, K, V> Extend<(&'a K, &'a V)> for SplayMap<K, V>where
K: 'a + Copy + Ord,
V: 'a + Copy,
source§fn extend<T>(&mut self, iter: T)where
T: IntoIterator<Item = (&'a K, &'a V)>,
fn extend<T>(&mut self, iter: T)where
T: IntoIterator<Item = (&'a K, &'a V)>,
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)source§impl<K, V> Extend<(K, V)> for SplayMap<K, V>where
K: Ord,
impl<K, V> Extend<(K, V)> for SplayMap<K, V>where
K: Ord,
source§fn extend<T>(&mut self, iter: T)where
T: IntoIterator<Item = (K, V)>,
fn extend<T>(&mut self, iter: T)where
T: IntoIterator<Item = (K, V)>,
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)source§impl<'a, K, V> IntoIterator for &'a SplayMap<K, V>where
K: 'a,
V: 'a,
impl<'a, K, V> IntoIterator for &'a SplayMap<K, V>where
K: 'a,
V: 'a,
source§impl<'a, K, V> IntoIterator for &'a mut SplayMap<K, V>where
K: 'a,
V: 'a,
impl<'a, K, V> IntoIterator for &'a mut SplayMap<K, V>where
K: 'a,
V: 'a,
source§impl<K, V> IntoIterator for SplayMap<K, V>
impl<K, V> IntoIterator for SplayMap<K, V>
source§impl<K: Ord, V: Ord> Ord for SplayMap<K, V>
impl<K: Ord, V: Ord> Ord for SplayMap<K, V>
1.21.0 · source§fn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere
Self: Sized,
source§impl<K: PartialEq, V: PartialEq> PartialEq<SplayMap<K, V>> for SplayMap<K, V>
impl<K: PartialEq, V: PartialEq> PartialEq<SplayMap<K, V>> for SplayMap<K, V>
source§impl<K: PartialOrd, V: PartialOrd> PartialOrd<SplayMap<K, V>> for SplayMap<K, V>
impl<K: PartialOrd, V: PartialOrd> PartialOrd<SplayMap<K, V>> for SplayMap<K, V>
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
self
and other
) and is used by the <=
operator. Read more