rust - 使用整数获取映射到数字范围的值以在 Rust 中查找键

Question

在 Rust 中，我可以使用位于该范围内的整数来选择映射到数字范围的值的最简单方法是什么？

类似于:

range_values.insert(0..1000, "A");
range_values.insert(1001..2000, "B");

get_value(range_values, 1500); // returns "B"

Answer 1

最简单的方法是使用成对的向量并按顺序迭代它们以找到向量中的正确条目。

use std::ops::Range;

fn get_value<'a>(range_values: &[(Range<i32>, &'a str)], key: i32) -> Option<&'a str> {
    for &(ref range, value) in range_values {
        //if range.contains(key) { // unstable as of Rust 1.23.0
        if (range.start <= key) && (key < range.end) {
            return Some(value);
        }
    }

    return None;
}

fn main() {
    let mut range_values = vec![];
    range_values.push((0..1000, "A"));
    range_values.push((1001..2000, "B"));

    println!("{:?}", get_value(&range_values, -1));   // prints None
    println!("{:?}", get_value(&range_values, 0));    // prints Some("A")
    println!("{:?}", get_value(&range_values, 500));  // prints Some("A")
    println!("{:?}", get_value(&range_values, 1000)); // prints None
    println!("{:?}", get_value(&range_values, 1500)); // prints Some("B")
    println!("{:?}", get_value(&range_values, 2500)); // prints None
}

但是，这不是最有效 的方法，尤其是当向量变大时。如果向量已排序，则执行二进制搜索 (O(log n)) 比线性扫描 (O(n)) 更有效。这假设范围不重叠。 (如果向量未排序并且您只使用它一次，那么进行线性扫描会更快，因为排序是 O(n log n)，即比单次线性扫描慢。)

use std::ops::Range;

fn get_value<'a>(range_values: &[(Range<i32>, &'a str)], key: i32) -> Option<&'a str> {
    // Find the index of the first item where `range.start <= key`.
    let index =
        match range_values.binary_search_by_key(&key, |&(ref range, _)| range.start) {
            Ok(index) => Some(index),

            // If the requested key is smaller than the smallest range in the slice,
            // we would be computing `0 - 1`, which would underflow an `usize`.
            // We use `checked_sub` to get `None` instead.
            Err(index) => index.checked_sub(1),
        };

    if let Some(index) = index {
        let (ref range, value) = range_values[index];
        if key < range.end {
            return Some(value);
        }
    }

    return None;
}

fn main() {
    let mut range_values = vec![];
    range_values.push((0..1000, "A"));
    range_values.push((1001..2000, "B"));

    // if the vector is not already sorted:
    range_values.sort_by_key(|&(ref range, _)| range.start);

    println!("{:?}", get_value(&range_values, -1));   // prints None
    println!("{:?}", get_value(&range_values, 0));    // prints Some("A")
    println!("{:?}", get_value(&range_values, 500));  // prints Some("A")
    println!("{:?}", get_value(&range_values, 1000)); // prints None
    println!("{:?}", get_value(&range_values, 1500)); // prints Some("B")
    println!("{:?}", get_value(&range_values, 2500)); // prints None
}