Repository: rust-itertools/itertools (language: rust)

Issue:
Suggestion: sorted_by_cached_key
Suggestion: sorted_by_cached_key

Like `sorted_by_key` but caching keys like [`slice::sort_by_cached_key`](https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by_cached_key).

Please add it, it would be very useful :)


Discussion / hints:

Fix patch:
diff --git a/src/lib.rs b/src/lib.rs
index 55c895844..37d2d52ff 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -2667,6 +2667,43 @@ pub trait Itertools : Iterator {
         v.into_iter()
     }
 
+    /// Sort all iterator elements into a new iterator in ascending order. The key function is
+    /// called exactly once per key.
+    ///
+    /// **Note:** This consumes the entire iterator, uses the
+    /// [`slice::sort_by_cached_key`] method and returns the result as a new
+    /// iterator that owns its elements.
+    ///
+    /// The sorted iterator, if directly collected to a `Vec`, is converted
+    /// without any extra copying or allocation cost.
+    ///
+    /// ```
+    /// use itertools::Itertools;
+    ///
+    /// // sort people in descending order by age
+    /// let people = vec![("Jane", 20), ("John", 18), ("Jill", 30), ("Jack", 27)];
+    ///
+    /// let oldest_people_first = people
+    ///     .into_iter()
+    ///     .sorted_by_cached_key(|x| -x.1)
+    ///     .map(|(person, _age)| person);
+    ///
+    /// itertools::assert_equal(oldest_people_first,
+    ///                         vec!["Jill", "Jack", "Jane", "John"]);
+    /// ```
+    /// ```
+    #[cfg(feature = "use_alloc")]
+    fn sorted_by_cached_key<K, F>(self, f: F) -> VecIntoIter<Self::Item>
+    where
+        Self: Sized,
+        K: Ord,
+        F: FnMut(&Self::Item) -> K,
+    {
+        let mut v = Vec::from_iter(self);
+        v.sort_by_cached_key(f);
+        v.into_iter()
+    }
+
     /// Sort the k smallest elements into a new iterator, in ascending order.
     ///
     /// **Note:** This consumes the entire iterator, and returns the result


Test patch:
diff --git a/tests/test_std.rs b/tests/test_std.rs
index 819995861..2049d1597 100644
--- a/tests/test_std.rs
+++ b/tests/test_std.rs
@@ -510,6 +510,30 @@ fn sorted_by_key() {
     it::assert_equal(v, vec![4, 3, 2, 1, 0]);
 }
 
+#[test]
+fn sorted_by_cached_key() {
+    // Track calls to key function
+    let mut ncalls = 0;
+
+    let sorted = [3, 4, 1, 2].iter().cloned().sorted_by_cached_key(|&x| {
+        ncalls += 1;
+        x.to_string()
+    });
+    it::assert_equal(sorted, vec![1, 2, 3, 4]);
+    // Check key function called once per element
+    assert_eq!(ncalls, 4);
+
+    let mut ncalls = 0;
+
+    let sorted = (0..5).sorted_by_cached_key(|&x| {
+        ncalls += 1;
+        -x
+    });
+    it::assert_equal(sorted, vec![4, 3, 2, 1, 0]);
+    // Check key function called once per element
+    assert_eq!(ncalls, 5);
+}
+
 #[test]
 fn test_multipeek() {
     let nums = vec![1u8,2,3,4,5];