&[start..end] is constant time right? where is this documented?

#1

I’ve been assuming so far that &v[start..end] is constant time. Is this correct? and if so, where is this documented?

#2

If v is a vec or slice then this is O(1) time, but in general it depends on the type of v! Types are free to provide an Index<Range<usize>> impl that is not constant time.

The complete implementation follows this sequence of calls:

I would be prepared to consider a PR documenting that slicing a slice is O(1) time.

9 Likes
#3

Although it doesn’t mention Index specifically, the collections module documentation has a table comparing the time complexity of various algorithms for each data structure. get is included.

3 Likes
#4

Another way to see how slicing is O(1) is to understand what &[T] actually is:

/// The layout of a fat pointer like &[T] 
struct SliceFatPtr<T> {
    /// pointer to the first element of the slice
    /// (information related to the position of the referred data)
    start: *const T,

    /// length of the slice (number of items)
    /// (information related to the size of the referred data)
    /// (because `[T]` is **not** `Sized`)
    len: usize,
}

Hence, when doing let slice = &v[start .. end], rust is creating the following struct:

let v: SliceFatPtr<_> = ...;
let slice = SliceFatPtr {
    start: v.start.offset(start as isize), // ~ "v.start + start"
    len: {
      if end > v.len { panic!("Index out of bounds"); }
      end.checked_sub(start).expect("Got start > end")
    },
};

Hence O(1).

(I haven’t talked about lifetimes because they do not exist at runtime)

1 Like