BTreeMap
- Rust course
- Intermediate
- Lesson 55/115
- 4 min
Use an ordered-key map with BTreeMap.
BTreeMap
BTreeMap<K, V> is also a key-value table, but it keeps the keys sorted. Lookup is O(log n); iteration is always in key order. The key type must be Ord:
use std::collections::BTreeMap;
let mut m = BTreeMap::new();
m.insert("zeytin", 3);
m.insert("armut", 5);
m.insert("muz", 2);
for (k, v) in &m {
println!("{k}={v}"); // in the order armut, muz, zeytin
}Range queries
The sorted structure gives cheap access to range queries and extreme values:
let mut sicaklik = BTreeMap::new();
for (saat, d) in [(8, 12), (12, 21), (15, 24), (20, 16)] {
sicaklik.insert(saat, d);
}
let ogleden_sonra: Vec<_> = sicaklik.range(12..=18).collect();
println!("{:?}", ogleden_sonra); // [(12, 21), (15, 24)]
println!("{:?}", sicaklik.first_key_value()); // Some((8, 12))Practice Sorted list
Insert ("zeytin", 3), ("armut", 5) and ("muz", 2) into a BTreeMap; print the pairs as key=value, one per line.
Starter code
use std::collections::BTreeMap;
fn main() {
// buraya yaz
}Sample solution
use std::collections::BTreeMap;
fn main() {
let mut m = BTreeMap::new();
m.insert("zeytin", 3);
m.insert("armut", 5);
m.insert("muz", 2);
for (k, v) in &m {
println!("{}={}", k, v);
}
}Expected output
armut=5 muz=2 zeytin=3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 In which case is BTreeMap a better fit than HashMap?
- When results must be reported in key order Correct answer
- When the fastest single lookup is needed
- When keys implement Hash but not Ord
- Never
Explanation: BTreeMap for sorted output, range queries and smallest/largest key; HashMap for raw speed.
2 Query by range
Question
let secim: Vec<_> = sicaklik.____(12..=18).collect();
Answer
let secim: Vec<_> = sicaklik.range(12..=18).collect();Explanation: BTreeMap::range yields the pairs in the given key range, in order.
3 Feature and structure
| Term | Meaning |
|---|---|
Ordered iteration |
BTreeMap |
Ortalama O(1) arama |
HashMap |
range(a..b) |
BTreeMap (only) |
Anahtar Hash + Eq |
HashMap requirement |