Rust中基于BTreeMap等树结构有序Map实现相邻值查找方法

Rust 标准库自带的std::collections::BTreeMap是基于B树实现的有序映射，完全满足树结构要求，查找、邻接元素访问的时间复杂度均为O(log n)，和C++通常基于红黑树实现的std::map性能处于同一量级，无需引入第三方库即可实现完全等效的逻辑。

实现逻辑对应关系 #

和C++参考实现的逻辑一一对应：

• BTreeMap::range(target..)生成的迭代器首个元素，完全等效于std::map::lower_bound(target)的返回结果
• 迭代器返回None等效于迭代器走到end()，直接返回类型默认值
• 小于当前键的最大元素即为前驱，大于当前键的最小元素即为后继，对应C++迭代器的--it和++it操作
• 所有边界判断由标准库API天然保证，不存在C++迭代器误操作触发的未定义行为

稳定版可用实现（无Unsafe、无Nightly特性） #

该版本和C++实现的值返回语义完全一致，适合绝大多数场景：

use std::collections::BTreeMap;
use std::ops::Bound::Excluded;

pub fn find_neighbor<K: Ord, V: Ord + Default + Clone>(
    m: &BTreeMap<K, V>,
    target: &K,
    val: &V,
) -> V {
    // 定位lower_bound：第一个键 >= target的条目
    let Some((current_k, current_v)) = m.range(target..).next() else {
        return V::default();
    };

    // 当前值小于等于比较值且存在前驱，返回前驱值
    if *current_v <= *val {
        if let Some((_, prev_v)) = m.range(..current_k).next_back() {
            return prev_v.clone();
        }
    } else {
        // 当前值大于比较值且存在后继，返回后继值
        if let Some((_, next_v)) = m.range((Excluded(current_k), ..)).next() {
            return next_v.clone();
        }
    }

    // 其余场景返回当前条目值
    current_v.clone()
}

零拷贝优化版本 #

如果存储的值是大对象、不需要副本返回，可以调整为返回引用的版本，省去Clone开销：

use std::collections::BTreeMap;
use std::ops::Bound::Excluded;

pub fn find_neighbor_ref<'a, K: Ord, V: Ord>(
    m: &'a BTreeMap<K, V>,
    target: &K,
    val: &V,
    default: &'a V,
) -> &'a V {
    let Some((current_k, current_v)) = m.range(target..).next() else {
        return default;
    };

    if *current_v <= *val {
        if let Some((_, prev_v)) = m.range(..current_k).next_back() {
            return prev_v;
        }
    } else {
        if let Some((_, next_v)) = m.range((Excluded(current_k), ..)).next() {
            return next_v;
        }
    }

    current_v
}

性能说明 #

上述实现中所有range操作的定位开销均为O(log n)，邻接元素获取为常数时间，整体时间复杂度和C++参考实现完全一致。B树结构相比红黑树有更好的缓存局部性，实际批量查询场景下性能通常优于红黑树实现的有序映射。如果必须使用红黑树结构，可替换为第三方红黑树实现的有序映射，核心查找逻辑完全一致，仅API命名略有差异。

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