Hello. Thank you for everything the Rust community has done! I've learned a lot and I'm hoping to learn a lot more too!

I'm writing code to intersect sorted Vec of ints. My application is a bit more complicated but I've simplified the example as much as possible and removed any custom structs. I don't need any help with the algorithmic part but I'm trying to wrap my head around how to do this. Ideally without cloning.

If there's an existing function to merge vectors that contain a type that implements Eq and Ord or other algorithmic approaches that's cool but I'd like to learn how to deal with this specific case. If this was at my day job I would ask for a code review but it isn't :(.

Apologies if this isn't the right forum to ask this.

fn main() {}

fn pairwise_intersect(x: &Vec<u32>, y: &Vec<u32>) -> Vec<u32> {
    let mut result = Vec::new();
    
    let mut i = 0;
    let mut j = 0;

    while i < x.len() && j < y.len() {
        let a = x[i];
        let b = y[j];

        if a == b {
            result.push(a);
            
            i += 1;
            j += 1;
        } else if a < b {
            i += 1;
        } else {
            j += 1;
        }
    }

    return result;
}

pub fn intersect(arrs: &Vec<Vec<u32>>) -> Vec<u32> {
    if arrs.len() == 0 {
        return Vec::new();
    }

    if arrs.len() == 1 {
        return arrs[0];
    }

    let mut x: Vec<u32> = arrs[0];

    for i in 1..arrs.len() {
        x = pairwise_intersect(&x, &arrs[i])
    }

    return x;
}

Here's the rust playground link.

With this code I get the two errors

error[E0507]: cannot move out of index of `Vec<Vec<u32>>`
  --> src/main.rs:34:16
   |
34 |         return arrs[0];
   |                ^^^^^^^ move occurs because value has type `Vec<u32>`, which does not implement the `Copy` trait
   |
help: consider cloning the value if the performance cost is acceptable
   |
34 |         return arrs[0].clone();
   |                       ++++++++

error[E0507]: cannot move out of index of `Vec<Vec<u32>>`
  --> src/main.rs:37:27
   |
37 |     let mut x: Vec<u32> = arrs[0];
   |                           ^^^^^^^ move occurs because value has type `Vec<u32>`, which does not implement the `Copy` trait
   |
help: consider borrowing here
   |
37 |     let mut x: Vec<u32> = &arrs[0];
   |                           +
help: consider cloning the value if the performance cost is acceptable
   |
37 |     let mut x: Vec<u32> = arrs[0].clone();
   |                                  ++++++++

Ok I guess that makes sense, the compiler doesn't know when to free the memory in arrs if I return it. The Book doesn't cover this particular error but from the other errors in the ownership section I'm guessing this is the reason for it.

It suggests borrowing, so I change it to a reference. Playground link.

pub fn intersect(arrs: &Vec<Vec<u32>>) -> &Vec<u32> {
    if arrs.len() == 0 {
        return &Vec::new();
    }

    if arrs.len() == 1 {
        return &arrs[0];
    }

    let mut x: &Vec<u32> = &arrs[0];

    for i in 1..arrs.len() {
        x = &pairwise_intersect(&x, &arrs[i])
    }

    return x;
}

Then I get the error

error[E0515]: cannot return reference to temporary value
  --> src/main.rs:30:16
   |
30 |         return &Vec::new();
   |                ^----------
   |                ||
   |                |temporary value created here
   |                returns a reference to data owned by the current function

error[E0515]: cannot return value referencing temporary value
  --> src/main.rs:43:12
   |
40 |         x = &pairwise_intersect(&x, &arrs[i])
   |              -------------------------------- temporary value created here
...
43 |     return x;
   |            ^ returns a value referencing data owned by the current function

For more information about this error, try `rustc --explain E0515`.

Ok I guess it makes sense, I can't return a reference to something on the stack of the current function that is about to exit. So should I put it on the heap here? And use Box ?

I'm a bit stuck. Thank you for any help!

Edit: upon reading the sticky I'm going to move this from Code Review to Help.

7 posts - 3 participants

Read full topic