Struct im::map::Map
[−]
[src]
pub struct Map<K, V>(_);
Ordered Map
An immutable ordered map implemented as a balanced 2-3 tree.
Most operations on this type of map are O(log n). It's a decent choice for a generic map datatype, but if you're using it for large datasets, you should consider whether you need an ordered map, or whether a hash map would suit you better.
Methods
impl<K, V> Map<K, V>
[src]
fn new() -> Map<K, V>
Construct an empty map.
fn singleton<RK, RV>(k: RK, v: RV) -> Map<K, V> where
Arc<K>: From<RK>,
Arc<V>: From<RV>,
Arc<K>: From<RK>,
Arc<V>: From<RV>,
Construct a map with a single mapping.
Examples
let map = Map::singleton(123, "onetwothree"); assert_eq!( map.get(&123), Some(Arc::new("onetwothree")) );
fn is_empty(&self) -> bool
Test whether a map is empty.
Time: O(1)
Examples
assert!( !map!{1 => 2}.is_empty() ); assert!( Map::<i32, i32>::new().is_empty() );
fn iter(&self) -> Iter<K, V>
Get an iterator over the key/value pairs of a map.
fn keys(&self) -> Keys<K, V>
Get an iterator over a map's keys.
fn values(&self) -> Values<K, V>
Get an iterator over a map's values.
fn len(&self) -> usize
fn get_max(&self) -> Option<(Arc<K>, Arc<V>)>
Get the largest key in a map, along with its value.
If the map is empty, return None
.
Time: O(log n)
Examples
assert_eq!(Some((Arc::new(3), Arc::new(33))), map!{ 1 => 11, 2 => 22, 3 => 33 }.get_max());
fn get_min(&self) -> Option<(Arc<K>, Arc<V>)>
Get the smallest key in a map, along with its value.
If the map is empty, return None
.
Time: O(log n)
Examples
assert_eq!(Some((Arc::new(1), Arc::new(11))), map!{ 1 => 11, 2 => 22, 3 => 33 }.get_min());
impl<K: Ord, V> Map<K, V>
[src]
fn get(&self, k: &K) -> Option<Arc<V>>
Get the value for a key from a map.
Time: O(log n)
Examples
let map = map!{123 => "lol"}; assert_eq!( map.get(&123), Some(Arc::new("lol")) );
fn get_or<RV>(&self, k: &K, default: RV) -> Arc<V> where
Arc<V>: From<RV>,
Arc<V>: From<RV>,
Get the value for a key from a map, or a default value if the key isn't in the map.
Time: O(log n)
Examples
let map = map!{123 => "lol"}; assert_eq!( map.get_or(&123, "hi"), Arc::new("lol") ); assert_eq!( map.get_or(&321, "hi"), Arc::new("hi") );
fn contains_key(&self, k: &K) -> bool
Test for the presence of a key in a map.
Time: O(log n)
Examples
let map = map!{123 => "lol"}; assert!( map.contains_key(&123) ); assert!( !map.contains_key(&321) );
fn insert<RK, RV>(&self, k: RK, v: RV) -> Self where
Arc<K>: From<RK>,
Arc<V>: From<RV>,
Arc<K>: From<RK>,
Arc<V>: From<RV>,
Construct a new map by inserting a key/value mapping into a map.
If the map already has a mapping for the given key, the previous value is overwritten.
Time: O(log n)
Examples
let map = map!{}; assert_eq!( map.insert(123, "123"), map!{123 => "123"} );
fn insert_with<RK, RV, F>(self, k: RK, v: RV, f: F) -> Self where
Arc<K>: From<RK>,
Arc<V>: From<RV>,
F: Fn(Arc<V>, Arc<V>) -> Arc<V>,
Arc<K>: From<RK>,
Arc<V>: From<RV>,
F: Fn(Arc<V>, Arc<V>) -> Arc<V>,
Construct a new map by inserting a key/value mapping into a map.
If the map already has a mapping for the given key, we call the provided function with the old value and the new value, and insert the result as the new value.
Time: O(log n)
fn insert_with_key<RK, RV, F>(self, k: RK, v: RV, f: F) -> Self where
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
Arc<K>: From<RK>,
Arc<V>: From<RV>,
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
Arc<K>: From<RK>,
Arc<V>: From<RV>,
Construct a new map by inserting a key/value mapping into a map.
If the map already has a mapping for the given key, we call the provided function with the key, the old value and the new value, and insert the result as the new value.
Time: O(log n)
fn insert_lookup_with_key<RK, RV, F>(
self,
k: RK,
v: RV,
f: F
) -> (Option<Arc<V>>, Self) where
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
Arc<K>: From<RK>,
Arc<V>: From<RV>,
self,
k: RK,
v: RV,
f: F
) -> (Option<Arc<V>>, Self) where
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
Arc<K>: From<RK>,
Arc<V>: From<RV>,
Construct a new map by inserting a key/value mapping into a map, returning the old value for the key as well as the new map.
If the map already has a mapping for the given key, we call the provided function with the key, the old value and the new value, and insert the result as the new value.
Time: O(log n)
fn update<F>(&self, k: &K, f: F) -> Self where
F: Fn(Arc<V>) -> Option<Arc<V>>,
F: Fn(Arc<V>) -> Option<Arc<V>>,
Update the value for a given key by calling a function with the current value and overwriting it with the function's return value.
Time: O(log n)
fn update_with_key<F>(&self, k: &K, f: F) -> Self where
F: Fn(Arc<K>, Arc<V>) -> Option<Arc<V>>,
F: Fn(Arc<K>, Arc<V>) -> Option<Arc<V>>,
Update the value for a given key by calling a function with the key and the current value and overwriting it with the function's return value.
Time: O(log n)
fn update_lookup_with_key<F>(&self, k: &K, f: F) -> (Option<Arc<V>>, Self) where
F: Fn(Arc<K>, Arc<V>) -> Option<Arc<V>>,
F: Fn(Arc<K>, Arc<V>) -> Option<Arc<V>>,
Update the value for a given key by calling a function with the key and the current value and overwriting it with the function's return value.
If the key was not in the map, the function is never called and the map is left unchanged.
Return a tuple of the old value, if there was one, and the new map.
Time: O(log n)
fn alter<RK, F>(&self, f: F, k: RK) -> Self where
F: Fn(Option<Arc<V>>) -> Option<Arc<V>>,
Arc<K>: From<RK>,
F: Fn(Option<Arc<V>>) -> Option<Arc<V>>,
Arc<K>: From<RK>,
Update the value for a given key by calling a function with the current value and overwriting it with the function's return value.
This is like the update
method, except with more control: the function gets
an Option<V>
and returns the same, so that it can decide to delete a mapping
instead of updating the value, and decide what to do if the key isn't in the map.
Time: O(log n)
fn remove(&self, k: &K) -> Self
Remove a key/value pair from a list, if it exists.
Time: O(log n)
fn pop(&self, k: &K) -> Option<(Arc<V>, Self)>
Remove a key/value pair from a list, if it exists, and return the removed value as well as the updated list.
Time: O(log n)
fn pop_with_key(&self, k: &K) -> Option<(Arc<K>, Arc<V>, Self)>
Remove a key/value pair from a list, if it exists, and return the removed key and value as well as the updated list.
Time: O(log n)
fn union(&self, other: &Self) -> Self
Construct the union of two maps, keeping the values in the current map when keys exist in both maps.
fn union_with<F, RM>(&self, other: RM, f: F) -> Self where
F: Fn(Arc<V>, Arc<V>) -> Arc<V>,
RM: Borrow<Self>,
F: Fn(Arc<V>, Arc<V>) -> Arc<V>,
RM: Borrow<Self>,
Construct the union of two maps, using a function to decide what to do with the value when a key is in both maps.
fn union_with_key<F, RM>(&self, other: RM, f: F) -> Self where
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
RM: Borrow<Self>,
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
RM: Borrow<Self>,
Construct the union of two maps, using a function to decide what to do with the value when a key is in both maps. The function receives the key as well as both values.
fn unions<I>(i: I) -> Self where
I: IntoIterator<Item = Self>,
I: IntoIterator<Item = Self>,
Construct the union of a sequence of maps, selecting the value of the leftmost when a key appears in more than one map.
fn unions_with<I, F>(i: I, f: F) -> Self where
I: IntoIterator<Item = Self>,
F: Fn(Arc<V>, Arc<V>) -> Arc<V>,
I: IntoIterator<Item = Self>,
F: Fn(Arc<V>, Arc<V>) -> Arc<V>,
Construct the union of a sequence of maps, using a function to decide what to do with the value when a key is in more than one map.
fn unions_with_key<I, F>(i: I, f: F) -> Self where
I: IntoIterator<Item = Self>,
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
I: IntoIterator<Item = Self>,
F: Fn(Arc<K>, Arc<V>, Arc<V>) -> Arc<V>,
Construct the union of a sequence of maps, using a function to decide what to do with the value when a key is in more than one map. The function receives the key as well as both values.
fn difference<B, RM>(&self, other: RM) -> Self where
RM: Borrow<Map<K, B>>,
RM: Borrow<Map<K, B>>,
Construct the difference between two maps by discarding keys which occur in both maps.
fn difference_with<B, RM, F>(&self, other: RM, f: F) -> Self where
F: Fn(Arc<V>, Arc<B>) -> Option<Arc<V>>,
RM: Borrow<Map<K, B>>,
F: Fn(Arc<V>, Arc<B>) -> Option<Arc<V>>,
RM: Borrow<Map<K, B>>,
Construct the difference between two maps by using a function to decide what to do if a key occurs in both.
fn difference_with_key<B, RM, F>(&self, other: RM, f: F) -> Self where
F: Fn(Arc<K>, Arc<V>, Arc<B>) -> Option<Arc<V>>,
RM: Borrow<Map<K, B>>,
F: Fn(Arc<K>, Arc<V>, Arc<B>) -> Option<Arc<V>>,
RM: Borrow<Map<K, B>>,
Construct the difference between two maps by using a function to decide what to do if a key occurs in both. The function receives the key as well as both values.
fn intersection<B, RM>(&self, other: RM) -> Self where
RM: Borrow<Map<K, B>>,
RM: Borrow<Map<K, B>>,
Construct the intersection of two maps, keeping the values from the current map.
fn intersection_with<B, C, RM, F>(&self, other: RM, f: F) -> Map<K, C> where
F: Fn(Arc<V>, Arc<B>) -> Arc<C>,
RM: Borrow<Map<K, B>>,
F: Fn(Arc<V>, Arc<B>) -> Arc<C>,
RM: Borrow<Map<K, B>>,
Construct the intersection of two maps, calling a function with both values for each key and using the result as the value for the key.
fn intersection_with_key<B, C, RM, F>(&self, other: RM, f: F) -> Map<K, C> where
F: Fn(Arc<K>, Arc<V>, Arc<B>) -> Arc<C>,
RM: Borrow<Map<K, B>>,
F: Fn(Arc<K>, Arc<V>, Arc<B>) -> Arc<C>,
RM: Borrow<Map<K, B>>,
Construct the intersection of two maps, calling a function with the key and both values for each key and using the result as the value for the key.
fn merge_with_key<B, C, RM, FC, F1, F2>(
&self,
other: RM,
combine: FC,
only1: F1,
only2: F2
) -> Map<K, C> where
RM: Borrow<Map<K, B>>,
FC: Fn(Arc<K>, Arc<V>, Arc<B>) -> Option<Arc<C>>,
F1: Fn(Self) -> Map<K, C>,
F2: Fn(Map<K, B>) -> Map<K, C>,
&self,
other: RM,
combine: FC,
only1: F1,
only2: F2
) -> Map<K, C> where
RM: Borrow<Map<K, B>>,
FC: Fn(Arc<K>, Arc<V>, Arc<B>) -> Option<Arc<C>>,
F1: Fn(Self) -> Map<K, C>,
F2: Fn(Map<K, B>) -> Map<K, C>,
Merge two maps.
First, we call the combine
function for each key/value pair which exists in both maps,
updating the value or discarding it according to the function's return value.
The only1
and only2
functions are called with the key/value pairs which are only in
the first and the second list respectively. The results of these are then merged with
the result of the first operation.
fn split(&self, split: &K) -> (Self, Self)
Split a map into two, with the left hand map containing keys which are smaller
than split
, and the right hand map containing keys which are larger than split
.
The split
mapping is discarded.
fn split_lookup(&self, split: &K) -> (Self, Option<Arc<V>>, Self)
Split a map into two, with the left hand map containing keys which are smaller
than split
, and the right hand map containing keys which are larger than split
.
Returns both the two maps and the value of split
.
fn is_submap_by<B, RM, F>(&self, other: RM, cmp: F) -> bool where
F: Fn(Arc<V>, Arc<B>) -> bool,
RM: Borrow<Map<K, B>>,
F: Fn(Arc<V>, Arc<B>) -> bool,
RM: Borrow<Map<K, B>>,
Test whether a map is a submap of another map, meaning that all keys in our map must also be in the other map, with the same values.
Use the provided function to decide whether values are equal.
fn is_proper_submap_by<B, RM, F>(&self, other: RM, cmp: F) -> bool where
F: Fn(Arc<V>, Arc<B>) -> bool,
RM: Borrow<Map<K, B>>,
F: Fn(Arc<V>, Arc<B>) -> bool,
RM: Borrow<Map<K, B>>,
Test whether a map is a proper submap of another map, meaning that all keys in our map must also be in the other map, with the same values. To be a proper submap, ours must also contain fewer keys than the other map.
Use the provided function to decide whether values are equal.
fn take(&self, n: usize) -> Self
Construct a map with only the n
smallest keys from a given map.
fn drop(&self, n: usize) -> Self
Construct a map with the n
smallest keys removed from a given map.
fn pop_min(&self) -> (Option<Arc<V>>, Self)
Remove the smallest key from a map, and return its value as well as the updated map.
fn pop_min_with_key(&self) -> (Option<(Arc<K>, Arc<V>)>, Self)
Remove the smallest key from a map, and return that key, its value as well as the updated map.
fn pop_max(&self) -> (Option<Arc<V>>, Self)
Remove the largest key from a map, and return its value as well as the updated map.
fn pop_max_with_key(&self) -> (Option<(Arc<K>, Arc<V>)>, Self)
Remove the largest key from a map, and return that key, its value as well as the updated map.
fn delete_min(&self) -> Self
Discard the smallest key from a map, returning the updated map.
fn delete_max(&self) -> Self
Discard the largest key from a map, returning the updated map.
impl<K: Ord, V: PartialEq> Map<K, V>
[src]
fn is_submap<RM>(&self, other: RM) -> bool where
RM: Borrow<Self>,
RM: Borrow<Self>,
Test whether a map is a submap of another map, meaning that all keys in our map must also be in the other map, with the same values.
fn is_proper_submap<RM>(&self, other: RM) -> bool where
RM: Borrow<Self>,
RM: Borrow<Self>,
Test whether a map is a proper submap of another map, meaning that all keys in our map must also be in the other map, with the same values. To be a proper submap, ours must also contain fewer keys than the other map.
Trait Implementations
impl<K, V> Clone for Map<K, V>
[src]
fn clone(&self) -> Self
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<K: PartialEq, V: PartialEq> PartialEq for Map<K, V>
[src]
fn eq(&self, other: &Self) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Rhs) -> bool
1.0.0
This method tests for !=
.
impl<K: Eq, V: Eq> Eq for Map<K, V>
[src]
impl<K: PartialOrd, V: PartialOrd> PartialOrd for Map<K, V>
[src]
fn partial_cmp(&self, other: &Self) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
fn lt(&self, other: &Rhs) -> bool
1.0.0
This method tests less than (for self
and other
) and is used by the <
operator. Read more
fn le(&self, other: &Rhs) -> bool
1.0.0
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
fn gt(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than (for self
and other
) and is used by the >
operator. Read more
fn ge(&self, other: &Rhs) -> bool
1.0.0
This method tests greater than or equal to (for self
and other
) and is used by the >=
operator. Read more
impl<K: Ord, V: Ord> Ord for Map<K, V>
[src]
fn cmp(&self, other: &Self) -> Ordering
This method returns an Ordering
between self
and other
. Read more
impl<K: Ord + Hash, V: Hash> Hash for Map<K, V>
[src]
fn hash<H>(&self, state: &mut H) where
H: Hasher,
H: Hasher,
Feeds this value into the given [Hasher
]. Read more
fn hash_slice<H>(data: &[Self], state: &mut H) where
H: Hasher,
1.3.0
H: Hasher,
Feeds a slice of this type into the given [Hasher
]. Read more
impl<K, V> Default for Map<K, V>
[src]
impl<'a, K: Ord, V> Add for &'a Map<K, V>
[src]
type Output = Map<K, V>
The resulting type after applying the +
operator
fn add(self, other: Self) -> Self::Output
The method for the +
operator
impl<K: Debug, V: Debug> Debug for Map<K, V>
[src]
impl<K: Ord, V> FromIterator<(K, V)> for Map<K, V>
[src]
fn from_iter<T>(i: T) -> Self where
T: IntoIterator<Item = (K, V)>,
T: IntoIterator<Item = (K, V)>,
Creates a value from an iterator. Read more
impl<K: Ord, V> FromIterator<(Arc<K>, Arc<V>)> for Map<K, V>
[src]
fn from_iter<T>(i: T) -> Self where
T: IntoIterator<Item = (Arc<K>, Arc<V>)>,
T: IntoIterator<Item = (Arc<K>, Arc<V>)>,
Creates a value from an iterator. Read more
impl<'a, K, V> IntoIterator for &'a Map<K, V>
[src]
type Item = (Arc<K>, Arc<V>)
The type of the elements being iterated over.
type IntoIter = Iter<K, V>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Self::IntoIter
Creates an iterator from a value. Read more
impl<K, V> IntoIterator for Map<K, V>
[src]
type Item = (Arc<K>, Arc<V>)
The type of the elements being iterated over.
type IntoIter = Iter<K, V>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Self::IntoIter
Creates an iterator from a value. Read more
impl<'a, K: Ord, V: Clone, RK, RV> From<&'a [(RK, RV)]> for Map<K, V> where
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,
[src]
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,
impl<K: Ord, V, RK, RV> From<Vec<(RK, RV)>> for Map<K, V> where
Arc<K>: From<RK>,
Arc<V>: From<RV>,
[src]
Arc<K>: From<RK>,
Arc<V>: From<RV>,
impl<'a, K: Ord, V, RK, RV> From<&'a Vec<(RK, RV)>> for Map<K, V> where
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,
[src]
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,
impl<K: Ord, V, RK: Eq + Hash, RV> From<HashMap<RK, RV>> for Map<K, V> where
Arc<K>: From<RK>,
Arc<V>: From<RV>,
[src]
Arc<K>: From<RK>,
Arc<V>: From<RV>,
impl<'a, K: Ord, V, RK: Eq + Hash, RV> From<&'a HashMap<RK, RV>> for Map<K, V> where
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,
[src]
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,
impl<K: Ord, V, RK, RV> From<BTreeMap<RK, RV>> for Map<K, V> where
Arc<K>: From<RK>,
Arc<V>: From<RV>,
[src]
Arc<K>: From<RK>,
Arc<V>: From<RV>,
impl<'a, K: Ord, V, RK, RV> From<&'a BTreeMap<RK, RV>> for Map<K, V> where
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,
[src]
Arc<K>: From<&'a RK>,
Arc<V>: From<&'a RV>,