# [solved] Largest item in a possibly empty vector (without early return)

tl;dr: ok, I already solved this while writing this post and before posting, but I've decided to still post it in the hopes that someone maybe, possibly, pretty please(?) would actually find this useful. Don't read this if you're not a beginner - to save your time.

In rustbook's generics chapter there is an example of extracting a function that finds the largest item(of i32 type there) in a vector. It eventually looks like this:

``````fn largest(list: &[i32]) -> i32 {
let mut largest = list[0];

for &item in list.iter() {
if item > largest {
largest = item;
}
}

largest
}

fn main() {
let number_list = vec![34, 50, 25, 100, 65];

let result = largest(&number_list);
println!("The largest number is {}", result);

let number_list = vec![102, 34, 6000, 89, 54, 2, 43, 8];

let result = largest(&number_list);
println!("The largest number is {}", result);

let number_list = vec![]; //FIXME: How handle this case?!

let result = largest(&number_list);
println!("The largest number is {}", result);
}
``````

I notice their example does not handle empty vectors, probably because it's not relevant to the point they're trying to make in that context and thus are trying to keep things simple. But it would be really nice to mention that in the text.

For learning purposes I attempted to find a way to handle that case (when the vector is empty) and ran into some trouble.

The simple/easy way that works seems to be this(playground):

``````fn largest(list: &[i32]) -> Option<i32> {
if list.is_empty() {
return None;
}
let mut largest = list[0];

for &item in list.iter() {
if item > largest {
largest = item;;
}
}

Some(largest)
}
``````

But I'm interested in the other ways too (for learning purposes!).
One way that I want to see if can work, is without using `if`s and without returning early if the vector is empty, therefore I've the following non-working code(because `vec::get(index)` returns an `Option<&i32>` instead of `Option<i32>` thus I have to somehow reference the local variable `item` when setting `largest` (??) ):

``````fn largest(list: &[i32]) -> Option<&i32> {
let mut largest:Option<&i32> = list.get(0);

for &item in list.iter() {
if item > *largest.unwrap() {
largest = Some(&item);
}
}

largest
}
``````

`error[E0515]: cannot return value referencing local variable 'item'`

How could I make this work?
Since this is for learning purposes, I'd appreciate small hints instead of full solution unless it simply can't be done, then I need to know as such.

Oh, this is ridiculous: I just found the solution(playground):

``````fn largest(list: &[i32]) -> Option<&i32> {
let mut largest:Option<&i32> = list.get(0);

for item in list.iter() {
if item > largest.unwrap() {
largest = Some(item);
}
}

largest
}
``````

It's weird because `for item in list.iter()` used to not work before (in 2017) (on second thought, it worked just not without changing the rest of the code), and yet that link explains why:
in `for item in list.iter()` , `item` is actually an `&i32` ie. a reference to an i32
in `for &item in list.iter()` , `item` is actually an `i32` ie. an i32 (moved out from vec)

Ok, this is a bit unclear to me due to possibly implicity Copy trait being at work here, so I'm re-doing the above with a non-Copy type:
ok it worked (playground)

``````#[derive(Debug, PartialOrd, PartialEq)]
struct NonCopyI32(i32);

fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
let mut largest:Option<&NonCopyI32> = list.get(0);

for item in list.iter() {
if item > largest.unwrap() {
largest = Some(item);
}
}

largest
}
``````

And here follows the non-working variant that shows that in `for &item in list.iter()` a NonCopyI32 element moves out of the vector (but if using just `i32` instead, it would've just been copied, so non-obvious - to me) (playground):

``````#[derive(Debug, PartialOrd, PartialEq)]
struct NonCopyI32(i32);

fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
let mut largest:Option<&NonCopyI32> = list.get(0);

for &item in list.iter() {
if item > *largest.unwrap() {
largest = Some(&item);
}
//let a:u32=item; //to see type of `item`
}

largest
}
``````

(to see how the above errors if the `i32` type(or equivalent) were used instead, then only add `, Copy, Clone` to the derive line)

Well, this was fun!

1 Like

just for fun i tried to put the for loop into a `.iter().fold()` and got it running.

``````fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
list.iter().fold(None, |largest, item| match largest {
// if `item` is bigger as `largest` return `item`
Some(largest) if item > largest => Some(item),
// else return `largest`
largest @ Some(_) => largest,
// first `item` return it
None => Some(item),
})
}
``````

playground

it's even `.unwrap()` free

1 Like

You're looking at the first element twice in this approach, so I encourage you to experiment more with other ways. For example, what if you just start with `let mut largest = None;`? (And also do `smallest`, since there's a weird trick that works for largest but not for smallest.)

1 Like

This is probably not what you had in mind (since it works for `smallest` too):

