How can I modify elements of a vector in place in Rust?

Question

I am trying to pass an immutable reference to a Vec (a slice) to a function which will fill the Vec with incrementing values, and then iterate over them again replacing some of those values with zeroes. (The Sieve of Eratosthenes).

I think the vector should immutable (the data type and size of the vector doesn't change) but the contents of the vector should be mutable (references to integers.)

This have proven a difficult task.. I've read about mutability and borrowing, and I feel I have an OK understanding of this. I also have a cursory understanding of how referencing, dereferencing, pointers, etc. work in C, but I think I am struggling with the syntax of Rust to achieve this.

Am I thinking about this the wrong way? In Rust, is it more idiomatic to create a copy of the (potentially huge) Vec, operate on that, and return it?

This is my code so far (does not compile, many errors):

#![feature(iterator_step_by)]

pub fn nth(n: usize) {
    let size: usize = (2 as f64 * n as f64 * (n as f64).ln()) as usize;
    // Set an upper bound for seiving.
    let size_sqrt: usize = (size as f64).sqrt().ceil() as usize;
    let nums: Vec<&mut usize> = Vec::with_capacity(size);
    sieve(nums, &size, &size_sqrt);
}

fn sieve(nums: [&mut usize], size: &usize, size_sqrt: &usize) {
    for i in 0..*size {
        nums[i] = i;
    }
    for num in nums {
        if num < 2 {
            continue;
        } else if num > *size_sqrt {
            break;
        }
        for x in (num.pow(2)..size).step_by(*num) {
            nums[x] = 0;
        }
    }
}

Solution

My thinking is that the vector is immutable (the data types and size of the vector will never change) but the contents of the vector should be mutable references to integers. Or should they be the actual values of the integers themselves (and not references)?

References (&'a T and &'a mut T) can only refer to values that are owned by another value. References cannot own their referent.

It might be a good idea to build a vector of references to integers if you want to have a function that operates on some integers of a collection that are not necessarily contiguous. However, based on your code sample, that does not appear to be the case; it will be much simpler and much easier for the vector to own the integers. That means that the vector itself will need to be mutable. However, if you want to ensure that a function doesn't try to change the size of a vector, that function can accept a mutable slice of integers &mut [usize], rather than a mutable reference to the vector (&mut Vec<usize>).

In Rust, is it more idiomatic to create a copy of a potentially huge Vec, operate on that, and return it?

It depends on whether you need to use the original Vec again afterwards. If you don't, then it's more efficient to mutate the Vec in-place. If you only need to keep the original Vec in some cases and not in others, you can always clone() the Vec beforehand. If you do need the original Vec every time, then it may be more efficient to return a new Vec, especially if you can fill it from an iterator using collect, since that will try to allocate the right size ahead of time and only assign each value in the Vec once.

---

Considering all this, here's how I would write your code. Notice that I had to change the main loop in sieve to not directly iterate over nums, because that lead to a borrow conflict – the for loop needed a borrow on nums, but the assignment nums[x] would also try to take a mutable borrow on nums while the other borrow is active. I also changed the &usize parameters to usize, because there is no benefit to using references for small, copyable types such as primitive integers (in fact, it may be slightly slower).

#![feature(iterator_step_by)]

pub fn nth(n: usize) {
    let size: usize = (2.0 * n as f64 * (n as f64).ln()) as usize;
    // Set an upper bound for seiving.
    let size_sqrt: usize = (size as f64).sqrt().ceil() as usize;
    let mut nums: Vec<usize> = vec![0; size];
    sieve(&mut nums, size, size_sqrt);
}

fn sieve(nums: &mut [usize], size: usize, size_sqrt: usize) {
    for i in 0..size {
        nums[i] = i;
    }

    for i in 0..size {
        let num = nums[i];
        if num < 2 {
            continue;
        }

        if num > size_sqrt {
            break;
        }

        for x in (num.pow(2)..size).step_by(num) {
            nums[x] = 0;
        }
    }
}

Comments

[Michael Fulton]

Thank you for the thoughtful answer. This clears up multiple misunderstandings I had, especially the part about mutable vectors vs. immutable vector with mutable references.