如何获取BTreeSet中元素的下界和上界? [英] How to get the lower bound and upper bound of an element in a BTreeSet?

问题描述

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

Reading the BTreeSet documentation, I can't seem to figure out how to get the least value greater than, or greatest value less than an element from a BTreeSet in logarithmic time.

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

I see there is a range method that can give the values in an arbitrary (min, max) range, but what if I don't know the range and I just want the previous and/or the next element in logarithmic time?

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

This would be similar to lower_bound and upper_bound in std::set in C++.

推荐答案

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

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

BTreeSet::range returns a double-ended iterator, so you can pull from either side of it.

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

Note that we are using the very explicit Bound operator so that we do not include the value we are looking around.

已经讨论了增强 BTreeMap/BTreeSet 以拥有一个光标"API，可以让您找到一个元素，然后在树内移动".这将允许您避免在树中搜索两次以找到起始节点，但尚未实现.

There have been discussions about enhancing BTreeMap / BTreeSet to have a "cursor" API that might allow you to find an element and then "move around" inside the tree. This would allow you to avoid searching through the tree to find the start node twice, but it has not been implemented.

为此打开了一个拉取请求，但由于人们认为应该对这样的 API 应该如何外观和工作进行更多的讨论.

A pull request was opened to do so, but it was closed because it was deemed that there should be more discussion about how such an API should look and work.

这篇关于如何获取BTreeSet中元素的下界和上界?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！