正确地为迭代器全面实现 argmax 特性

Question

我决定尝试使用一揽子实现在 Rust 中创建一个特征，要实现的测试方法是 returns 迭代器上的 argmax 和元素的特征。现在的实施是

use num::Bounded;

trait Argmax<T> {
    fn argmax(self) -> (usize, T);
}

impl<I, T> Argmax<T> for I
where
    I: Iterator<Item = T>,
    T: std::cmp::PartialOrd + Bounded,
{
    fn argmax(self) -> (usize, T) {
        self.enumerate()
            .fold((0, T::min_value()), |(i_max, val_max), (i, val)| {
                if val >= val_max {
                    (i, val)
                } else {
                    (i_max, val_max)
                }
            })
    }
}

正在使用此代码对其进行测试

fn main() {
    let v = vec![1., 2., 3., 4., 2., 3.];
    println!("v: {:?}", v);
    let (i_max, v_max) = v.iter().copied().argmax();
    println!("i_max: {}\nv_max: {}", i_max, v_max);
}

有效，而

fn main() {
    let v = vec![1., 2., 3., 4., 2., 3.];
    println!("v: {:?}", v);
    let (i_max, v_max) = v.iter().argmax();
    println!("i_max: {}\nv_max: {}", i_max, v_max);
}

不编译，并给出这些错误：

  --> src/main.rs:27:35
   |
27 |     let (i_max, v_max) = v.iter().argmax();
   |                                   ^^^^^^ method cannot be called on `std::slice::Iter<'_, {float}>` due to unsatisfied trait bounds
   |
   = note: the following trait bounds were not satisfied:
           `<&std::slice::Iter<'_, {float}> as Iterator>::Item = _`
           which is required by `&std::slice::Iter<'_, {float}>: Argmax<_>`
           `&std::slice::Iter<'_, {float}>: Iterator`
           which is required by `&std::slice::Iter<'_, {float}>: Argmax<_>`

error: aborting due to previous error

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

我认为问题源于 .iter() 循环引用，而 .iter().copied() 循环实际值，但我仍然无法理解错误消息以及如何使其通用并使用循环引用。

编辑：在被推荐尝试使用关联类型而不是泛型类型来实现上述内容之后，最终得到了这个工作实现供以后参考：

trait Argmax {
    type Maximum;

    fn argmax(self) -> Option<(usize, Self::Maximum)>;
}

impl<I> Argmax for I
where
    I: Iterator,
    I::Item: std::cmp::PartialOrd,
{
    type Maximum = I::Item;

    fn argmax(mut self) -> Option<(usize, Self::Maximum)> {
        let v0 = match self.next() {
            Some(v) => v,
            None => return None,
        };

        Some(
            self.enumerate()
                .fold((0, v0), |(i_max, val_max), (i, val)| {
                    if val > val_max {
                        (i + 1, val) // Add 1 as index is one off due to next() above
                    } else {
                        (i_max, val_max)
                    }
                }),
        )
    }
}

此实现还删除了 Bounded 作为依赖项，而是检查迭代器是否为空，如果不是，则使用迭代器返回的第一个元素初始化当前最大值。此实现 returns 它找到的第一个最大值的索引。

Answer 1

I still can't wrap my head around the error message

不幸的是，错误消息是含糊不清的，因为它没有告诉您 <&std::slice::Iter<'_, {float}> as Iterator>::Item 是什么 ，这是关键事实 — 只是它不是什么. （可能涉及 {float}，一种尚未选择的数字类型，这无济于事。我也不确定 & 在那里做什么，因为没有对迭代器的引用涉及。）

但是，如果你查找the documentation for std::slice::Iter<'a, T>，你会发现它的项目类型是&'a T，所以在这种情况下，&'a {float}。

这告诉您您已经知道的事情：迭代器超出了引用。不幸的是，错误消息并没有告诉您有关问题其余部分的太多信息。但是，如果我查看 num::Bounded 的文档，我发现 Bounded 并未针对 对数字的引用 实现。这并不奇怪，因为引用必须指向存在于内存中的值，因此构造不借用某些现有数据结构的引用可能很棘手或不可能。（我认为在这种情况下可能是可行的，但 num 尚未实现。）

and how to make it generic and working with looping over references.

只要您选择使用 Bounded 特征就不可能，因为 Bounded 没有为原始数字的引用实现，并且不可能为 &T 和 T.

（您可以为自己的类型实现 Bounded，MyWrapper<f32> 并引用它，但用户必须处理该包装器。）

这里有一些选项：

保留您当前拥有的代码，并忍受编写 .copied() 的需要。在其他迭代器中出现这种情况并不少见——不要为了避免一个额外的函数调用而使代码更复杂。
使用 return 类型 Option<(usize, T)> 编写 argmax() 的一个版本，当迭代器为空时生成 None。然后，就不需要使用 Bounded 并且代码将只使用 PartialEq 约束。此外，当迭代器为空时，它不会 return 无意义的索引和值——这通常被认为是 Rust 代码中的优点。如果 (0, T::min_value()) 适合他们的申请，来电者始终可以使用 .unwrap_or_else()。
写一个 argmax() 的版本，它采用单独的初始值，而不是使用 T::min_value().

Answer 2

PartialOrd 是 implemented for references; the issue here is that num::Bounded is not. If you make the argmax function follow the convention of returning None when the iterator is empty (as Iterator::max），你可以完全摆脱对 num::Bounded 特性的依赖：

fn argmax(self) -> Option<(usize, T)> {
    let mut enumerated = self.enumerate();
    enumerated.next().map(move |first| {
        enumerated.fold(first, |(i_max, val_max), (i, val)| {
            if val >= val_max {
                (i, val)
            } else {
                (i_max, val_max)
            }
        })
    })
}

这也允许 Argmax 为自定义（可能）非数字可比较类型的迭代器实现。

顺便说一句，您可能希望将 Argmax 特征转换为使用关联类型而不是泛型类型，只是 like Iterator.

Playground

正确地为迭代器全面实现 argmax 特性

Correctly make blanket implementation of argmax trait for iterators

generics

iterator

rust