BTreeMap and BTreeSet

Recipe	Crates	Categories

BTreeMap<K, V>

BTreeMap<K, V> is a sorted map data structure, similar to HashMap, but its keys are always kept in sorted order. This allows for efficient range queries (e.g., retrieving all values within a specific key range) and ordered iteration. Iterating over a BTreeMap will always yield the key-value pairs in ascending order of the keys.

This ordering is the main difference between BTreeMap and the more common HashMap. BTreeMap is implemented as a B-tree, a self-balancing tree structure that guarantees logarithmic time complexity for most operations.

• insert(key, value) inserts a new key-value pair. If the key already exists, the old value is replaced and returned.
• get(key) returns a reference to the value associated with the given key, or None if the key is not present.
• remove(key) removes the key-value pair associated with the given key. Returns the removed value, or None if the key was not present.
• contains_key(key) returns true if the map contains the given key.
• iter() returns an iterator over the key-value pairs in sorted order.
• range(range) returns an iterator over a specified range of keys.
• first_key_value() returns the smallest (first) key-value pair.
• last_key_value() returns the largest (last) key-value pair.

use std::collections::BTreeMap;

fn main() {
    // Create a new BTreeMap
    let mut book_ratings = BTreeMap::new();

    // Insert some book ratings
    book_ratings.insert("The Hitchhiker's Guide to the Galaxy", 5);
    book_ratings.insert("Pride and Prejudice", 4);
    book_ratings.insert("1984", 5);
    book_ratings.insert("To Kill a Mockingbird", 4);
    book_ratings.insert("Dune", 4);

    // Print the map (elements are printed in sorted key order)
    println!("Book ratings:");
    for (book, rating) in &book_ratings {
        println!("{}: {}", book, rating);
    }

    // Get the rating for a specific book
    if let Some(rating) = book_ratings.get("1984") {
        println!("Rating for 1984: {}", rating);
    }

    // Check if a book is in the map
    if book_ratings.contains_key("Pride and Prejudice") {
        println!("Pride and Prejudice is in the map.");
    }

    // Remove a book and its rating
    if let Some(rating) = book_ratings.remove("Dune") {
        println!("Removed Dune, rating was {}", rating);
    }

    // Iterate over a range of books (lexicographically between "P" and "T")
    println!("\nRatings between 'P' and 'T':");
    for (book, rating) in book_ratings.range("P".."T") {
        println!("{}: {}", book, rating);
    }

    // Find the first and last entries
    println!("\nFirst entry: {:?}", book_ratings.first_key_value());
    println!("Last entry: {:?}", book_ratings.last_key_value());

    // Example of using entry API to efficiently update or insert
    let book_title = "The Lord of the Rings";
    let new_rating = 5;
    let entry = book_ratings.entry(book_title);
    match entry {
        std::collections::btree_map::Entry::Occupied(mut occupied) => {
            let old_rating = occupied.get();
            println!(
                "Book '{}' already exists with rating {}",
                book_title, old_rating
            );
            *occupied.get_mut() = new_rating; // Update in place
            println!("Updated rating for '{}' to {}", book_title, new_rating);
        }
        std::collections::btree_map::Entry::Vacant(vacant) => {
            vacant.insert(new_rating); // Insert if it doesn't exist
            println!("Inserted '{}' with rating {}", book_title, new_rating);
        }
    }
    println!("Updated book ratings:");
    for (book, rating) in &book_ratings {
        println!("{}: {}", book, rating);
    }

    // Clear the map
    book_ratings.clear();
    println!("Map is empty: {}", book_ratings.is_empty());
}

BTreeSet<T>

BTreeSet is a sorted set based on a self-balancing tree, specifically a B-Tree. BTreeSet allows you to store unique elements in a sorted order and provides efficient operations for insertion, deletion, and lookup, with average time complexity of O(log n).

B-Tree Set is similar to HashSet, but it keeps the elements sorted.

use std::collections::BTreeSet;

fn main() {
    // Create a new BTreeSet
    let mut names = BTreeSet::new();

    // Insert some names
    names.insert("Alice");
    names.insert("Bob");
    names.insert("Charlie");
    names.insert("Alice"); // Duplicate insertion, will be ignored
    names.insert("David");
    names.insert("Eve");

    // Print the set (elements are printed in sorted order)
    println!("Names in the set:");
    for name in &names {
        println!("{}", name);
    }

    // Check if a name is in the set
    if names.contains("Bob") {
        println!("Bob is in the set.");
    }

    // Remove a name
    names.remove("Charlie");

    // Iterate over a range of names
    println!("\nNames starting with 'B' and beyond:");
    for name in names.range("B"..) {
        println!("{}", name);
    }

    // Find the first and last elements
    println!("\nFirst name: {:?}", names.first());
    println!("Last name: {:?}", names.last());

    // Get the length of the set
    println!("\nNumber of names in the set: {}", names.len());

    // Check if the set is empty
    println!("Is the set empty? {}", names.is_empty());

    // Example of using the difference method to find elements in one set but
    // not another
    let other_names = BTreeSet::from(["Bob", "Eve", "Frank"]);
    let difference = names.difference(&other_names);
    println!("\nNames in the set but not in other_names:");
    for name in difference {
        println!("{}", name);
    }

    // Example of using the union method to combine two sets
    let union = names.union(&other_names);
    println!("\nUnion of both sets:");
    for name in union {
        println!("{}", name);
    }

    // Example of using the intersection method to find common elements
    let intersection = names.intersection(&other_names);
    println!("\nIntersection of both sets:");
    for name in intersection {
        println!("{}", name);
    }

    // Example of using the symmetric_difference method to find elements in
    // either set but not both
    let symmetric_difference = names.symmetric_difference(&other_names);
    println!("\nSymmetric difference of both sets:");
    for name in symmetric_difference {
        println!("{}", name);
    }

    // Clear the set
    names.clear();
    println!("Set is empty: {}", names.is_empty());
}