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

Question

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

我看到有一个 range可以在任意(最小值、最大值)范围内给出值的方法，但是如果我不知道范围并且我只想要对数时间的前一个和/或下一个元素怎么办？

这类似于 C++ 中 std::set 中的 lower_bound 和 upper_bound。

Answer 1

but what if I don't know the range

然后使用无界范围:

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返回一个双端迭代器，因此您可以从它的任一侧拉取。

请注意，我们使用的是非常明确的 Bound运算符，以便我们不包括我们正在寻找的值。

---

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

A pull request was opened to do so ，但它已关闭，因为人们认为应该就此类 API 的外观和工作方式进行更多讨论。