Как получить максимальное и минимальное значение упорядоченного набора / упорядоченной карты?

Question

Упорядоченный набор Rust - это 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");

Упорядоченная карта - это BTreeMap.

Поскольку набор и карта упорядочены, должен быть способ получить максимальный и минимальный содержащиеся элементы. Как их получить?

Answer 1

Для этого типа не существует методов максимальных или минимальных членов (неотъемлемых или от черты).

Лучший способ получить доступ к этой информации в O(log(n)) - это напрямую использовать итератор, как было упомянуто командой разработчиков в выпуске 31690 с GitHub:

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

---

Вы можете получить максимум и минимум коллекции, используя Iterator::max() а также Iterator::min() методы, но при этом с упорядоченным набором будет просматриваться вся коллекция, игнорируя информацию, которая у нас есть из заказа.

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

Проблема 59947 содержит тест, показывающий две альтернативы для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)