如何在Rust的BTreeSet中单次查找严格小于和大于指定键的元素？

好问题！在Rust里确实可以模拟C++ std::set那种单次定位后获取前后边界的逻辑，虽然标准库没有直接提供和lower_bound完全一致的迭代器操作方式，但我们可以用BTreeSet的range方法高效实现需求，避免冗余的查找操作——毕竟热点路径的性能优化可不能马虎。

下面是符合Rust惯用风格的实现，逻辑和你给出的C++代码完全对齐：

use std::collections::BTreeSet;

fn bounding_box<T: Ord + Clone>(space: &BTreeSet<T>, point: &T) -> (Option<T>, Option<T>) {
    if space.is_empty() {
        return (None, None);
    }

    // 定位第一个 >= point 的元素，对应C++的lower_bound
    let mut ge_iter = space.range(point..);
    let ge_element = ge_iter.next().cloned();

    // 计算严格大于的上界：如果当前元素等于point，就取下一个元素；否则当前元素就是上界
    let upper_bound = match &ge_element {
        Some(val) if val == point => ge_iter.next().cloned(),
        Some(_) => ge_element.clone(),
        None => None,
    };

    // 计算严格小于的下界：如果存在>=point的元素，找最后一个<point的元素；否则取集合最大元素
    let lower_bound = match ge_element {
        Some(_) => space.range(..point).next_back().cloned(),
        None => space.iter().next_back().cloned(),
    };

    (lower_bound, upper_bound)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_middle_point() {
        let set: BTreeSet<_> = ["1", "3"].into();
        let (lt, gt) = bounding_box(&set, "2");
        assert_eq!(lt, Some("1".to_string()));
        assert_eq!(gt, Some("3".to_string()));
    }

    #[test]
    fn test_greater_than_max() {
        let set: BTreeSet<_> = ["1", "3"].into();
        let (lt, gt) = bounding_box(&set, "4");
        assert_eq!(lt, Some("3".to_string()));
        assert_eq!(gt, None);
    }

    #[test]
    fn test_less_than_min() {
        let set: BTreeSet<_> = ["1", "3"].into();
        let (lt, gt) = bounding_box(&set, "0");
        assert_eq!(lt, None);
        assert_eq!(gt, Some("1".to_string()));
    }

    #[test]
    fn test_exact_match_duplicate() {
        let set: BTreeSet<_> = ["3", "3"].into(); // BTreeSet自动去重，实际仅存"3"
        let (lt, gt) = bounding_box(&set, "3");
        assert_eq!(lt, None);
        assert_eq!(gt, None);
    }

    #[test]
    fn test_exact_match_with_successor() {
        let set: BTreeSet<_> = ["3", "4"].into();
        let (lt, gt) = bounding_box(&set, "3");
        assert_eq!(lt, None);
        assert_eq!(gt, Some("4".to_string()));
    }

    #[test]
    fn test_empty_set() {
        let set: BTreeSet<String> = BTreeSet::new();
        let (lt, gt) = bounding_box(&set, "3");
        assert_eq!(lt, None);
        assert_eq!(gt, None);
    }
}

代码说明： #

1. 空集合处理：直接返回(None, None)，避免后续无效操作。
2. 定位下界起点：用space.range(point..).next()获取第一个大于等于目标值的元素，这一步和C++的lower_bound逻辑完全一致。
3. 计算严格上界：如果定位到的元素和目标值相等，就跳过它取下一个元素（如果存在）；否则这个元素就是第一个严格大于目标值的元素。
4. 计算严格下界：如果存在大于等于目标值的元素，就找最后一个小于目标值的元素；如果目标值比所有元素都大，就取集合中最大的元素。

性能说明： #

虽然代码里用了两次range调用，但BTreeSet的range操作是O(log n)时间复杂度，两次调用的总复杂度还是O(log n)，和C++的单次查找加O(1)迭代器移动在渐近性能上是等价的，完全能满足热点路径的性能要求。而且这种写法充分利用了Rust标准库的抽象能力，代码可读性和维护性都很好。

另外要注意，BTreeSet会自动去重，这和C++的std::set行为一致，所以测试用例里的重复元素会被自动合并。

内容的提问来源于stack exchange，提问作者MasterWindu