Struct BTreeMap

pub struct BTreeMap<K, V, M>
where
    K: Storable + Ord + Clone,
    V: Storable,
    M: Memory,
{ /* private fields */ }

A B-Tree map implementation that stores its data into a designated memory.

Memory Implementations

BTreeMap works with any memory implementation that satisfies the Memory trait:

• Ic0StableMemory: Stores data in the Internet Computer’s stable memory
• VectorMemory: In-memory implementation backed by a Rust Vec<u8>
• FileMemory: Persists data to disk using a file
• DefaultMemoryImpl: Default implementation that automatically selects the appropriate memory backend based on the environment:
  • Uses Ic0StableMemory when running in an Internet Computer canister (wasm32 target)
  • Falls back to VectorMemory in other environments (like tests or non-IC contexts)

For almost all use cases, DefaultMemoryImpl is recommended as it provides the right implementation based on the runtime context.

Examples

Basic Usage with a Single BTreeMap

use ic_stable_structures::{BTreeMap, DefaultMemoryImpl};
let mut map: BTreeMap<u64, String, _> = BTreeMap::init(DefaultMemoryImpl::default());

map.insert(1, "hello".to_string());

Multiple BTreeMaps and Memory Management

Important: Each stable structure requires its own designated memory region. Attempting to initialize multiple structures with the same memory will lead to data corruption.

What NOT to do:

use ic_stable_structures::{BTreeMap, DefaultMemoryImpl};

// ERROR: Using the same memory for multiple BTreeMaps will corrupt data
let mut map_1: BTreeMap<u64, String, _> = BTreeMap::init(DefaultMemoryImpl::default());
let mut map_2: BTreeMap<u64, String, _> = BTreeMap::init(DefaultMemoryImpl::default());

map_1.insert(1, "two".to_string());
map_2.insert(1, "three".to_string());
// This assertion would fail: changes to map_2 corrupt map_1's data
assert_eq!(map_1.get(&1), Some("two".to_string()));

Correct approach using MemoryManager:

use ic_stable_structures::{
   memory_manager::{MemoryId, MemoryManager},
   BTreeMap, DefaultMemoryImpl,
};

// Initialize the memory manager with a single memory
let memory_manager = MemoryManager::init(DefaultMemoryImpl::default());

// Get separate virtual memories for each BTreeMap
let mut map_1: BTreeMap<u64, String, _> = BTreeMap::init(memory_manager.get(MemoryId::new(0)));
let mut map_2: BTreeMap<u64, String, _> = BTreeMap::init(memory_manager.get(MemoryId::new(1)));

map_1.insert(1, "two".to_string());
map_2.insert(1, "three".to_string());
// Now this works as expected
assert_eq!(map_1.get(&1), Some("two".to_string()));

The MemoryManager creates up to 255 virtual memories from a single contiguous memory, allowing multiple stable structures to safely coexist.

For complete examples of using multiple stable structures in a production environment, see the Quick Start example.

Custom Types

You can store custom structs in a BTreeMap by implementing the Storable trait:

use ic_stable_structures::{BTreeMap, DefaultMemoryImpl, Storable, storable::Bound};
use std::borrow::Cow;

#[derive(Debug, PartialEq)]
struct User {
    id: u64,
    name: String,
}

impl Storable for User {
    fn to_bytes(&self) -> Cow<[u8]> {
        let mut bytes = Vec::new();
        // TODO: Convert your struct to bytes...
        Cow::Owned(bytes)
    }

    fn from_bytes(bytes: Cow<[u8]>) -> Self {
        // TODO: Convert bytes back to your struct
        let (id, name) = (0, "".to_string());
        User { id, name }
    }

    // Types can be bounded or unbounded:
    // - Use Bound::Unbounded if the size can vary or isn't known in advance (recommended for most cases)
    // - Use Bound::Bounded if you know the maximum size and want memory optimization
    const BOUND: Bound = Bound::Unbounded;
}

// Now you can use your custom type in a BTreeMap
let mut map: BTreeMap<u64, User, _> = BTreeMap::init(DefaultMemoryImpl::default());

let user = User { id: 1, name: "Alice".to_string() };
map.insert(1, user);

// Retrieving the custom type
if let Some(user) = map.get(&1) {
    println!("Found user: {}", user.name);
}

Bounded vs Unbounded Types

When implementing Storable, you must specify whether your type is bounded or unbounded:

• Unbounded (Bound::Unbounded):

  • Use when your type’s serialized size can vary or has no fixed maximum
  • Recommended for most custom types, especially those containing Strings or Vecs
  • Example: const BOUND: Bound = Bound::Unbounded;

