Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 132 ยท Collections and Iterators

Vec

Learn Rust's Vec from scratch - creating vectors, push and pop, indexing versus get, capacity, sorting, dedup, retain, drain, extend, nested vectors, vectors of enums and performance.

Vec<T> (say "vec" or "vector") is the collection you will use most in Rust. It is a growable list of values of one type, stored next to each other in memory. If you come from Python, think list; from JavaScript, Array; from C++, std::vector; from Java, ArrayList. Unlike a fixed-size array, a vector can grow and shrink while the program runs.

A Vec is an owner, as in ownership: it owns its elements, which live on the heap, and when the vector is dropped, every element is dropped with it. The vector itself is a small value on the stack made of three words: a pointer to the heap buffer, the length (how many elements are in use) and the capacity (how many fit before the buffer must be reallocated). Knowing those three numbers explains nearly everything that follows. The next lesson covers String, which is a Vec<u8> with a promise about UTF-8.

Creating vectors

There are several ways to make a vector. The most common are Vec::new() for an empty one, the vec![] macro for a literal list, and collect() from an iterator.

Rust Five ways to create a Vec

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

vec![0u8; 5] needs the element type to be Clone, because the value is cloned for each slot. An empty Vec::new() does not allocate at all, so it is free until the first push.

The type of a vector is Vec<T>. Every element has the same T. If you need to mix types, use an enum (shown below) or a vector of trait objects.

Adding and removing elements

Rust push, pop, insert, remove and friends

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Pay attention to the costs hidden in these names:

  • push and pop work at the end and are fast (amortized O(1)).
  • insert(i, x) and remove(i) must slide every element after i, which is O(n). Doing it at the front of a big vector in a loop gets slow quickly. If you need a queue, see VecDeque.
  • swap_remove(i) is O(1) but changes the order: the last element takes the freed place. Use it when order does not matter.
  • pop returns an Option<T>, because the vector might be empty. Rust makes you handle that case instead of crashing or returning garbage; see Option.

Since Rust 1.86 there is also pop_if, which pops the last element only if a condition holds:

Rust Vec::pop_if (Rust 1.86)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Reading elements: indexing versus get

You can read an element with v[i], which panics if i is out of range, or with v.get(i), which returns an Option<&T>.

