What is the difference between immutable arrays and immutable vectors?

What is the difference between immutable arrays and immutable vectors?

Arrays have a size known at compile time [String; 10] has 10 strings in it, no more and no less.

A Vec<String> can have elements added or removed.

1 Like

Array types are also stored directly, so [u32; 1000] is 4000 bytes either on the stack directly or in the type, which makes it more expensive to move than a vector, which directly only stores the pointer to the data, the length, and the alphabet capacity, which will be 24 bytes on a 64 bit machine, much quicker to move. (As an aside, you can use Box<[T]> to save the redundant capacity)

As a downside, the vector isn't stored directly, so it can be slower to access, though you're unlikely to notice, and doesn't have a statically determined length, which might make it harder to prove you won't access any out of bounds items and panic.

3 Likes

If you're talking about Vec<T> versus [T; N], whether they are immutable or not is just a lint-like property on the variable binding, not a type-level quality. That is, if you own a Vec<T> or a [T; N], you can mutate it.

Some differences are:

  • Vec<T> stores items in heap-allocated memory
  • [T; N] is not intrinsically on the heap; most often it's on the stack
  • Vec<T> has a dynamic length (you can add an remove a practically arbitrary number of elements)
  • [T; N] has a static (compile-time known) size of length N
  • Vec<T> is Clone if T is Clone
  • [T; N] is similar for Clone, but is also Copy if T is Copy (Vec does not)

The flexibility of Vec<T> lets it do various things arrays cannot due to their fixed length, such as (infallibly) implementing FromIterator<T>.


If you're talking about the shared borrows (aka immutable borrows) &Vec<T> versus &[T; N] versus &[T], then

  • &[T] is a borrow of some contiguous memory containing consecutive Ts; how many Ts is dynamic. The memory could be anywhere (stack, heap, static, ...)
  • &Vec<T> is a borrow of a Vec<T> (see above)
    • But you can coerce it to a &[T]
  • &[T; N] is a borrow of a [T; N] (see above)
    • But you can coerce it to a &[T]

And what is [T] itself then? It's a slice, and it is dynamically sized (aka unsized aka does not implement Sized). For these reasons you typically see it behind a reference (but can also be in a Box or Rc, et cetera). Slices underly other unsized types you'll become familiar with, like str.

7 Likes

An immutable vector cannot have elements added or removed either, just like an immutable array.

For a shared ("immutable") borrows of a Vec, i.e. for &Vec, this is true -- you can't add or remove elements through that. But whatever owns the Vec can modify it, when not borrowed; you may have to create a new mutable binding, but there's nothing that stops you from doing that.

Example.

(&mut Vec<T> and &Vec<T> are different types, in contrast.)


Even though you can't add or remove elements through a &Vec<T>, you might be able to modify some of the Ts which are already in the Vec, if they have shared mutability, aka interior mutability. Atomics are another example. I wouldn't worry about such types while you're just starting out, but I'm mentioning it to illustrate that Rust's immutability properties/terminology may not be as strict as you're interpreting.

5 Likes

The difference for each of the immutable version? Only where the memory is located - heap versus stack. No?

If I’m reading these answers correctly anything else is from comparing types other than immutable.

The Vec will likely have some additional memory allocated beyond the end of the stored items. Under certain very rare conditions, this can be soundly read via unsafe. So rare, in fact, that I’d be deeply suspicious of every unsafe block in any program that took advantage of it.

3 Likes