Introduction

In Rust, BTreeMap is a sorted map based on a B-Tree. It stores key-value pairs in sorted order, and provides efficient insertion, deletion, and lookup operations. BTreeMap is part of the standard library's std::collections module and is useful when you need a map with ordered keys.

Using BTreeMap

To use BTreeMap, you need to import it from the std::collections module. You can create a BTreeMap by using the BTreeMap::new method. Elements can be added using insert, and accessed or removed using methods like get and remove respectively.

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("a", 1);
    map.insert("b", 2);

    println!("Map: {:?}", map);
    println!("Value for key 'a': {:?}", map.get("a"));
}
// Output:
// Map: {"a": 1, "b": 2}
// Value for key 'a': Some(1)

Key Methods

Below are some of the key methods exposed by the BTreeMap class:

BTreeMap::new

Creates a new, empty BTreeMap.

use std::collections::BTreeMap;

fn main() {
    let map: BTreeMap<&str, i32> = BTreeMap::new();
    println!("Created an empty map: {:?}", map);
}
// Output:
// Created an empty map: {}

BTreeMap::insert

Adds a key-value pair to the BTreeMap. If the key already exists, the corresponding value is updated.

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("key1", 10);
    map.insert("key2", 20);
    println!("Map after insertions: {:?}", map);
}
// Output:
// Map after insertions: {"key1": 10, "key2": 20}

BTreeMap::get

Returns a reference to the value corresponding to the key, or None if the key is not present.

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("key1", 30);
    println!("Value for 'key1': {:?}", map.get("key1"));
    println!("Value for 'key2': {:?}", map.get("key2"));
}
// Output:
// Value for 'key1': Some(30)
// Value for 'key2': None

BTreeMap::remove

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

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("key1", 40);
    println!("Removed value: {:?}", map.remove("key1"));
    println!("Map after removal: {:?}", map);
}
// Output:
// Removed value: Some(40)
// Map after removal: {}

BTreeMap::contains_key

Returns true if the BTreeMap contains a value for the specified key.

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("key1", 50);
    println!("Contains 'key1': {}", map.contains_key("key1"));
    println!("Contains 'key2': {}", map.contains_key("key2"));
}
// Output:
// Contains 'key1': true
// Contains 'key2': false

Example Usage

Example 1: Basic Usage

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("x", 10);
    map.insert("y", 20);

    println!("Map: {:?}", map);
    println!("Value for key 'x': {:?}", map.get("x"));
}
// Output:
// Map: {"x": 10, "y": 20}
// Value for key 'x': Some(10)

Example 2: Updating a Value

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("key", 1);
    map.insert("key", 2);

    println!("Map after update: {:?}", map);
}
// Output:
// Map after update: {"key": 2}

Example 3: Removing a Key-Value Pair

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    let removed = map.remove("a");

    println!("Removed value: {:?}", removed);
    println!("Map after removal: {:?}", map);
}
// Output:
// Removed value: Some(1)
// Map after removal: {"b": 2}

Example 4: Iterating Over Elements

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("c", 3);
    map.insert("a", 1);
    map.insert("b", 2);

    for (key, value) in &map {
        println!("Key: {}, Value: {}", key, value);
    }
}
// Output:
// Key: a, Value: 1
// Key: b, Value: 2
// Key: c, Value: 3

Example 5: Checking Key Existence

use std::collections::BTreeMap;

fn main() {
    let mut map = BTreeMap::new();
    map.insert("k1", 100);
    map.insert("k2", 200);

    println!("Contains 'k1': {}", map.contains_key("k1"));
    println!("Contains 'k3': {}", map.contains_key("k3"));
}
// Output:
// Contains 'k1': true
// Contains 'k3': false

Considerations

BTreeMap keeps keys in sorted order, which can be useful for range queries or ordered traversal.
All keys in a BTreeMap must implement the Ord trait.
Insertion and removal operations in BTreeMap have logarithmic complexity.