如何获得既没有恐慌又不安全的嫌疑人？

Question

注意:如何获取子数是接近的,但没有任何约束.

我正在寻找具有此签名的函数的最佳实现:

fn sub(slice: &[u8], range: Range<usize>) -> Option<&[u8]>;

它将具有impl Index<Range<usize>>与之相同的功能,但替换故障情况None而不是恐慌.

扭曲是看似不寻常的约束,这个功能不应该:

• 调用可能的函数 panic
• 使用unsafe代码

仔细研究slice界面引起了我的注意:

• split_first 和 split_last
• split_at
• impl Index<Range<usize>> (和变种)
• as_ptr 和 from_raw_parts

但大多数都不适合:

• split_at并Index<Range<usize>>::index可能会恐慌
• from_raw_parts 是 unsafe

让我实施sub为:

fn sub(slice: &[u8], range: Range<usize>) -> Option<&[u8]> {
    if range.start > range.end { return None; }

    let length = range.end - range.start;

    if length > slice.len() { return None; }

    if length == 0 { return Some(b""); }

    let mut slice = slice;
    for _ in 0..range.start {
        if let Some((_, s)) = slice.split_first() {
            slice = s;
        }
    }

    for _ in 0..(slice.len() - length) {
        if let Some((_, s)) = slice.split_last() {
            slice = s;
        }
    }

    Some(slice)
}

虽然看似工作有O(N)的复杂性; 相当不满意.

有什么方法可以做得更好吗？

Answer 1

我将从我喜欢的版本开始.它是get_slice,它使用边界检查切片,你可以查看编译器的优化输出,以验证编译器知道它永远不会恐慌.(1.我同意,"没有恐慌"是一个很好的事情,能够作为一个断言工作; 2. get_slice将是libstd的一个很好的补充,确实是有计划的.)

/// Return the subslice corresponding to `range`, if it is in bounds
/// and well formed (start <= end).
pub fn get_slice(slice: &[u8], range: Range<usize>) -> Option<&[u8]> {
    if range.start > range.end || range.end > slice.len() {
        None
    } else {
        Some(&slice[range])
    }
}

接下来是一个尝试的解决方案,仍然用似乎是O(N)算法编码,但优化器将强度降低到O(1).

我们使用切片迭代器以及我们可以将其转换回切片的事实.切片迭代器的.nth()开放编码是在恒定时间内向前跳转,但遗憾的是反向版本没有.然而,它的循环被优化了.

pub fn sub(slice: &[u8], range: Range<usize>) -> Option<&[u8]> {
    if range.start > range.end || range.end > slice.len() {
        return None;
    }

    let mut iter = slice.iter();
    let take_front = range.start; 
    let take_back = slice.len() - range.end; 
    if take_front > 0 {
        iter.nth(take_front - 1);
    }
    if take_back > 0 {
        (&mut iter).rev().nth(take_back - 1);
    }
    Some(iter.as_slice())
}

游乐场链接

注意:遗憾的是我认为我们在这里制定了一些武断的规则.我们可以.chunks()在take front操作之后使用它,它会给你一个直接的O(1)解决方案.但是,如果要求0大小的块,块可能会出现混乱.这使得它只是使用边界检查切片为我("它可能会恐慌").

Answer 2

现在您可以get在切片上使用该方法。

我从该方法的文档中复制了下面的代码。

let v = [10, 40, 30];
assert_eq!(Some(&40), v.get(1));
assert_eq!(Some(&[10, 40][..]), v.get(0..2));
assert_eq!(None, v.get(3));
assert_eq!(None, v.get(0..4));