7

I want to access the element next to the maximal one in a Vec<i32>. I'm looking for something like this:

let v = vec![1, 3, 2];
let it = v.iter().max_element();
assert_eq!(Some(&2), it.next());

In C++, I would go with std::max_element and then just increase the iterator (with or without bounds checking, depending on how adventurous I feel at the moment). The Rust max only returns a reference to the element, which is not good enough for my use case.

The only solution I came up with is using enumerate to get the index of the item - but this seems manual and cumbersome when compared to the C++ way.

I would prefer something in the standard library.

This example is simplified - I actually want to attach to the highest value and then from that point loop over the whole container (possibly with cycle() or something similar).

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Leśny Rumcajs
  • 2,259
  • 2
  • 17
  • 33
  • "with or without bound checking, depending on how adventurous I feel at the moment" or never do this ? That will be stupid – Stargateur Sep 25 '19 at 16:22
  • Why an iterator if you just want a value ? Why not compute the index (and the value if you want) using enumerate and fold ? – Denys Séguret Sep 25 '19 at 16:29
  • 2
    C++ iterators are like cursors; Rust iterators are based more closely on the Python model. You may want to think a little harder about the algorithm that requires `max_element` (I find most problems are a lot easier to solve with Rust-like iterators than C++-like ones, once you make the mental switch). – trent Sep 25 '19 at 16:34
  • @trentcl feels like an answer to me ;-) – Shepmaster Sep 25 '19 at 16:35
  • 1
    @Denys Let the down-votes come but I wasn't asking on opinions why I would like to do it this way for such simple case. I am asking *how* and I'd be glad for an answer with explanation or simple *you can't do this in Rust*. The example is simplified - I actually want to attach to the highest value and then from that point loop over the whole container (possibly with `cycle()` or something similar). – Leśny Rumcajs Sep 25 '19 at 16:48

3 Answers3

7

C++ iterators are not the same as Rust iterators. Rust iterators are forward-only and can only be traversed once. C++ iterators can be thought of as cursors. See What are the main differences between a Rust Iterator and C++ Iterator? for more details.

In order to accomplish your goal in the most generic way possible, you have to walk through the entire iterator to find the maximum value. Along the way, you have to duplicate the iterator each time you find a new maximum value. At the end, you can return the iterator corresponding to the point after the maximum value.

trait MaxElement {
    type Iter;

    fn max_element(self) -> Self::Iter;
}

impl<I> MaxElement for I
where
    I: Iterator + Clone,
    I::Item: PartialOrd,
{
    type Iter = Self;

    fn max_element(mut self) -> Self::Iter {
        let mut max_iter = self.clone();
        let mut max_val = None;

        while let Some(val) = self.next() {
            if max_val.as_ref().map_or(true, |m| &val > m) {
                max_iter = self.clone();
                max_val = Some(val);
            }
        }

        max_iter
    }
}

fn main() {
    let v = vec![1, 3, 2];
    let mut it = v.iter().max_element();
    assert_eq!(Some(&2), it.next());
}

See also:

I actually want to attach to the highest value and then from that point loop over the whole container (possibly with cycle() or something similar).

In that case, I'd attempt to be more obvious:

fn index_of_max(values: &[i32]) -> Option<usize> {
    values
        .iter()
        .enumerate()
        .max_by_key(|(_idx, &val)| val)
        .map(|(idx, _val)| idx)
}

fn main() {
    let v = vec![1, 3, 2];
    let idx = index_of_max(&v).unwrap_or(0);
    let (a, b) = v.split_at(idx);
    let mut it = b.iter().chain(a).skip(1);
    assert_eq!(Some(&2), it.next());
}

See also:

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
  • Thanks for clarifying. This does the thing I wanted to achieve (with added `cycle()` after `chain()`), but doesn't seem expressive at all. Moreover I am concerned about performance in this case (comparing to C++) - but this I would need to check on my own. Thanks again. – Leśny Rumcajs Sep 25 '19 at 18:50
  • Another option to iterating through all the elements is to use a BinaryHeap and pop N elements from it. – Schneems Jan 19 '23 at 03:51
7

a simple solution is to use fold, the following code produces "largest num is: 99"

    let vv:Vec<i32> = (1..100).collect();
    let largest = vv.iter().fold(std::i32::MIN, |a,b| a.max(*b));
    println!("largest {} ", largest);
Jacky_Cai
  • 81
  • 1
  • 2
2

If all you want is the value of the item following the maximum, I would do it with a simple call to fold, keeping track of the max found so far and the corresponding next value:

fn main() {
    let v = vec![1, 3, 2];
    let nxt = v.iter().fold (
        (None, None),
        |acc, x| {
            match acc {
                (Some (max), _) if x > max => (Some (x), None),
                (Some (max), None) => (Some (max), Some (x)),
                (None, _) => (Some (x), None),
                _ => acc
            }
        }
    ).1;
    assert_eq!(Some(&2), nxt);
}

playground

Depending on what you want to do with the items following the max, a similar approach may allow you to do it in a single pass.

Jmb
  • 18,893
  • 2
  • 28
  • 55