[Solved] Summing a vector of refs

This is a very novice question, as I'm just trying to learn Rust by doing this year's Advent of Code in it. I'm attempting to sum up the Vec<&u32> that's coming back from an itertools operation, and if I do what I think should work, I get an error:

let sum: u32 = combination.iter().sum();  // the trait `Sum<&&u32>` is not implemented for `u32`

In order to get around this, I seemingly have to use an into_iter instead, but then the sum takes ownership, so if I want to use the vector later, I have to clone it, which seems super gross and unnecessary:

let sum: u32 = combination.clone().into_iter().sum();  // yuck

Alternatively, I can just dump sum and fold this together myself, managing the dereference with &val:

let sum = combination.iter().fold(0, |sum, &val| sum + val);

But surely there is a way to make this work conveniently with the supplied method? Thanks!

You can use combination.iter().copied().sum() to copy the individual references in the Vec, without cloning the Vec itself.

2 Likes

You can also look at this question for understanding why combination.iter() yields &&u32s:

Thanks! I actually had found that discussion and I understand the logic of why the generic iterator works this way. My question is more about what the accepted, idiomatic way is to do this type of operation. The recommendation from @mbrubeck seems reasonable, and the documentation is fairly explicit about it existing to solve this exact problem:

Creates an iterator which copies all of its elements.

This is useful when you have an iterator over &T , but you need an iterator over T .

On the other hand, in a case where those copies had an actual cost, I suppose you'd just do the fold manually? Is there something technical (or philosophical) which prevents std::iter::Sum from accepting && types?

What do you mean "actual cost"? A Copy is exactly a bitwise memcopy, nothing more, nothing less. It's never completely free, but in the overwhelming majority of cases (i.e. for small value types), it's almost free.

Writing out the loop manually doesn't make the operation any faster – there's no way around moving primitives into CPU registers from the heap in order to perform an add instruction on them.

Your manual fold is also making a copy, by using the pattern &val to destructure the reference and copy its referent into val.

iter.copied() can also be written as iter.map(|&val| val).

3 Likes

Got it, that makes sense! I think in my mind a dereference is somehow free, but yeah it makes sense that the value has to be copied onto the stack one way or another. Here's what my final solution was (to this puzzle):

    for num in 2..4 {
        for combination in numbers.iter().combinations(num) {
            let sum: u32 = combination.iter().copied().sum();
            if sum == 2020 {
                let product: u32 = combination.iter().copied().product();
                println!("{}", product);
                break;
            }
        }
    }

@H2CO3 The situation I'm thinking of would be something like where it's a series of large objects that you have a vector of refs to, and you want to do something with a singular field on those objects— maybe sum up all the values in that particular field, but without incurring the cost of copying all the containing objects. Anyway, it's a contrived example since in that case you're into custom logic anyway, but that's the idea anyway.

In that case, you can still use .map() instead of writing out an explicit loop:

#[derive(Debug, Clone)] // it's not even `Copy`
struct Huge {
    do_not_copy_me: [u64; 10_000],
    i_am_cheap: u64,
}

fn main() {
    let huger = vec![Huge {
        do_not_copy_me: [42; 10_000],
        i_am_cheap: 1337,
    }; 100];

    let sum: u64 = huger.iter().map(|x| x.i_am_cheap).sum();
    println!("sum = {}", sum);
}
1 Like

Just chiming in here again to say that I think I understand this much better after this reddit post explained it from another angle.

Basically, it's not Vec<&T> that's the problem— the sum trait actually supports ref values. The issue is Vec<&&T>, and that is happening because there are two iterators in play. There's the first iterator which feeds the combinations call, and then the second iterator to perform the sum/product operations. I found it much clearer to move the copied call up to the first iterator, so that the combinations I'm operating on are vectors of integers rather than vectors of refs to integers. So the final version is then:

    for num in 2..4 {
        for combination in numbers.iter().copied().combinations(num) {
            let sum: u32 = combination.iter().sum();
            if sum == 2020 {
                let product: u32 = combination.iter().product();
                println!("{}", product);
                break;
            }
        }
    }
1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.