B-Trees: Sorted Maps and Sets

Recipe	Crates	Categories
Create a Map Sorted by Key with BTreeMap
Create a Sorted Set with BTreeSet<T>

Create a Map Sorted by Key with BTreeMap

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.

BTreeMap is implemented as a B-tree, a self-balancing tree structure that guarantees logarithmic time complexity for most operations. The following are common 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. It 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;
use std::collections::btree_map::Entry;

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", 3);
    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 for books between 'P' and 'R':");
    for (book, rating) in book_ratings.range("P".."R") {
        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());

    // Use the `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 {
        Entry::Occupied(mut occupied) => {
            let old_rating = occupied.get();
            println!(
                "Book '{book_title}' already exists with rating {old_rating}",
            );
            *occupied.get_mut() = new_rating; // Update in place.
            println!("Updated rating for '{book_title}' to {new_rating}");
        }
        Entry::Vacant(vacant) => {
            vacant.insert(new_rating); // Insert if it doesn't exist.
            println!("Inserted '{book_title}' with rating {new_rating}");
        }
    }
    // Most commonly you will use `or_insert` and related methods:
    book_ratings.entry("The Hitchhiker's Guide to the Galaxy")
     .and_modify(|e| { *e += 1 }) // Provides in-place mutable access to an occupied entry.
     // Ensures a value is in the entry by inserting the default if empty,
     // and returns a mutable reference to the value in the entry.
     .or_insert(5);
    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());
}

Create a Sorted Set with BTreeSet<T>

BTreeSet is similar to HashSet, but it keeps the elements sorted.

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

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());

    // Use 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}");
    }

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

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

    // Use 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());
}

Related Topics

• Hashmaps.
• Other Maps.
• Sorting.
• Vectors.

Refer as well to the ordered-float↗ example in the Additional Numeric Types chapter.