连接数组切片 [英] Concatenate array slices

问题描述

我有两个(非常大的)数组 foo 和 bar 相同类型.为了能够编写一些漂亮的代码，我想获得两个数组连接的只读切片 result.此操作必须在 O(1) 时间和空间内运行.

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

我不想复制 foo 和 bar 的任何元素.

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

解决方案

没有预定义的类型，但是您可以通过为同时包含两者的类型实现 Index trait 来轻松创建自己的类型你的切片:

使用 std::ops::Index;struct Slice<'a, T: 'a>(&'a[T], &'a[T]);impl<'a，T:'a>索引<使用大小>对于切片a，T{类型输出 = T;fn index(&self, index: usize) ->&T {如果索引

<块引用>

更一般地，如果 result 是 k 个数组切片的串联，result 的任意数组访问应该在 O(>k).

您可以在 O(log(k)) 中访问切片，如果您的切片连接是 O(k)，通过创建一个保存累积长度的数组切片并使用二分搜索找到要索引的实际切片.

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

I have two (very large) arrays foo and bar of the same type. To be able to write some nice code, I would like to obtain a read-only slice, result, of the concatenation of the two arrays. This operation must run in O(1) time and space.

Array access for result must also be in O(1). More generally, if result were the concatenation of k array slices, an arbitrary array access for result should run in O(k).

I do not want to copy any elements of foo nor bar.

This would seem to be easy to implement into the Rust core, but no amount of searching has brought me a solution.

解决方案

There isn't a predefined type, but you can easily create your own by implementing the Index trait for a type that holds both your slices:

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()]
        }
    }
}

More generally, if result were the concatenation of k array slices, an arbitrary array access for result should run in O(k).

You can get slice access in O(log(k)), if your slice concatenation is O(k), by creating an array that holds the cumulative lengths of the slices and using a binary search to find the actual slice to index into.

This would require a macro, because we don't have a good enough constant evaluator yet and no value generics.

这篇关于连接数组切片的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！