BTreeMap and BTreeSet

RecipeCratesCategories
BTreeMap<K, V>stdcat~data-structures
BTreeSet<T>stdcat~data-structures

BTreeMap<K, V>

std cat~data-structures

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 '{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}");
        }
        std::collections::btree_map::Entry::Vacant(vacant) => {
            vacant.insert(new_rating); // Insert if it doesn't exist.
            println!("Inserted '{book_title}' with rating {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>

std cat~data-structures

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());
}
  • Hashmaps.
  • Other Maps.
  • Sorting.
  • Vectors.

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