Struct BTreeSet

Source

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

Expand description

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

§Overview

A BTreeSet is a “stable” set implementation based on a B-tree, designed to work directly in stable memory.

§Memory Implementations

BTreeSet 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: 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 most use cases, DefaultMemoryImpl is recommended as it provides the right implementation based on the runtime context.

§Examples

§Basic Usage

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));

set.insert(42);
assert!(set.contains(&42));
assert_eq!(set.pop_first(), Some(42));
assert!(set.is_empty());

§Range Queries

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(1);
set.insert(2);
set.insert(3);

let range: Vec<_> = set.range(2..).collect();
assert_eq!(range, vec![2, 3]);

§Custom Types

You can store custom types in a BTreeSet by implementing the Storable trait:

use ic_stable_structures::{BTreeSet, DefaultMemoryImpl, Storable};
use ic_stable_structures::memory_manager::{MemoryId, MemoryManager};
use std::borrow::Cow;

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
struct CustomType {
    id: u64,
}

impl Storable for CustomType {
    fn to_bytes(&self) -> Cow<'_, [u8]> {
        Cow::Owned(self.id.to_le_bytes().to_vec())
    }

    fn into_bytes(self) -> Vec<u8> {
        self.id.to_le_bytes().to_vec()
    }

    fn from_bytes(bytes: Cow<[u8]>) -> Self {
        let id = u64::from_le_bytes(bytes.as_ref().try_into().unwrap());
        CustomType { id }
    }

    const BOUND: ic_stable_structures::storable::Bound =
        ic_stable_structures::storable::Bound::Bounded {
            max_size: 8,
            is_fixed_size: true,
        };
}

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<CustomType, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(CustomType { id: 42 });
assert!(set.contains(&CustomType { id: 42 }));

§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 BTreeSet.
- 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§

Source §

impl<K, M> BTreeSet<K, M>
where K: Storable + Ord + Clone, M: Memory,

Source

pub fn init(memory: M) -> BTreeSet<K, M>

Initializes a BTreeSet.

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

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let set: BTreeSet<u64, _> = BTreeSet::init(mem_mgr.get(MemoryId::new(0)));

Source

pub fn new(memory: M) -> BTreeSet<K, M>

Creates a new instance of a BTreeSet.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));

Source

pub fn load(memory: M) -> BTreeSet<K, M>

Loads the BTreeSet from memory.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);

// Save the set to memory
let memory = set.into_memory();

// Load the set from memory
let loaded_set: BTreeSet<u64, _> = BTreeSet::load(memory);
assert!(loaded_set.contains(&42));

Source

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

Inserts a key into the set. Returns true if the key did not exist in the set before.

§Complexity

