有序映射中获取指定值的相邻值：四款有序树库实现方案问询

以下是针对四款Rust有序映射库，获取目标键对应下一个更大值和下一个更小值的具体实现：

1. BTreeMap（标准库） #

作为Rust标准库自带的有序映射，BTreeMap通过range方法实现范围查询，结合迭代器操作获取前后元素：

获取下一个更大值 #

use std::collections::BTreeMap;

fn get_next_greater<K: Ord, V>(map: &BTreeMap<K, V>, key: &K) -> Option<(&K, &V)> {
    // 从目标键的位置开始遍历，跳过自身后取第一个元素
    map.range((key, ..)).skip(1).next()
}

获取下一个更小值 #

fn get_next_smaller<K: Ord, V>(map: &BTreeMap<K, V>, key: &K) -> Option<(&K, &V)> {
    // 取目标键之前的所有元素中的最后一个
    map.range(..key).next_back()
}

2. rudy::rudymap::RudyMap #

这款基于B树的有序映射提供了upper_bound和range两种方式来获取下一个更大值，操作逻辑类似标准库：

获取下一个更大值 #

方式一：使用upper_bound直接定位第一个大于目标键的元素

use rudy::rudymap::RudyMap;

fn get_next_greater<K: Ord, V>(map: &RudyMap<K, V>, key: &K) -> Option<(&K, &V)> {
    map.upper_bound(key).map(|entry| (entry.key(), entry.value()))
}

方式二：通过range结合迭代器跳过自身

fn get_next_greater<K: Ord + Clone, V>(map: &RudyMap<K, V>, key: &K) -> Option<(&K, &V)> {
    map.range((key.clone(), ..)).skip(1).next()
}

获取下一个更小值 #

fn get_next_smaller<K: Ord, V>(map: &RudyMap<K, V>, key: &K) -> Option<(&K, &V)> {
    map.range(..key).next_back()
}

3. art_tree #

基于自适应基数树（ART）的ArtMap直接提供了successor和predecessor方法，无需手动处理迭代器：

获取下一个更大值 #

use art_tree::ArtMap;

fn get_next_greater<K: Ord + AsRef<[u8]>, V>(map: &ArtMap<K, V>, key: &K) -> Option<(&K, &V)> {
    map.successor(key)
}

获取下一个更小值 #

fn get_next_smaller<K: Ord + AsRef<[u8]>, V>(map: &ArtMap<K, V>, key: &K) -> Option<(&K, &V)> {
    map.predecessor(key)
}

注意：ArtMap的键需要实现AsRef<[u8]> trait，适配基数树的存储特性。

4. Judy Arrays #

Judy数组是针对整数键优化的有序结构，常用的JudyL（64位整数键）通过专属方法获取前后元素：

获取下一个更大值 #

use judy::JudyL;

fn get_next_greater(map: &JudyL<u64>, key: &u64) -> Option<(u64, &u64)> {
    let mut next_key = *key;
    // get_next会修改next_key为第一个大于原键的数值，同时返回对应值
    map.get_next(&mut next_key).map(|val| (next_key, val))
}

获取下一个更小值 #

fn get_next_smaller(map: &JudyL<u64>, key: &u64) -> Option<(u64, &u64)> {
    let mut prev_key = *key;
    // get_prev会修改prev_key为第一个小于原键的数值，同时返回对应值
    map.get_prev(&mut prev_key).map(|val| (prev_key, val))
}

注意：Judy数组的键类型仅限整数类，不同Judy变体对应不同键范围（如JudyU对应32位无符号整数）。

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