连接数组切片

Question

我有两个(非常大)的数组foo和bar相同的类型.为了能够编写一些不错的代码,我想获得result两个数组串联的只读片.此操作必须在O(1)时间和空间中运行.

数组访问result也必须在O(1)中.更一般地说,如果result是k数组切片的串联,则result应该在O(k)中运行任意数组访问.

我不想复制的任何元素foo,也没有bar.

这似乎很容易实现到Rust核心,但没有多少搜索给我带来了解决方案.

Answer 1

没有预定义的类型,但您可以通过Index为包含两个切片的类型实现特征来轻松创建自己的类型:

use std::ops::Index;

struct Slice<'a, T: 'a>(&'a[T], &'a[T]);

impl<'a, T: 'a> Index<usize> for Slice<'a, T> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        if index < self.0.len() {
            &self.0[index]
        } else {
            &self.1[index - self.0.len()]
        }
    }
}

更一般地说,如果result是k数组切片的串联,则result应该在O(k)中运行任意数组访问.

O(log(k))如果切片连接是O(k),则可以通过创建一个包含切片累积长度的数组并使用二进制搜索来查找要索引的实际切片来获取切片访问权限.

这将需要一个宏,因为我们还没有足够好的常量求值器,也没有值泛型.