Rust's Vector
Tags: rust, beginners, basics, collection
Published: 2021-08-08 15:40:35

I'll be honest: I initially wanted to describe all collections available in Rust as well as their related concepts. Then, I started to dig a bit into it, and I decided it would have been (much) too long. For that reason, I'll restrict the scope to the `Vec` type.

Here's the diagram we will dive into:

![Rust's Vector "class" diagram](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eguknq7s243ysx0sgawx.png)

## Basics of Vector

From the [documentation](https://doc.rust-lang.org/std/vec/struct.Vec.html):

>A contiguous growable array type, written as `Vec<T>` and pronounced 'vector'.

Just as with Java's `ArrayList`, `Vec` is backed by an array. When the array reaches full capacity, `Vec` reserves a new array with more capacity and copies elements from the original array to the newly-created one. Then, it frees the former. Note that the collection may allocate a larger array than necessary to avoid frequent reallocations.

To add values to a `Vec`, we need to use an additional step, _e.g._, the `push()` function:

```rust
let mut v = Vec::new();
v.push(1);
v.push(5);
```

Functions that create new `Vec` initialize them with no items. If we want to create a `Vec` and values simultaneously, Rust offers the `vec!` macro. We can replace the above code with the following one-liner:

```rust
let v = vec![1, 5];
```

At that point, if you've already dabbled a bit in Rust, you probably learned nothing new. Instead of describing every function on `Vec` - they are pretty similar to those found in other languages - let's explore around a bit.

## Vector and Iterator

_Iterator_ is a design pattern described in the classic _Design Patterns: Elements of Reusable Object-Oriented Software_ book:

>**Intent:** Provide an object which traverses some aggregate structure, abstracting away assumptions about the implementation of that structure.
>
>-- [Iterator pattern](https://wiki.c2.com/?IteratorPattern)

Though the book describes _Iterator_, nothing limits the pattern to <abbr title="Object-Oriented Programming">OOP</abbr> languages. It's a pretty widespread abstraction.

Rust provides the `Iterator` trait, and `Vec` implements it. Hence, we can traverse its values:

```rust
let v = vec![1, 5];
let mut iter = v.iter();                       // 1
loop {
    let value = iter.next();                   // 2
    if value.is_some() {
        println!("value: {}", value.unwrap());
    } else {
        break;
    }
}
```

1. Create the iterator. Because calling `next()` changes the state of `iter`, it must be _mutable_.
2. Get the next value

If I had received a dollar for each bug originating from a misplaced `break` statement, I'd surely be rich now. If you break too early, you lose values; too late, and all hell breaks loose (pun intended). For that reason, `for` along with iterator is a better fit. We can rewrite the above code as:

```rust
let v = vec![1, 5];
for value in v.iter() {                        // 1
    println!("value: {}", value);
}
```

1. Shorter, safer, hence better

## Too many iterators to iterate from

Interestingly enough, we can slightly change the above code to remove the call to `iter()`. It still works!

```rust
let v = vec![1, 5];
for value in v {                               // 1
    println!("value: {}", value);
}
```

1. Magic!

That's actually not magic but Rust' syntactic sugar in action. `for` loops accept iterators. Yet, some instances can be transformed into iterators "on the fly". The type must implement the `IntoIterator` trait and its `into_iter()` function to be eligible. As seen from the diagram above, that's the case of `Vec`.

If you ask yourself the difference between `iter()` and `into_inter()`, take comfort in the fact that I wondered as well.
After some research, I found this brilliant answer:

>**TL;DR:**
>
>* The iterator returned by `into_iter` may yield any of `T`, `&T` or `&mut T`, depending on the context.
>* The iterator returned by `iter` will yield `&T`, by convention.
>* The iterator returned by `iter_mut` will yield `&mut T`, by convention.
>
-- [What is the difference between iter and into_iter?](https://stackoverflow.com/questions/34733811/what-is-the-difference-between-iter-and-into-iter)

Finally, you can create a `Vec` _from_ an `Iterator` thanks to `FromIterator`.

```rust
struct Foo {
    count: u8
}

impl Iterator for Foo {                           // 1
    type Item = u8;
    fn next(&mut self) -> Option<Self::Item> {
        match self.count {
            0 => {
                self.count = self.count + 1;
                Option::Some(1)                   // 2
            }
            1 => {
                self.count = self.count + 1;
                Option::Some(5)                   // 2
            }
            _ => None                             // 2
        }
    }
}

let i = Foo { count: 0 };
let v = Vec::from_iter(i);                        // 3
for value in v {
    println!("value: {}", value);
}
```

1. Implement our own `Iterator`
2. First, return `1`, then `5`, then nothing
3. Create a `Vec` from our iterator

## Memory allocation

We have overlooked one aspect of `Vec` so far: the definition is actually `Vec<T, A: Allocator = Global>`. While `T` is the type of items that the `Vec` contains, we didn't look at `A`, which is **what allocates memory**. I won't describe the subject in much detail because I currently lack the relevant knowledge. Yet, I believe it's interesting to mention it, as no other language I know about provides this kind of hook.

>An implementation of `Allocator` can allocate, grow, shrink, and deallocate arbitrary blocks of data described via `Layout`.
>
>-- [std::alloc::Allocator](https://doc.rust-lang.org/stable/std/alloc/trait.Allocator.html)

![Rust's Allocator "class" diagram](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/btrzjltw8jf86j11tk6f.png)

Rust uses the `Global` memory allocator by default. It delegates to another allocator: it's `System` unless you register one with the `#[global_allocator]` attribute.

With `Vec<T, A>`, it's thus possible to use a different allocator than the one defined centrally. One possible use-case would be to create an allocator that keeps track of allocated bytes only for a `Vec` instance.

## Conclusion

This concludes my dabbling in `Vec`. In this post, I tried to avoid the usual handling of this kind of post and explore a bit around. While a dedicated memory allocator won't be necessary in most cases, I think it's one good trick to keep in mind just in case.

**To go further:**

* [Module std::collections](https://doc.rust-lang.org/std/collections/index.html)
* [Storing Lists of Values with Vectors](https://doc.rust-lang.org/book/ch08-01-vectors.html)
* [Struct std::vec::Vec](https://doc.rust-lang.org/std/vec/struct.Vec.html)
* [What is the difference between iter and into_iter?](https://stackoverflow.com/questions/34733811/what-is-the-difference-between-iter-and-into-iter)

_Originally published at [A Java Geek](https://blog.frankel.ch/start-rust/9/) on August 8<sup>th</sup>, 2021_