How to get the maximum and minimum value of an ordered set / ordered map?

Question

Rust's ordered set is a BTreeSet:

use std::collections::BTreeSet;

// Type inference lets us omit an explicit type signature (which
// would be `BTreeSet<&str>` in this example).
let mut books = BTreeSet::new();

// Add some books.
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

An ordered map is a BTreeMap.

Since the set and map are ordered, there should be a way to get the maximal and minimal element contained. How do you get them?

Answer 1

There are no maximum or minimum member methods (inherent or from a trait) for this type.

The best way to have access to this information in O(log(n)) is to directly use an iterator, as mentioned by the developer team in issue 31690 from GitHub:

let map: BTreeSet<V> = ...;
let min = map.iter().next();
let max = map.iter().next_back();

---

You can get the maximum and minimum of a collection by using the Iterator::max() and Iterator::min() methods, but doing this with an ordered set will browse the whole collection, ignoring the information that we have from the order.

// This will be very slow
map.iter().max()
map.iter().min()

Issue 59947 has a benchmark showing the two alternatives for BTreeMap:

test bench_first ... bench:           9 ns/iter (+/- 0)
test bench_last  ... bench:           8 ns/iter (+/- 0)
test bench_max   ... bench:       3,603 ns/iter (+/- 536)
test bench_min   ... bench:       3,755 ns/iter (+/- 328)