Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 978
Jeremy Cochoy Avatar asked Nov 20 '19 09:11

Jeremy Cochoy


Video Answer


1 Answers

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)
like image 62
Jeremy Cochoy Avatar answered Sep 28 '22 04:09

Jeremy Cochoy