Home
Rust
BTreeMap Example
This page was last reviewed on Mar 27, 2023.
Dot Net Perls
BTreeMap. In Rust the BTreeMap uses a tree-based algorithm to store keys along with their values. This can be much faster than a linear search through a vector.
vec
Compared to HashMap, the BTreeMap has nearly identical usage. It usually tends to be slower than HashMap, but not always. A benchmark can help determine the faster collection.
HashMap
First example. Consider this example program in Rust. We create a BTreeMap with integer keys and values. With BTreeMap, we could use other types like Strings or even arrays as keys and values.
Note When looping over the keys in a BTreeMap, we can see that they are stored in a sorted way (an ascending sort).
for
Note 2 As with HashMap, we can call get in an if-let statement. This gives us an unwrapped value to use more easily.
if
use std::collections::BTreeMap; fn main() { // Create BTreeMap. let mut b = BTreeMap::new(); b.insert(200, 20); b.insert(100, 5); // Keys are ordered. for k in b.keys() { println!("KEY: {k}"); } // Get a value. let test = 100; if let Some(value) = b.get(&test) { println!("FOR 100: {value}"); } }
KEY: 100 KEY: 200 FOR 100: 5
BTreeSet. This collection is the same as BTreeMap but does not provide values, and it has helpful additional methods. When values are not needed, BTreeSet can be clearer.
Part 1 We create a BTreeSet with new() and add 2 items to it with the insert function.
Part 2 We can use pop_first to remove an element from the BTreeSet. In a sense, this collection is linear and has a start element.
Part 3 We can get the length of the collection with len(). This tells us the total number of keys.
use std::collections::*; fn main() { // Part 1: create set and add elements. let mut set = BTreeSet::new(); set.insert(10); set.insert(20); // Part 2: We can use pop to remove an element at the start. if let Some(x) = set.pop_first() { println!("{x}"); } // Part 3: Length. println!("{}", set.len()); }
10 1
Benchmark. The important question with BTreeMap is how it performs against HashMap. Both collections are about as easy to use—most code (not all) can be left unchanged.
Version 1 In this version of the code, we look up 6 million keys in a BTreeMap. All of the keys exist in the collection.
Version 2 Here we do the same thing, but use the HashMap. In both versions, a panic macro handles unexpected results.
Result HashMap is about twice as fast as BTreeMap—in most situations, HashMap will have better performance overall.
use std::time::*; use std::collections::*; fn main() { let keys = ["bird", "frog", "dog", "cat", "tree", "house"]; let mut b = BTreeMap::new(); let mut h = HashMap::new(); for k in keys { b.insert(k, true); h.insert(k, true); } // Version 1: use BTreeMap. let t0 = Instant::now(); for _ in 0..1000000 { for k in &keys { if !b.contains_key(k) { panic!("Error"); } } } println!("{}", t0.elapsed().as_millis()); // Version 2: use HashMap. let t1 = Instant::now(); for _ in 0..1000000 { for k in &keys { if !h.contains_key(k) { panic!("Error"); } } } println!("{}", t1.elapsed().as_millis()); }
111 ms BTreeMap 58 ms HashMap
Performance notes. Occasionally, particularly on collections with small keys, the BTreeMap is a better choice. Try it out when integers or small arrays are used as keys.
A summary. BTreeMap is an optimized collection in the Rust standard library (std). It is implemented with a different algorithm than HashMap, and is usually but not always slower.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Mar 27, 2023 (edit link).
Home
Changes
© 2007-2024 Sam Allen.