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

Question

阅读BTreeSet文档,我似乎无法弄清楚如何BTreeSet在对数时间内获得大于或小于元素的最小值.

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

这将是类似lower_bound与upper_bound在std::setC++中.

Answer 1

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

然后使用无界范围：

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

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

BTreeSet::range 返回一个双端迭代器，因此您可以从它的任一侧拉取。

请注意，我们使用了非常明确的Bound运算符，因此我们不包括我们正在查看的值。

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

为此打开了一个拉取请求，但它被关闭了，因为它被认为应该对这样的 API 应该如何外观和工作进行更多的讨论。

Answer 2

好吧...如果您不介意修改当前集合并承受性能影响...看来您可以split_off创造性地使用。

let mut tree = BTreeSet::new();
tree.insert(1);
tree.insert(3);
tree.insert(5);

let other = tree.split_off(&2);

println!("{:?}", tree);
println!("{:?}", other);

将打印{1}并{3, 5}：

• 下限是第二个范围的第一个元素，
• 如果不相等，则上限是第二个范围的第一个元素，否则是第二个元素。

完成后，您可以使用 重新组装树tree.append(other)。

是的，这确实不太理想......