Struct TreeMap

pub struct TreeMap<K, V, H = Sha256>
where
    K: BorshSerialize + Ord,
    V: BorshSerialize,
    H: ToKey,
{ /* private fields */ }

TreeMap based on AVL-tree

Runtime complexity (worst case):

• get/contains_key: O(1) - LookupMap lookup
• insert/remove: O(log(N))
• min/max: O(log(N))
• above/below: O(log(N))
• range of K elements: O(Klog(N))

Implementations

impl<K, V> TreeMap<K, V, Sha256>

where K: BorshSerialize + Ord, V: BorshSerialize,

pub fn new<S>(prefix: S) -> Self

where 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.

impl<K, V, H> TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize, H: ToKey,

pub fn with_hasher<S>(prefix: S) -> Self

where S: IntoStorageKey,

pub fn len(&self) -> u32

Return the amount of elements inside of the map.

pub fn is_empty(&self) -> bool

Returns true if there are no elements inside of the map.

impl<K, V, H> TreeMap<K, V, H>

where K: Ord + Clone + BorshSerialize, V: BorshSerialize + BorshDeserialize, H: ToKey,

pub fn clear(&mut self)

where K: BorshDeserialize,

Clears the map, removing all key-value pairs. Keeps the allocated memory for reuse.

pub fn contains_key<Q>(&self, k: &Q) -> bool

where K: Borrow<Q>, Q: BorshSerialize + ToOwned<Owned = K> + 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 BorshSerialize and ToOwned<Owned = K> on the borrowed form must match those for the key type.

pub fn get<Q>(&self, k: &Q) -> Option<&V>

where K: Borrow<Q>, Q: BorshSerialize + ToOwned<Owned = K> + ?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 BorshSerialize and ToOwned<Owned = K> on the borrowed form must match those for the key type.

pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>

where K: Borrow<Q> + BorshDeserialize, Q: BorshSerialize + ToOwned<Owned = K> + 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 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);

pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>

where K: Borrow<Q>, Q: BorshSerialize + ToOwned<Owned = K> + ?Sized,

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.

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.

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q> + BorshDeserialize, Q: BorshSerialize + ToOwned<Owned = K> + 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 BorshSerialize and ToOwned<Owned = K> on the borrowed form must match those for the key type.

impl<K, V, H> TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize, H: ToKey,

pub fn iter(&self) -> Iter<'_, K, V, H>

where K: BorshDeserialize,

An iterator visiting all key-value pairs in arbitrary order. The iterator element type is (&'a K, &'a V).

pub fn iter_mut(&mut self) -> IterMut<'_, K, V, H>

where K: BorshDeserialize,

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).

pub fn keys(&self) -> Keys<'_, K>

where K: BorshDeserialize,

An iterator visiting all keys in arbitrary order. The iterator element type is &'a K.

pub fn values(&self) -> Values<'_, K, V, H>

where K: BorshDeserialize,

An iterator visiting all values in arbitrary order. The iterator element type is &'a V.

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, H>

where K: BorshDeserialize,

A mutable iterator visiting all values in arbitrary order. The iterator element type is &'a mut V.

pub fn range<'a, R, Q>(&'a self, range: R) -> Range<'a, K, V, H>

where K: BorshDeserialize + Borrow<Q>, Q: ?Sized + Ord + 'a, R: RangeBounds<Q> + 'a,

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());

pub fn range_mut<R, Q>(&mut self, range: R) -> RangeMut<'_, K, V, H>

where K: BorshDeserialize + Borrow<Q>, Q: ?Sized + Ord, R: RangeBounds<Q>,

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);
}

impl<K, V, H> TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize + BorshDeserialize, H: ToKey,

pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>

where K: Borrow<Q> + BorshDeserialize + Clone, Q: BorshSerialize + ToOwned<Owned = K> + Eq + PartialOrd + ?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 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);

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);

impl<K, V, H> TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize, H: ToKey,

pub fn flush(&mut self)

Flushes the intermediate values of the map before this is called when the structure is Droped. This will write all modified values to storage but keep all cached values in memory.

Trait Implementations

impl<K, V, H> BorshDeserialize for TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize, H: ToKey,

fn deserialize_reader<__R: Read>(reader: &mut __R) -> Result<Self, Error>

fn deserialize(buf: &mut &[u8]) -> Result<Self, Error>

Deserializes this instance from a given slice of bytes. Updates the buffer to point at the remaining bytes.

fn try_from_slice(v: &[u8]) -> Result<Self, Error>

Deserialize this instance from a slice of bytes.

fn try_from_reader<R>(reader: &mut R) -> Result<Self, Error>

where R: Read,

impl<K, V, H> BorshSchema for TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize, H: ToKey,

fn declaration() -> Declaration

Get the name of the type without brackets.

fn add_definitions_recursively( definitions: &mut BTreeMap<Declaration, Definition>, )

Recursively, using DFS, add type definitions required for this type. Type definition partially explains how to serialize/deserialize a type.

impl<K, V, H> BorshSerialize for TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize, H: ToKey,

fn serialize<__W: Write>(&self, writer: &mut __W) -> Result<(), Error>

impl<K, V, H> Debug for TreeMap<K, V, H>

where K: Ord + Clone + Debug + BorshSerialize + BorshDeserialize, V: Debug + BorshSerialize + BorshDeserialize, H: ToKey,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V, H> Drop for TreeMap<K, V, H>

where K: BorshSerialize + Ord, V: BorshSerialize, H: ToKey,

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V, H> Extend<(K, V)> for TreeMap<K, V, H>

where K: BorshSerialize + Ord + BorshDeserialize + Clone, V: BorshSerialize + BorshDeserialize, H: ToKey,

fn extend<I>(&mut self, iter: I)

where I: IntoIterator<Item = (K, V)>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, H, Q> Index<&Q> for TreeMap<K, V, H>

where K: BorshSerialize + Ord + Clone + Borrow<Q>, V: BorshSerialize + BorshDeserialize, H: ToKey, Q: BorshSerialize + ToOwned<Owned = K> + ?Sized,

fn index(&self, index: &Q) -> &Self::Output

Returns reference to value corresponding to key.

Panics

Panics if the key does not exist in the map

type Output = V

The returned type after indexing.

impl<'a, K, V, H> IntoIterator for &'a TreeMap<K, V, H>

where K: BorshSerialize + Ord + BorshDeserialize + Clone, V: BorshSerialize + BorshDeserialize, H: ToKey,

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V, H>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V, H> IntoIterator for &'a mut TreeMap<K, V, H>

where K: BorshSerialize + Ord + BorshDeserialize + Clone, V: BorshSerialize + BorshDeserialize, H: ToKey,

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V, H>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.