pub struct TreeMap<K, V, H = Sha256>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,{ /* private fields */ }
Expand description
TreeMap based on AVL-tree
Runtime complexity (worst case):
get
/contains_key
: O(1) - LookupMap lookupinsert
/remove
: O(log(N))min
/max
: O(log(N))above
/below
: O(log(N))range
of K elements: O(Klog(N))
Implementations
sourceimpl<K, V> TreeMap<K, V, Sha256>where
K: BorshSerialize + Ord,
V: BorshSerialize,
impl<K, V> TreeMap<K, V, Sha256>where
K: BorshSerialize + Ord,
V: BorshSerialize,
sourcepub fn new<S>(prefix: S) -> Selfwhere
S: IntoStorageKey,
pub fn new<S>(prefix: S) -> Selfwhere
S: IntoStorageKey,
Initialize new TreeMap
with the prefix provided.
This prefix can be anything that implements IntoStorageKey
. The prefix is used when
storing and looking up values in storage to ensure no collisions with other collections.
sourceimpl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
impl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
pub fn with_hasher<S>(prefix: S) -> Selfwhere
S: IntoStorageKey,
sourceimpl<K, V, H> TreeMap<K, V, H>where
K: Ord + Clone + BorshSerialize,
V: BorshSerialize + BorshDeserialize,
H: ToKey,
impl<K, V, H> TreeMap<K, V, H>where
K: Ord + Clone + BorshSerialize,
V: BorshSerialize + BorshDeserialize,
H: ToKey,
sourcepub fn clear(&mut self)where
K: BorshDeserialize,
pub fn clear(&mut self)where
K: BorshDeserialize,
Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse.
sourcepub fn contains_key<Q: ?Sized>(&self, k: &Q) -> boolwhere
K: Borrow<Q>,
Q: BorshSerialize + ToOwned<Owned = K> + Ord,
pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> boolwhere
K: Borrow<Q>,
Q: BorshSerialize + ToOwned<Owned = K> + 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
BorshSerialize
and ToOwned<Owned = K>
on the borrowed form must match
those for the key type.
sourcepub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: BorshSerialize + ToOwned<Owned = K>,
pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>where
K: Borrow<Q>,
Q: BorshSerialize + ToOwned<Owned = K>,
Returns a reference to the value corresponding to the key.
The key may be any borrowed form of the map’s key type, but
BorshSerialize
and ToOwned<Owned = K>
on the borrowed form must match
those for the key type.
sourcepub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>where
K: Borrow<Q> + BorshDeserialize,
Q: BorshSerialize + ToOwned<Owned = K> + Ord,
pub fn get_key_value<Q: ?Sized>(&self, k: &Q) -> Option<(&K, &V)>where
K: Borrow<Q> + BorshDeserialize,
Q: BorshSerialize + ToOwned<Owned = K> + Ord,
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 near_sdk::store::TreeMap;
let mut map = TreeMap::new(b"t");
map.insert(1, "a".to_string());
assert_eq!(map.get_key_value(&1), Some((&1, &"a".to_string())));
assert_eq!(map.get_key_value(&2), None);
sourcepub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: BorshSerialize + ToOwned<Owned = K>,
pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>where
K: Borrow<Q>,
Q: BorshSerialize + ToOwned<Owned = K>,
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
BorshSerialize
and ToOwned<Owned = K>
on the borrowed form must match
those for the key type.
sourcepub fn insert(&mut self, key: K, value: V) -> Option<V>where
K: Clone + BorshDeserialize,
pub fn insert(&mut self, key: K, value: V) -> Option<V>where
K: Clone + BorshDeserialize,
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.
sourcepub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>where
K: Borrow<Q> + BorshDeserialize,
Q: BorshSerialize + ToOwned<Owned = K> + Ord,
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>where
K: Borrow<Q> + BorshDeserialize,
Q: BorshSerialize + ToOwned<Owned = K> + 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
BorshSerialize
and ToOwned<Owned = K>
on the borrowed form must match
those for the key type.
sourceimpl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
impl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
sourcepub fn iter(&self) -> Iter<'_, K, V, H>ⓘNotable traits for Iter<'a, K, V, H>impl<'a, K, V, H> Iterator for Iter<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a V);
where
K: BorshDeserialize,
pub fn iter(&self) -> Iter<'_, K, V, H>ⓘNotable traits for Iter<'a, K, V, H>impl<'a, K, V, H> Iterator for Iter<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a V);
where
K: BorshDeserialize,
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a V);
An iterator visiting all key-value pairs in arbitrary order.
The iterator element type is (&'a K, &'a V)
.
sourcepub fn iter_mut(&mut self) -> IterMut<'_, K, V, H>ⓘNotable traits for IterMut<'a, K, V, H>impl<'a, K, V, H> Iterator for IterMut<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a mut V);
where
K: BorshDeserialize,
pub fn iter_mut(&mut self) -> IterMut<'_, K, V, H>ⓘNotable traits for IterMut<'a, K, V, H>impl<'a, K, V, H> Iterator for IterMut<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a mut V);
where
K: BorshDeserialize,
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a mut V);
An iterator visiting all key-value pairs in arbitrary order,
with exclusive references to the values.
The iterator element type is (&'a K, &'a mut V)
.
sourcepub fn keys(&self) -> Keys<'_, K>ⓘNotable traits for Keys<'a, K>impl<'a, K> Iterator for Keys<'a, K>where
K: BorshSerialize + BorshDeserialize + Ord, type Item = &'a K;
where
K: BorshDeserialize,
pub fn keys(&self) -> Keys<'_, K>ⓘNotable traits for Keys<'a, K>impl<'a, K> Iterator for Keys<'a, K>where
K: BorshSerialize + BorshDeserialize + Ord, type Item = &'a K;
where
K: BorshDeserialize,
K: BorshSerialize + BorshDeserialize + Ord, type Item = &'a K;
An iterator visiting all keys in arbitrary order.
The iterator element type is &'a K
.
sourcepub fn values(&self) -> Values<'_, K, V, H>ⓘNotable traits for Values<'a, K, V, H>impl<'a, K, V, H> Iterator for Values<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = &'a V;
where
K: BorshDeserialize,
pub fn values(&self) -> Values<'_, K, V, H>ⓘNotable traits for Values<'a, K, V, H>impl<'a, K, V, H> Iterator for Values<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = &'a V;
where
K: BorshDeserialize,
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = &'a V;
An iterator visiting all values in arbitrary order.
The iterator element type is &'a V
.
sourcepub fn values_mut(&mut self) -> ValuesMut<'_, K, V, H>ⓘNotable traits for ValuesMut<'a, K, V, H>impl<'a, K, V, H> Iterator for ValuesMut<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = &'a mut V;
where
K: BorshDeserialize,
pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, H>ⓘNotable traits for ValuesMut<'a, K, V, H>impl<'a, K, V, H> Iterator for ValuesMut<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = &'a mut V;
where
K: BorshDeserialize,
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = &'a mut V;
A mutable iterator visiting all values in arbitrary order.
The iterator element type is &'a mut V
.
sourcepub fn range<'a, R: 'a, Q: 'a>(&'a self, range: R) -> Range<'a, K, V, H>ⓘNotable traits for Range<'a, K, V, H>impl<'a, K, V, H> Iterator for Range<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a V);
where
K: BorshDeserialize + Borrow<Q>,
Q: ?Sized + Ord,
R: RangeBounds<Q>,
pub fn range<'a, R: 'a, Q: 'a>(&'a self, range: R) -> Range<'a, K, V, H>ⓘNotable traits for Range<'a, K, V, H>impl<'a, K, V, H> Iterator for Range<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a V);
where
K: BorshDeserialize + Borrow<Q>,
Q: ?Sized + Ord,
R: RangeBounds<Q>,
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a V);
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 near_sdk::store::TreeMap;
use std::ops::Bound::Included;
let mut map = TreeMap::new(b"t");
map.insert(3, "a".to_string());
map.insert(5, "b".to_string());
map.insert(8, "c".to_string());
for (key, value) in map.range((Included(&4), Included(&8))) {
println!("{}: {}", key, value);
}
assert_eq!(Some((&5, &"b".to_string())), map.range(4..).next());
sourcepub fn range_mut<R, Q>(&mut self, range: R) -> RangeMut<'_, K, V, H>ⓘNotable traits for RangeMut<'a, K, V, H>impl<'a, K, V, H> Iterator for RangeMut<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a mut V);
where
K: BorshDeserialize + Borrow<Q>,
Q: ?Sized + Ord,
R: RangeBounds<Q>,
pub fn range_mut<R, Q>(&mut self, range: R) -> RangeMut<'_, K, V, H>ⓘNotable traits for RangeMut<'a, K, V, H>impl<'a, K, V, H> Iterator for RangeMut<'a, K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a mut V);
where
K: BorshDeserialize + Borrow<Q>,
Q: ?Sized + Ord,
R: RangeBounds<Q>,
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey, type Item = (&'a K, &'a mut V);
Constructs a mutable 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 near_sdk::store::TreeMap;
let mut map: TreeMap<i32, i32> = TreeMap::new(b"t");
map.extend([4, 6, 8, 11]
.iter()
.map(|&s| (s, 0)));
for (_, balance) in map.range_mut(6..10) {
*balance += 100;
}
for (id, balance) in &map {
println!("{} => {}", id, balance);
}
sourceimpl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize + BorshDeserialize,
H: ToKey,
impl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize + BorshDeserialize,
H: ToKey,
sourcepub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>where
K: Borrow<Q> + BorshDeserialize + Clone,
Q: BorshSerialize + ToOwned<Owned = K> + Eq + PartialOrd,
pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>where
K: Borrow<Q> + BorshDeserialize + Clone,
Q: BorshSerialize + ToOwned<Owned = K> + Eq + PartialOrd,
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
BorshSerialize
and ToOwned<Owned = K>
on the borrowed form must match
those for the key type.
Examples
use near_sdk::store::TreeMap;
let mut map = TreeMap::new(b"m");
map.insert(1, "a".to_string());
assert_eq!(map.remove(&1), Some("a".to_string()));
assert_eq!(map.remove(&1), None);
sourcepub fn entry(&mut self, key: K) -> Entry<'_, K, V>where
K: Clone,
pub fn entry(&mut self, key: K) -> Entry<'_, K, V>where
K: Clone,
Gets the given key’s corresponding entry in the map for in-place manipulation.
use near_sdk::store::TreeMap;
let mut count = TreeMap::new(b"m");
for ch in [7, 2, 4, 7, 4, 1, 7] {
let counter = count.entry(ch).or_insert(0);
*counter += 1;
}
assert_eq!(count[&4], 2);
assert_eq!(count[&7], 3);
assert_eq!(count[&1], 1);
assert_eq!(count.get(&8), None);
sourceimpl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
impl<K, V, H> TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
Trait Implementations
sourceimpl<K, V, H> BorshDeserialize for TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
impl<K, V, H> BorshDeserialize for TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
sourceimpl<K, V, H> BorshSerialize for TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
impl<K, V, H> BorshSerialize for TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
sourceimpl<K, V, H> Debug for TreeMap<K, V, H>where
K: Ord + Clone + Debug + BorshSerialize + BorshDeserialize,
V: Debug + BorshSerialize + BorshDeserialize,
H: ToKey,
impl<K, V, H> Debug for TreeMap<K, V, H>where
K: Ord + Clone + Debug + BorshSerialize + BorshDeserialize,
V: Debug + BorshSerialize + BorshDeserialize,
H: ToKey,
sourceimpl<K, V, H> Drop for TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
impl<K, V, H> Drop for TreeMap<K, V, H>where
K: BorshSerialize + Ord,
V: BorshSerialize,
H: ToKey,
sourceimpl<K, V, H> Extend<(K, V)> for TreeMap<K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey,
impl<K, V, H> Extend<(K, V)> for TreeMap<K, V, H>where
K: BorshSerialize + Ord + BorshDeserialize + Clone,
V: BorshSerialize + BorshDeserialize,
H: ToKey,
sourcefn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = (K, V)>,
fn extend<I>(&mut self, iter: I)where
I: IntoIterator<Item = (K, V)>,
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)