Auto merge of #64047 - timvermeulen:cmp_min_max_by, r=cuviper

Add `cmp::{min_by, min_by_key, max_by, max_by_key}`

This adds the following functions to `core::cmp`:

- `min_by`
- `min_by_key`
- `max_by`
- `max_by_key`

`min_by` and `max_by` are somewhat trivial to implement, but not entirely because `min_by` returns the first value in case the two are equal (and `max_by` the second). `min` and `max` can be implemented in terms of `min_by` and `max_by`, but not as easily the other way around.

To give an example of why I think these functions could be useful: the `Iterator::{min_by, min_by_key, max_by, max_by_key}` methods all currently hard-code the behavior mentioned above which is an ever so small duplication of logic. If we delegate them to `cmp::{min_by, max_by}` methods instead, we get the correct behavior for free. (edit: this is now included in the PR)

I added `min_by_key` / `max_by_key` for consistency's sake but I wouldn't mind removing them. I don't have a particular use case in mind for them, and `min_by` / `max_by` seem to be more useful.

Tracking issue: #64460

1 files changed, 17 insertions, 31 deletions

diff --git a/src/libcore/iter/traits/iterator.rs b/src/libcore/iter/traits/iterator.rs
index c09df3f7f22..da49223dfb2 100644
--- a/src/libcore/iter/traits/iterator.rs
+++ b/src/libcore/iter/traits/iterator.rs
@@ -1,4 +1,4 @@
-use crate::cmp::Ordering;
+use crate::cmp::{self, Ordering};
 use crate::ops::{Add, Try};
 
 use super::super::LoopState;
@@ -2223,13 +2223,12 @@ pub trait Iterator {
             move |x| (f(&x), x)
         }
 
-        // switch to y even if it is only equal, to preserve stability.
         #[inline]
-        fn select<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> bool {
-            x_p <= y_p
+        fn compare<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> Ordering {
+            x_p.cmp(y_p)
         }
 
-        let (_, x) = select_fold1(self.map(key(f)), select)?;
+        let (_, x) = self.map(key(f)).max_by(compare)?;
         Some(x)
     }
 
@@ -2252,13 +2251,12 @@ pub trait Iterator {
     fn max_by<F>(self, compare: F) -> Option<Self::Item>
         where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,
     {
-        // switch to y even if it is only equal, to preserve stability.
         #[inline]
-        fn select<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(&T, &T) -> bool {
-            move |x, y| compare(x, y) != Ordering::Greater
+        fn fold<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(T, T) -> T {
+            move |x, y| cmp::max_by(x, y, &mut compare)
         }
 
-        select_fold1(self, select(compare))
+        fold1(self, fold(compare))
     }
 
     /// Returns the element that gives the minimum value from the
@@ -2285,13 +2283,12 @@ pub trait Iterator {
             move |x| (f(&x), x)
         }
 
-        // only switch to y if it is strictly smaller, to preserve stability.
         #[inline]
-        fn select<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> bool {
-            x_p > y_p
+        fn compare<T, B: Ord>((x_p, _): &(B, T), (y_p, _): &(B, T)) -> Ordering {
+            x_p.cmp(y_p)
         }
 
-        let (_, x) = select_fold1(self.map(key(f)), select)?;
+        let (_, x) = self.map(key(f)).min_by(compare)?;
         Some(x)
     }
 
@@ -2314,13 +2311,12 @@ pub trait Iterator {
     fn min_by<F>(self, compare: F) -> Option<Self::Item>
         where Self: Sized, F: FnMut(&Self::Item, &Self::Item) -> Ordering,
     {
-        // only switch to y if it is strictly smaller, to preserve stability.
         #[inline]
-        fn select<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(&T, &T) -> bool {
-            move |x, y| compare(x, y) == Ordering::Greater
+        fn fold<T>(mut compare: impl FnMut(&T, &T) -> Ordering) -> impl FnMut(T, T) -> T {
+            move |x, y| cmp::min_by(x, y, &mut compare)
         }
 
-        select_fold1(self, select(compare))
+        fold1(self, fold(compare))
     }
 
 
@@ -2958,28 +2954,18 @@ pub trait Iterator {
     }
 }
 
-/// Select an element from an iterator based on the given "comparison"
-/// function.
-///
-/// This is an idiosyncratic helper to try to factor out the
-/// commonalities of {max,min}{,_by}. In particular, this avoids
-/// having to implement optimizations several times.
+/// Fold an iterator without having to provide an initial value.
 #[inline]
-fn select_fold1<I, F>(mut it: I, f: F) -> Option<I::Item>
+fn fold1<I, F>(mut it: I, f: F) -> Option<I::Item>
     where
         I: Iterator,
-        F: FnMut(&I::Item, &I::Item) -> bool,
+        F: FnMut(I::Item, I::Item) -> I::Item,
 {
-    #[inline]
-    fn select<T>(mut f: impl FnMut(&T, &T) -> bool) -> impl FnMut(T, T) -> T {
-        move |sel, x| if f(&sel, &x) { x } else { sel }
-    }
-
     // start with the first element as our selection. This avoids
     // having to use `Option`s inside the loop, translating to a
     // sizeable performance gain (6x in one case).
     let first = it.next()?;
-    Some(it.fold(first, select(f)))
+    Some(it.fold(first, f))
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]