Rust Indexing panics, get does not (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The last line panics with a message like index out of bounds: the len is 3 but the index is 10 and the exit code 101. A panic is a deliberate, safe crash: Rust never reads memory past the end of a vector the way C can. Use v[i] when an invalid index would be a bug in your own logic, and get when the index comes from outside (user input, a file) and you want to handle the miss.

Slices of a vector

A range index gives you a slice, a borrowed view of part of the vector (see slices). Functions that only read a sequence should take &[T], not &Vec<T>: a &Vec<T> converts to &[T] automatically, and so do arrays.

Rust Taking a slice instead of a Vec

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Borrowing rules apply to vectors

References into a vector point directly into its buffer. If the vector grew and moved its buffer, those references would dangle. Rust prevents that at compile time: you cannot change a vector while a reference into it is alive. This is the borrowing rule in action.

Rust Pushing while holding a reference (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The compiler rejects it with error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable, marking the &v[0] line as the immutable borrow, the v.push(4) line as the mutable one and the println! as the later use. The fix is to finish with first before pushing, or to copy the value out: let first = v[0]; works for Copy types like integers.

For the same reason you cannot add or remove elements inside a for x in &v loop. To modify while looping, use iter_mut for in-place changes, or retain/drain below for removals.

Rust Changing elements in place

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Capacity and growth

When a vector is full and you push again, it allocates a bigger buffer (usually double), copies the elements over and frees the old buffer. This amortized growth makes push cheap on average. But the copy is real work, and it also invalidates any pointers into the old buffer, which is why borrowing rules above exist.

Rust Length versus capacity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The standard library only promises that with_capacity(n) gives at least n, and that growth is amortized. The exact numbers can change between versions, so never write code that depends on them. The practical advice is simple:

  • If you know roughly how many elements you will add, call Vec::with_capacity(n) or reserve(n) once. It avoids repeated reallocation.
  • clear and truncate keep the capacity so that the buffer can be reused. This is useful for a vector that is refilled every iteration of a loop.
  • shrink_to_fit gives memory back after a vector shrinks a lot. Do not call it routinely.

Sorting and searching

sort arranges the elements in ascending order and needs T: Ord. It is a stable sort: equal elements keep their relative order. sort_unstable can be faster and uses no extra memory but does not promise that.

Rust Sorting vectors

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

binary_search returns Ok(index) when found, and Err(index) with the position where the value could be inserted to keep the vector sorted. A fuller discussion of ordering is in sorting, searching and comparison.

Calling sort() on a Vec<f64> does not compile: the trait bound `f64: Ord` is not satisfied. Floating-point numbers include NaN, which is not equal to itself, so they have no total order. Use sort_by(|a, b| a.total_cmp(b)) as above.

Cleaning up: dedup, retain, drain

Three methods change the contents in bulk and are much better than removing elements one at a time.

Rust dedup, retain and drain

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

retain is the idiomatic replacement for the buggy loop "walk the vector, remove some elements". It does one pass in O(n), whereas calling remove inside a loop is O(nยฒ) and also easy to get wrong because indexes shift. drain is like remove for a whole range, and it returns an iterator over what was removed; if you drop the iterator without using it, the elements are still removed.

Combining and querying

Rust extend, contains, position and chunks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

contains and position scan the vector from the start, so they are O(n). If you need many lookups by value, a HashSet or HashMap is a better fit.

Vectors of vectors

A Vec<Vec<T>> is the straightforward way to represent a grid. Each inner vector is a separate heap allocation, and the inner ones may have different lengths.

Rust A grid as Vec of Vec

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

vec![vec![0; cols]; rows] clones the inner vector rows times, so each row is independent. For big, performance-sensitive grids, a single flat Vec<T> with index r * cols + c is faster (one allocation, better cache use), at the cost of writing the index math yourself.

A vector of enums: many shapes in one list

All elements share one type, but that type can be an enum with different variants:

Rust Vec of enum values

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

See modelling with enums for more on this style.

Performance notes

Operation Cost Comment
v[i], get(i) O(1) Bounds-checked
push, pop O(1) amortized Occasional reallocation
insert(i, x), remove(i) O(n) Shifts elements after i
swap_remove(i) O(1) Does not keep order
contains, position O(n) Linear scan
sort O(n log n) Stable, allocates scratch space
sort_unstable O(n log n) No allocation, often faster
retain, dedup, drain(..) O(n) One pass
clone O(n) Copies every element

Because elements sit side by side, iterating over a Vec is very friendly to the CPU cache, which makes it hard to beat for sequential work. A frequent beginner mistake is reaching for a linked list "because inserting is cheaper": in practice a Vec wins for almost all sizes. Also remember that passing a Vec by value moves it (cheap: three words), while .clone() copies all elements. Pass &[T] or &mut Vec<T> unless the function needs to own the data.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does v[10] do on a vector with three elements?

    Indexing is bounds-checked and panics when the index is out of range. Use get(10) to receive an Option instead.
  2. 2. Why does this fail to compile? let first = &v[0]; v.push(4); println!("{first}");

    A shared reference into the vector is still alive while push needs a mutable borrow. Rust rejects this because growing the vector can move its buffer.
  3. 3. Which method removes an element in O(1) time without preserving the order?

    swap_remove moves the last element into the removed slot, so nothing needs to shift. remove must slide all later elements.
  4. 4. What does dedup() remove?

    dedup compares each element with its neighbor. Sort first if you want to remove every duplicate.
  5. 5. What is the best parameter type for a function that only reads a sequence of integers?

    A slice accepts vectors, arrays and sub-ranges alike, and does not tie the caller to Vec.

Summary

  • Vec<T> is a growable, heap-allocated list; the handle holds a pointer, a length and a capacity.
  • Create with Vec::new(), vec![...], vec![x; n], with_capacity or collect().
  • push/pop are cheap; insert/remove shift elements; swap_remove is O(1) but reorders; pop returns an Option.
  • v[i] panics when out of range; get(i) returns an Option. Take &[T] in function parameters.
  • You cannot mutate a vector while a reference into it is alive (E0502).
  • Reserve capacity when you know the size. Never rely on exact capacity numbers.
  • sort, sort_by, sort_by_key, sort_unstable; floats need total_cmp.
  • dedup, retain and drain clean up in a single pass; extend and append combine vectors.
  • Vec<Vec<T>> makes grids, Vec<Enum> mixes shapes, and a flat Vec<T> is faster for big grids.

Next: String Handling in Depth