在 Rust 中使用什么来代替 `std::lower_bound` 和 `std::upper_bound`？

Question

我们在 C++ 中拥有什么

C++ 有两个 STL 函数：std::lower_bound和std::upper_bound

std::lower_bound查找搜索值的第一个位置（如果存在），或者第一个值更大的位置。

std::upper_bound找到比请求值更大的第一个位置。

该函数一起允许用户找到半开迭代器范围，其中包含等于搜索值的所有值。

生锈

在 Rust 中，我们只有带有binary_search一些额外谓词的切片，但它可以返回值等于搜索到的任何位置。

我如何last value index + 1在 C++ 中找到第一个值索引或类似内容？

Answer 1

您可以使用 Rust轻松获得std::lower_bound或的行为。std::upper_boundbinary_search_by

因此，替换std::lower_bound：

use std::cmp::Ordering;

// This have exact same behaviour as C++ std::lower_bound.
let lower_bound = my_sorted_slice
    .binary_search_by(|element| match element.cmp(&searched_value) {
        // Since we try to find position of first element,
        // we treat all equal values as greater to move left.
        Ordering::Equal => Ordering::Greater,
        ord => ord,
    })
    // Since our comparator never returns `Ordering::Equal`,
    // it would always `Err(idx)`.
    .unwrap_err();

// Another version if we want to have Ok or Err
// like Rust std binary_search.
let (Ok(lower_bound) | Err(lower_bound)) = my_sorted_slice
    .binary_search_by(|element| match element.cmp(&searched_value) {
        Ordering::Equal => Ordering::Greater,
        ord => ord,
    })
    // Check what we found.
    .or_else(|idx| {
        if my_sorted_slice.get(idx) == Some(&searched_value) {
            Ok(idx)
        } else {
            Err(idx)
        }
    });

并替换std::upper_bound：

use std::cmp::Ordering;

let res: usize = my_sorted_slice
    .binary_search_by(|element| match element.cmp(&searched_value) {
        // Since we try to find position right after searched value,
        // we treat all equal values as less to move right.
        Ordering::Equal => Ordering::Less,
        ord => ord,
    })
    // Since `std::upper_bound` always return position
    // which doesn't point to searched value,
    // we would always get `Err` value from bsearch.
    .unwrap_err();