``````fn largest(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
let mut largest: Option<&NonCopyI32> = None; //list.get(0);

for item in list.iter() {
if None == largest {
largest = Some(item);
continue;
} else {
if item > largest.unwrap() {
largest = Some(item);
}
}
}

largest
}
``````

because that seems somehow worse to have two `if` for each vec value instead of just one in the example that's checking first value twice.

I wonder if you expected me to use some `iter` methods perhaps not unlike `fold` in the above mind-boggling example by juggle-tux which took me a while to get

May I get another hint? assuming this is mandatory: `let mut largest = None;`, but if it's not, then I've found this variant:

``````fn largest3(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
let mut iterator = list.iter();
let mut largest:Option<&NonCopyI32> = iterator.next(); // and skip first

for item in iterator {
if item > largest.unwrap() {
largest = Some(item);
}
}

largest
}
``````

I have two other (worse)variants:

``````fn largest2_2(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
//avoid checking first item twice
let mut largest: Option<&NonCopyI32> = None; //list.get(0);

for item in list.iter() {
match largest {
//this seems worse :)
Some(x) if x < item => largest = Some(item),
Some(_) => (),
None => largest = Some(item),
}
}

largest
}

//#[derive(Debug)]
fn largest2_3(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
//avoid checking first item twice
let mut largest: Option<&NonCopyI32> = None; //list.get(0);

for item in list.iter() {
match largest {
Some(x) => if x < item { largest = Some(item) },
None => largest = Some(item),
}
}

largest
}
``````

That's essentially what I was thinking, probably just using `match largest {` and `Ord::max` to shorten it somewhat.

Edit: Looks like you did the `match` update in one of the edits I personally like the match version because it avoids the `.unwrap`, which is generally a good approach.

That's not what I was thinking, though it's certainly a good one. The standard library's implementation uses `fold`:

And you'll also see that it's using this trick you noticed:

This is one of the things I was thinking, though

For the trick one, notice that you can directly compare options: Option in std::option - Rust

Spoiler
``````#[derive(Ord, PartialOrd, Eq, PartialEq)]
struct NonCopyI32(i32);

fn largest2_3(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
let mut largest = None;

for item in list.iter() {
largest = Some(item).max(largest);
}

largest
}
``````
1 Like

Very interesting! I'm comparing `Option`s:

``````fn largest4(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
let mut iterator = list.iter();
let mut largest: Option<&NonCopyI32> = iterator.next(); //skip first

loop {
let item = iterator.next();
match item {
None => break,
i => {
if i > largest {
largest = item;
}
}
}
}

largest
}
``````

Is there a better way to match against `Some(_)` and assign the matched to `i` ? The way I did it above requires `None` to be first!

you can do

``````match item {
// if `item` is `Some(_)` assign `item` to `i`
i @ Some(_) => {...}
}
``````
1 Like

you are right i should have pointed out match guards and @ bindings

1 Like

Sweet! That's what I was looking for! (seemingly in the wrong places)

``````fn largest4_1(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
let mut iterator = list.iter();
let mut largest: Option<&NonCopyI32> = iterator.next(); //skip first

loop {
let item = iterator.next();
match item {
i @ Some(_) => {
if i > largest {
largest = item;
}
}
None => break,
}
}

largest
}
``````

I made a bunch of functions with "all" variants thus far on playground, but having trouble translating the easy solution(from OP) to `NonCopyI32`, that is, this one:

It's interesting how much Copy trait does(for the above), making me think it's "good"(or just generic enough?) code, but for a non-Copy type it needs to be changed (haven't figured out yet how)... if someone answers please hide it inside a spoiler because I'm still at it. oh I just missed the return type should be a reference:

spoiler

playground

``````fn largest_1(list: &[NonCopyI32]) -> Option<&NonCopyI32> {
if list.is_empty() {
return None;
}
let mut largest: &NonCopyI32 = &list[0];

for item in list.iter() {
if item > largest {
largest = item;;
}
}

Some(largest)
}
``````

Oh thank you! I was about to ask where to find more help about those because looking in std docs wasn't yielding much. Chapter 19 woot! I'm only at 12 so far, but looking very much forward to it!

if the return type should be a owned value there is `clone` to get it a bit more generic.

1 Like

This is the easiest way to do it:

``````pub fn largest(list: &[i32]) -> Option<&i32> {
list.iter().max()
}
``````

If you think that is cheating, using `Option::map()` and `Iterator::fold()` can be elegant and efficient:

``````pub fn largest(list: &[i32]) -> Option<&i32> {
let mut iter = list.iter();
iter.next().map(|first| {
iter.fold(first, |a, b| a.max(b))
})
}
``````
1 Like