• Bounded (Bound::Bounded{ max_size, is_fixed_size }):

  • Use when you know the maximum serialized size of your type
  • Enables memory optimizations in the BTreeMap
  • Example: const BOUND: Bound = Bound::Bounded { max_size: 100, is_fixed_size: false };
  • For types with truly fixed size (like primitive types), set is_fixed_size: true

If unsure, use Bound::Unbounded as it’s the safer choice.

Warning

Once you’ve deployed with a bounded type, you cannot increase its max_size in future versions without risking data corruption. You can, however, migrate from a bounded type to an unbounded type if needed. For evolving data structures, prefer Bound::Unbounded.

Implementations

impl<K, V, M> BTreeMap<K, V, M>

where K: Storable + Ord + Clone, V: Storable, M: Memory,

pub fn init(memory: M) -> Self

Initializes a BTreeMap.

If the memory provided already contains a BTreeMap, then that map is loaded. Otherwise, a new BTreeMap instance is created.

pub fn new(memory: M) -> Self

Creates a new instance a BTreeMap.

The given memory is assumed to be exclusively reserved for this data structure and that it starts at address zero. Typically memory will be an instance of RestrictedMemory.

When initialized, the data structure has the following memory layout:

| BTreeHeader | Allocator | … free memory for nodes |

See Allocator for more details on its own memory layout.

pub fn load(memory: M) -> Self

Loads the map from memory.

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

Inserts a key-value pair into the map.

The previous value of the key, if present, is returned.

PRECONDITION: key.to_bytes().len() <= max_size(Key) value.to_bytes().len() <= max_size(Value)

pub fn get(&self, key: &K) -> Option<V>

Returns the value for the given key, if it exists.

pub fn contains_key(&self, key: &K) -> bool

Returns true if the key exists.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn len(&self) -> u64

Returns the number of elements in the map.

pub fn into_memory(self) -> M

Returns the underlying memory.

pub fn clear(self) -> Self

👎Deprecated since 0.6.3: please use clear_new instead

Removes all elements from the map.

pub fn clear_new(&mut self)

Removes all elements from the map.

pub fn first_key_value(&self) -> Option<(K, V)>

Returns the first key-value pair in the map. The key in this pair is the minimum key in the map.

pub fn last_key_value(&self) -> Option<(K, V)>

Returns the last key-value pair in the map. The key in this pair is the maximum key in the map.

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

Removes a key from the map, returning the previous value at the key if it exists.

pub fn pop_last(&mut self) -> Option<(K, V)>

Removes and returns the last element in the map. The key of this element is the maximum key that was in the map

pub fn pop_first(&mut self) -> Option<(K, V)>

Removes and returns the first element in the map. The key of this element is the minimum key that was in the map

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

Returns an iterator over the entries of the map, sorted by key.

Example

use ic_stable_structures::{BTreeMap, DefaultMemoryImpl};
let mut map: BTreeMap<u64, String, _> = BTreeMap::init(DefaultMemoryImpl::default());

map.insert(1, "one".to_string());
map.insert(2, "two".to_string());

for (key, value) in map.iter() {
    println!("{}: {}", key, value);
}

pub fn range(&self, key_range: impl RangeBounds<K>) -> Iter<'_, K, V, M>

Returns an iterator over the entries in the map where keys belong to the specified range.

Example

use ic_stable_structures::{BTreeMap, DefaultMemoryImpl};
use std::ops::Bound;

let mut map: BTreeMap<u64, String, _> = BTreeMap::init(DefaultMemoryImpl::default());
map.insert(1, "one".to_string());
map.insert(2, "two".to_string());
map.insert(3, "three".to_string());

// Get entries with keys between 1 and 3 (inclusive)
for (key, value) in map.range((Bound::Included(1), Bound::Included(3))) {
    println!("{}: {}", key, value);
}

pub fn iter_upper_bound(&self, bound: &K) -> Iter<'_, K, V, M>

Returns an iterator pointing to the first element below the given bound. Returns an empty iterator if there are no keys below the given bound.

pub fn keys(&self) -> KeysIter<'_, K, V, M>

Returns an iterator over the keys of the map.

pub fn keys_range( &self, key_range: impl RangeBounds<K>, ) -> KeysIter<'_, K, V, M>

Returns an iterator over the keys of the map which belong to the specified range.

pub fn values(&self) -> ValuesIter<'_, K, V, M>

Returns an iterator over the values of the map, sorted by key.

pub fn values_range( &self, key_range: impl RangeBounds<K>, ) -> ValuesIter<'_, K, V, M>

Returns an iterator over the values of the map where keys belong to the specified range.