如何获取 BTreeSet 中元素的下界和上限？

正在阅读BTreeSet文档，我似乎无法弄清楚如何从 a 中获取大于元素的最小值或小于元素的最大值BTreeSet在对数时间内。

我看到有一个range https://doc.rust-lang.org/std/collections/struct.BTreeSet.html#method.range可以给出任意（最小，最大）范围内的值的方法，但是如果我不知道范围并且我只想在对数时间内获得上一个和/或下一个元素怎么办？

这类似于lower_bound and upper_bound in std::set in C++.

但如果我不知道范围怎么办

然后使用无界范围：

use std::collections::BTreeSet;

fn neighbors(tree: &BTreeSet<i32>, val: i32) -> (Option<&i32>, Option<&i32>) {
    use std::ops::Bound::*;

    let mut before = tree.range((Unbounded, Excluded(val)));
    let mut after = tree.range((Excluded(val), Unbounded));

    (before.next_back(), after.next())
}

fn main() {
    let tree: BTreeSet<_> = [1, 3, 5].iter().cloned().collect();

    let (prev, next) = neighbors(&tree, 2);

    println!("greatest less than 2: {:?}", prev);
    println!("least bigger than 2:  {:?}", next);
}

greatest less than 2: Some(1)
least bigger than 2:  Some(3)

BTreeSet::range https://doc.rust-lang.org/std/collections/struct.BTreeSet.html#method.range返回一个双端迭代器，因此您可以从它的任一侧拉取。

请注意，我们使用的是非常明确的Bound https://doc.rust-lang.org/std/ops/enum.Bound.html运算符，以便我们不包括我们正在查找的值。

已经有关于加强的讨论BTreeMap / BTreeSet拥有一个“光标”API，可以让您找到一个元素，然后在树内“移动”。这将允许您避免两次搜索树来查找起始节点，但它尚未实现。

为此提出了拉取请求 https://github.com/rust-lang/rust/pull/47228，但它被关闭了，因为人们认为应该对这样的 API 应该如何外观和工作进行更多讨论。