# Struct near_sdk::collections::TreeMap

``pub struct TreeMap<K, V> { /* private fields */ }``
Expand description

TreeMap based on AVL-tree

Runtime complexity (worst case):

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

## Implementations

Makes a new, empty TreeMap

##### Examples
``````use near_sdk::collections::TreeMap;
let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");``````

Returns the number of elements in the tree, also referred to as its size.

##### Examples
``````use near_sdk::collections::TreeMap;

let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
tree.insert(&1, &10);
tree.insert(&2, &20);
assert_eq!(tree.len(), 2);``````

Clears the tree, removing all elements.

##### Examples
``````use near_sdk::collections::TreeMap;

let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
tree.insert(&1, &10);
tree.insert(&2, &20);
tree.clear();
assert_eq!(tree.len(), 0);``````

Returns true if the map contains a given key.

##### Examples
``````use near_sdk::collections::TreeMap;

let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.contains_key(&1), false);
tree.insert(&1, &10);
assert_eq!(tree.contains_key(&1), true);``````

Returns the value corresponding to the key.

##### Examples
``````use near_sdk::collections::TreeMap;

let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.get(&1), None);
tree.insert(&1, &10);
assert_eq!(tree.get(&1), Some(10));``````

Inserts a key-value pair into the tree. If the tree did not have this key present, `None` is returned. Otherwise returns a value. Note, the keys that have the same hash value are undistinguished by the implementation.

##### Examples
``````use near_sdk::collections::TreeMap;

let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.insert(&1, &10), None);
assert_eq!(tree.insert(&1, &20), Some(10));
assert_eq!(tree.contains_key(&1), true);``````

Removes a key from the tree, returning the value at the key if the key was previously in the tree.

##### Examples
``````use near_sdk::collections::TreeMap;

let mut tree: TreeMap<u32, u32> = TreeMap::new(b"t");
assert_eq!(tree.remove(&1), None);
tree.insert(&1, &10);
assert_eq!(tree.remove(&1), Some(10));
assert_eq!(tree.contains_key(&1), false);``````

Returns the smallest stored key from the tree

Returns the largest stored key from the tree

Returns the smallest key that is strictly greater than key given as the parameter

Returns the largest key that is strictly less than key given as the parameter

Returns the smallest key that is greater or equal to key given as the parameter

##### Examples
``````use near_sdk::collections::TreeMap;

let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let vec: Vec<u32> = vec![10, 20, 30, 40, 50];

for x in vec.iter() {
map.insert(x, &1);
}

assert_eq!(map.ceil_key(&5), Some(10));
assert_eq!(map.ceil_key(&10), Some(10));
assert_eq!(map.ceil_key(&11), Some(20));
assert_eq!(map.ceil_key(&20), Some(20));
assert_eq!(map.ceil_key(&49), Some(50));
assert_eq!(map.ceil_key(&50), Some(50));
assert_eq!(map.ceil_key(&51), None);``````

Returns the largest key that is less or equal to key given as the parameter

##### Examples
``````use near_sdk::collections::TreeMap;

let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let vec: Vec<u32> = vec![10, 20, 30, 40, 50];
for x in vec.iter() {
map.insert(x, &1);
}

assert_eq!(map.floor_key(&5), None);
assert_eq!(map.floor_key(&10), Some(10));
assert_eq!(map.floor_key(&11), Some(10));
assert_eq!(map.floor_key(&20), Some(20));
assert_eq!(map.floor_key(&49), Some(40));
assert_eq!(map.floor_key(&50), Some(50));
assert_eq!(map.floor_key(&51), Some(50));``````

Iterate all entries in ascending order: min to max, both inclusive

Iterate entries in ascending order: given key (exclusive) to max (inclusive)

##### Examples
``````use near_sdk::collections::TreeMap;

let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let one: Vec<u32> = vec![10, 20, 30, 40, 50,45, 35, 25, 15, 5];
for x in &one {
map.insert(x, &42);
}
assert_eq!(
map.iter_from(29).collect::<Vec<(u32, u32)>>(),
vec![(30, 42), (35, 42), (40, 42), (45, 42), (50, 42)]
)``````

Iterate all entries in descending order: max to min, both inclusive

Iterate entries in descending order: given key (exclusive) to min (inclusive)

##### Examples
``````use near_sdk::collections::TreeMap;

let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let one: Vec<u32> = vec![10, 20, 30, 40, 50,45, 35, 25, 15, 5];
for x in &one {
map.insert(x, &42);
}
assert_eq!(
map.iter_rev_from(45).collect::<Vec<(u32, u32)>>(),
vec![(40, 42), (35, 42), (30, 42), (25, 42), (20, 42), (15, 42), (10, 42), (5, 42)]
);``````

Iterate entries in ascending order according to specified bounds.

##### Panics

Panics if range start > end. Panics if range start == end and both bounds are Excluded.

##### Examples
``````use near_sdk::collections::TreeMap;
use std::ops::Bound;

let mut map: TreeMap<u32, u32> = TreeMap::new(b"t");
let one: Vec<u32> = vec![10, 20, 30, 40, 50];
let two: Vec<u32> = vec![45, 35, 25, 15];
for x in &one {
map.insert(x, &0);
}
for x in &two {
map.insert(x, &0);
}
assert_eq!(
map.range((Bound::Included(20), Bound::Excluded(30))).collect::<Vec<(u32, u32)>>(),
vec![(20, 0), (25, 0)]
);``````

Helper function which creates a [`Vec<(K, V)>`] of all items in the `TreeMap`. This function collects elements from `TreeMap::iter`.

## Trait Implementations

Deserializes this instance from a given slice of bytes. Updates the buffer to point at the remaining bytes. Read more
Deserialize this instance from a slice of bytes.
Serialize this instance into a vector of bytes.
Formats the value using the given formatter. Read more
The type of the elements being iterated over.
Which kind of iterator are we turning this into?
Creates an iterator from a value. Read more

## Blanket Implementations

Gets the `TypeId` of `self`. Read more
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more

Returns the argument unchanged.

Calls `U::from(self)`.

That is, this conversion is whatever the implementation of `From<T> for U` chooses to do.

Should always be `Self`
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion.