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?

Chirpy

Why not using a BinaryHeap instead, which has a pop() method. – Aho

@Aho Yes, and probably more suitable is peek if you only need to read the value. But I am not sure you can also get the other extremal value. In my personal case, I was using BTreeMaps and the order was used to search inside the collection. – Chirpy

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)

Chirpy

Rust is not limited to std, crates.io/crates/min-max-heap – Glimpse

@Stargateur: Sure, but a heap is not a set/map, so while it may suits the OP needs, for this question it would not be suitable. – Tripedal

Of interest, I just came upon github.com/rust-lang/rust/pull/65637 in TWiR. – Tripedal

@MatthieuM. Thanks. If I understand this commit, there will be first and last for the ordered set, and first_key_value and last_key_value for the ordered maps. Since the merge is young, I guess we will have to wait a bit. (: – Chirpy

In 2020, The performance issue may not be there anymore! :) – Chirpy