如何获取有序集合/有序映射的最大值和最小值？

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。

既然set和map是有序的，那么应该有办法得到其中包含的最大和最小元素。你是怎么得到它们的？

Answer 1

此类型没有最大或最小成员方法（固有或来自特征）。

在 O(log(n)) 中访问此信息的最佳方法是直接使用迭代器，正如开发团队在 issue 31690 from 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()

Issue 59947 has a benchmark 显示 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)

如何获取有序集合/有序映射的最大值和最小值？

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

rust

b-tree

ordered-map

ordered-set