Concatenate array slices

Question

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.

Answer 1

I'm afraid what you are asking is pretty much impossible if you require the result to be an actual slice. A slice is a view into a block of memory. Contiguous memory. If you want a new slice by combining two other slices you have to copy the contents to a new location, so that you get a new contiguous block of memory.

If you are satisfied just concatenating by copying SliceConcatExt provides the methods concat and join on slices, which can be used on slices of custom types as long as they implement Clone:

#[derive(Clone, PartialEq, Debug)]
struct A {
    a: u64,
}

fn main() {
    assert_eq!(["hello", "world"].concat(), "helloworld");
    assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
    assert_eq!([[A { a: 1 }, A { a: 2 }], [A { a: 3 }, A { a: 4 }]].concat(),
               [A { a: 1 }, A { a: 2 }, A { a: 3 }, A { a: 4 }]);
}

Note that even though SliceConcatExt is unstable, the methods themselves are stable. So there is no reason not to use them if copying is OK. If you can't copy you can't get a slice. In that case, you need to create a wrapper type, as explained in the answer of ker.

Answer 2

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.