O(log n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
assert!(set.insert(42));
assert!(!set.insert(42)); // Key already exists

Source

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

Returns true if the key exists in the set, false otherwise.

§Complexity

O(log n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
assert!(set.contains(&42));
assert!(!set.contains(&7));

Source

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

§Complexity

O(1)

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
assert!(set.is_empty());

Source

pub fn len(&self) -> u64

Returns the number of elements in the set.

§Complexity

O(1)

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
set.insert(7);
assert_eq!(set.len(), 2);

Source

pub fn into_memory(self) -> M

Returns the underlying memory.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
let memory = set.into_memory();

Source

pub fn clear(&mut self)

Removes all elements from the set.

This operation clears the set by deallocating all memory used by its elements.

§Complexity

O(n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
set.clear();
assert!(set.is_empty());

Source

pub fn first(&self) -> Option<K>

Returns the first key in the set. This key is the minimum key in the set.

§Complexity

O(log n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
set.insert(7);
assert_eq!(set.first(), Some(7));

Source

pub fn last(&self) -> Option<K>

Returns the last key in the set. This key is the maximum key in the set.

§Complexity

O(log n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
set.insert(7);
assert_eq!(set.last(), Some(42));

Source

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

Removes a key from the set, returning true if it exists.

§Complexity

O(log n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
assert!(set.remove(&42));
assert!(!set.contains(&42));

Source

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

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

§Complexity

O(log n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
set.insert(7);
assert_eq!(set.pop_last(), Some(42));

Source

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

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

§Complexity

O(log n), where n is the number of elements in the set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
set.insert(7);
assert_eq!(set.pop_first(), Some(7));

Source

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

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

§Complexity

Creating the iterator is O(1), and iterating over k elements is O(k).

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(42);
set.insert(7);
for key in set.iter() {
    println!("{}", key);
}

Source

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

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

§Complexity

O(log n) for creating the iterator. Iterating over the range is O(k), where k is the number of elements in the range.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
set.insert(1);
set.insert(2);
set.insert(3);
let range: Vec<_> = set.range(2..).collect();
assert_eq!(range, vec![2, 3]);

Source

pub fn union<'a>( &'a self, other: &'a BTreeSet<K, M>, ) -> impl Iterator<Item = K> + 'a

Returns an iterator over the union of this set and another.

The union of two sets is a set containing all elements that are in either set.

§Complexity

O(n + m), where:

n is the size of the first set.
m is the size of the second set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));

set1.insert(1);
set1.insert(2);
set2.insert(2);
set2.insert(3);

let union: Vec<_> = set1.union(&set2).collect();
assert_eq!(union, vec![1, 2, 3]);

Source

pub fn intersection<'a>( &'a self, other: &'a BTreeSet<K, M>, ) -> impl Iterator<Item = K> + 'a

Returns an iterator over the intersection of this set and another.

The intersection of two sets is a set containing only the elements that are in both sets.

§Complexity

O(n + m), where:

n is the size of the first set.
m is the size of the second set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));

set1.insert(1);
set1.insert(2);
set1.insert(3);

set2.insert(2);
set2.insert(3);
set2.insert(4);

let intersection: Vec<_> = set1.intersection(&set2).collect();
assert_eq!(intersection, vec![2, 3]);

Source

pub fn is_disjoint(&self, other: &BTreeSet<K, M>) -> bool

Returns true if this set has no elements in common with another set.

§Complexity

O(n + m), where:

n is the size of the first set.
m is the size of the second set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));

set1.insert(1);
set1.insert(2);
set2.insert(3);
set2.insert(4);

assert!(set1.is_disjoint(&set2));
set2.insert(2);
assert!(!set1.is_disjoint(&set2));

Source

pub fn is_subset(&self, other: &BTreeSet<K, M>) -> bool

Returns true if this set is a subset of another set.

A set A is a subset of a set B if all elements of A are also elements of B.

§Complexity

O(n + m), where:

n is the size of the first set.
m is the size of the second set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));

set1.insert(1);
set1.insert(2);
set2.insert(1);
set2.insert(2);
set2.insert(3);

assert!(set1.is_subset(&set2));
assert!(!set2.is_subset(&set1));

Source

pub fn is_superset(&self, other: &BTreeSet<K, M>) -> bool

Returns true if this set is a superset of another set.

A set A is a superset of a set B if all elements of B are also elements of A.

§Complexity

O(n + m), where:

n is the size of the first set.
m is the size of the second set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));

set1.insert(1);
set1.insert(2);
set1.insert(3);
set2.insert(1);
set2.insert(2);

assert!(set1.is_superset(&set2));
assert!(!set2.is_superset(&set1));

Source

pub fn symmetric_difference<'a>( &'a self, other: &'a BTreeSet<K, M>, ) -> impl Iterator<Item = K> + 'a

Returns an iterator over the symmetric difference of this set and another.

The symmetric difference of two sets is the set of elements that are in either of the sets, but not in their intersection.

§Complexity

O(n + m), where:

n is the size of the first set.
m is the size of the second set.

§Example

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

let mem_mgr = MemoryManager::init(DefaultMemoryImpl::default());
let mut set1: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(0)));
let mut set2: BTreeSet<u64, _> = BTreeSet::new(mem_mgr.get(MemoryId::new(1)));

set1.insert(1);
set1.insert(2);
set2.insert(2);
set2.insert(3);

let symmetric_diff: Vec<_> = set1.symmetric_difference(&set2).collect();
assert_eq!(symmetric_diff, vec![1, 3]);