Struct skiplist::skipmap::SkipMap
[−]
[src]
pub struct SkipMap<K, V> {
// some fields omitted
}The skipmap provides a way of storing element pairs such that they keys are always sorted whilst at the same time providing efficient way to access, insert and removes nodes.
A particular node can be accessed through the matching key, and since the keys are always sorted, it is also possible to access key-value pairs by index.
Note that mutable references to keys are not available at all as this could result in a node being left out of the proper ordering.
Methods
impl<K, V> SkipMap<K, V> where K: Ord
fn new() -> Self
Create a new skipmap with the default number of 16 levels.
Examples
use skiplist::SkipMap; let mut skipmap: SkipMap<i64, String> = SkipMap::new();
fn with_capacity(capacity: usize) -> Self
Constructs a new, empty skipmap with the optimal number of levels for the intended
capacity. Specifically, it uses floor(log2(capacity)) number of levels, ensuring that
only a few nodes occupy the highest level.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::with_capacity(100); skipmap.extend((0..100).map(|x| (x, x)));
fn insert(&mut self, key: K, value: V) -> Option<V>
Insert the element into the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.len(), 2); assert!(!skipmap.is_empty());
impl<K, V> SkipMap<K, V>
fn clear(&mut self)
Clears the skipmap, removing all values.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); skipmap.clear(); assert!(skipmap.is_empty());
fn len(&self) -> usize
Returns the number of elements in the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.len(), 10);
fn is_empty(&self) -> bool
Returns true if the skipmap contains no elements.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert!(skipmap.is_empty()); skipmap.insert(1, "Rust"); assert!(!skipmap.is_empty());
fn front(&self) -> Option<(&K, &V)>
Provides a reference to the front element, or None if the skipmap is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.front(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.front(), Some((&1, &"Hello")));
fn front_mut(&self) -> Option<(&K, &mut V)>
Provides a mutable reference to the front element, or None if the skipmap is empty.
The reference to the key remains immutable as the keys must remain sorted.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.front(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.front_mut(), Some((&1, &mut "Hello")));
fn back(&self) -> Option<(&K, &V)>
Provides a reference to the back element, or None if the skipmap is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.back(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.back(), Some((&2, &"World")));
fn back_mut(&mut self) -> Option<(&K, &mut V)>
Provides a reference to the back element, or None if the skipmap is empty.
The reference to the key remains immutable as the keys must remain sorted.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.back(), None); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.back_mut(), Some((&2, &mut "World")));
fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where K: Borrow<Q>, Q: Ord
Provides a reference to the element at the given index, or None if the skipmap is empty
or the index is out of bounds.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.get(&0), None); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.get(&0), Some(&0)); assert_eq!(skipmap.get(&10), None);
fn get_mut<Q: ?Sized>(&self, key: &Q) -> Option<&mut V> where K: Borrow<Q>, Q: Ord
Provides a reference to the element at the given index, or None if the skipmap is empty
or the index is out of bounds.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); assert_eq!(skipmap.get(&0), None); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.get_mut(&0), Some(&mut 0)); assert_eq!(skipmap.get_mut(&10), None); match skipmap.get_mut(&0) { Some(x) => *x = 100, None => (), } assert_eq!(skipmap.get(&0), Some(&100));
fn pop_front(&mut self) -> Option<(K, V)>
Removes the first element and returns it, or None if the sequence is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.pop_front(), Some((1, "Hello"))); assert_eq!(skipmap.pop_front(), Some((2, "World"))); assert_eq!(skipmap.pop_front(), None);
fn pop_back(&mut self) -> Option<(K, V)>
Removes the last element and returns it, or None if the sequence is empty.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.insert(1, "Hello"); skipmap.insert(2, "World"); assert_eq!(skipmap.pop_back(), Some((2, "World"))); assert_eq!(skipmap.pop_back(), Some((1, "Hello"))); assert_eq!(skipmap.pop_back(), None);
fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where K: Borrow<Q>, Q: Ord
Returns true if the value is contained in the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert!(skipmap.contains_key(&4)); assert!(!skipmap.contains_key(&15));
fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where K: Borrow<Q>, Q: Ord
Removes and returns an element with the same value or None if there are no such values in the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.remove(&4), Some(4)); // Removes the last one assert_eq!(skipmap.remove(&4), None); // No more '4' left
fn remove_index(&mut self, index: &usize) -> (K, V)
Removes and returns an element with the given index.
Panics
Panics is the index is out of bounds.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); assert_eq!(skipmap.remove_index(&4), (4, 4)); assert_eq!(skipmap.remove_index(&4), (5, 5));
fn into_iter(self) -> IntoIter<K, V>
Get an owning iterator over the entries of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.into_iter() { println!("Key {}, Value: {}", k, v); }
fn iter(&self) -> Iter<K, V>
Creates an iterator over the entries of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.iter() { println!("Key: {}, Value: {}", k, v); }
fn iter_mut(&self) -> IterMut<K, V>
Creates an mutable iterator over the entries of the skipmap.
The keys cannot be modified as they must remain in order.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.iter_mut() { println!("Key: {}, Value: {}", k, v); }
fn keys(&self) -> Keys<K, V>
Creates an iterator over the keys of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for k in skipmap.keys() { println!("Key: {}", k); }
fn values(&self) -> Values<K, V>
Creates an iterator over the values of the skipmap.
Examples
use skiplist::SkipMap; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for v in skipmap.values() { println!("Value: {}", v); }
fn range<Q>(&self, min: Bound<&Q>, max: Bound<&Q>) -> Iter<K, V> where K: Borrow<Q>, Q: Ord
Constructs a double-ended iterator over a sub-range of elements in the skipmap, starting
at min, and ending at max. If min is Unbounded, then it will be treated as "negative
infinity", and if max is Unbounded, then it will be treated as "positive infinity". Thus
range(Unbounded, Unbounded) will yield the whole collection.
Examples
#![feature(collections_bound)] use skiplist::SkipMap; use std::collections::Bound::{Included, Unbounded}; let mut skipmap = SkipMap::new(); skipmap.extend((0..10).map(|x| (x, x))); for (k, v) in skipmap.range(Included(&3), Included(&7)) { println!("Key: {}, Value: {}", k, v); } assert_eq!(Some((&4, &4)), skipmap.range(Included(&4), Unbounded).next());
Trait Implementations
impl<K: Send, V: Send> Send for SkipMap<K, V>
impl<K: Sync, V: Sync> Sync for SkipMap<K, V>
impl<K, V> Drop for SkipMap<K, V>
fn drop(&mut self)
impl<K: Ord, V> Default for SkipMap<K, V>
impl<AK, AV, BK, BV> PartialEq<SkipMap<BK, BV>> for SkipMap<AK, AV> where AK: PartialEq<BK>, AV: PartialEq<BV>
This implementation of PartialEq only checks that the values are equal; it does not check for
equivalence of other features (such as the ordering function and the node levels).
Furthermore, this uses T's implementation of PartialEq and does not use the owning
skipmap's comparison function.