Rust 如何获得有序集(set)有序图( ordered map)的最大值和最小值

发布于11月20日

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");

有序 map 是BTreeMap.

因为集合和映射是有序的，所以应该有一种方法来获得包含的最大和最小元素.你怎么弄到的？

推荐答案

对于这种类型，没有最大或最小成员方法(固有或来自特征).

在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)