Rollup merge of #58074 - scottmcm:stabilize-sort_by_cached_key, r=SimonSapin

Stabilize slice_sort_by_cached_key

I was going to ask on the tracking issue (https://github.com/rust-lang/rust/issues/34447), but decided to just send this and hope for an FCP here.  The method was added last March by https://github.com/rust-lang/rust/pull/48639.

Signature: https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by_cached_key
```rust
impl [T] {
    pub fn sort_by_cached_key<K, F>(&mut self, f: F)
        where F: FnMut(&T) -> K, K: Ord;
}
```

That's an identical signature to the existing `sort_by_key`, so I think the questions are just naming, implementation, and the usual "do we want this?".

The implementation seems to have proven its use in rustc at least, which many uses: https://github.com/rust-lang/rust/search?l=Rust&q=sort_by_cached_key

(I'm asking because it's exactly what I just needed the other day:
```rust
    all_positions.sort_by_cached_key(|&n|
        data::CITIES.iter()
            .map(|x| *metric_closure.get_edge(n, x.pos).unwrap())
            .sum::<usize>()
    );
```
since caching that key is a pretty obviously good idea.)

Closes #34447

14 files changed, 9 insertions, 14 deletions

diff --git a/src/liballoc/benches/lib.rs b/src/liballoc/benches/lib.rs
index 08c69ee6e85..a1884b7d548 100644
--- a/src/liballoc/benches/lib.rs
+++ b/src/liballoc/benches/lib.rs
@@ -1,5 +1,4 @@
 #![feature(repr_simd)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(test)]
 
 extern crate rand;
diff --git a/src/liballoc/slice.rs b/src/liballoc/slice.rs
index c4f4a80a017..f4b2d463778 100644
--- a/src/liballoc/slice.rs
+++ b/src/liballoc/slice.rs
@@ -257,6 +257,10 @@ impl<T> [T] {
     /// This sort is stable (i.e., does not reorder equal elements) and `O(m n log(m n))`
     /// worst-case, where the key function is `O(m)`.
     ///
+    /// For expensive key functions (e.g. functions that are not simple property accesses or
+    /// basic operations), [`sort_by_cached_key`](#method.sort_by_cached_key) is likely to be
+    /// significantly faster, as it does not recompute element keys.
+    ///
     /// When applicable, unstable sorting is preferred because it is generally faster than stable
     /// sorting and it doesn't allocate auxiliary memory.
     /// See [`sort_unstable_by_key`](#method.sort_unstable_by_key).
@@ -312,7 +316,6 @@ impl<T> [T] {
     /// # Examples
     ///
     /// ```
-    /// #![feature(slice_sort_by_cached_key)]
     /// let mut v = [-5i32, 4, 32, -3, 2];
     ///
     /// v.sort_by_cached_key(|k| k.to_string());
@@ -320,7 +323,7 @@ impl<T> [T] {
     /// ```
     ///
     /// [pdqsort]: https://github.com/orlp/pdqsort
-    #[unstable(feature = "slice_sort_by_cached_key", issue = "34447")]
+    #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")]
     #[inline]
     pub fn sort_by_cached_key<K, F>(&mut self, f: F)
         where F: FnMut(&T) -> K, K: Ord
diff --git a/src/liballoc/tests/lib.rs b/src/liballoc/tests/lib.rs
index 2b63ac5c7d2..2361a7db1f7 100644
--- a/src/liballoc/tests/lib.rs
+++ b/src/liballoc/tests/lib.rs
@@ -4,7 +4,6 @@
 #![feature(exact_size_is_empty)]
 #![feature(pattern)]
 #![feature(repeat_generic_slice)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(try_reserve)]
 #![feature(unboxed_closures)]
 #![feature(vecdeque_rotate)]
diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index acca9748372..a628fd0cfa4 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -1563,6 +1563,10 @@ impl<T> [T] {
     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
     /// deterministic behavior.
     ///
+    /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key)
+    /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_cached_key) in
+    /// cases where the key function is expensive.
+    ///
     /// # Examples
     ///
     /// ```
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index bfe59eda06e..3d79b6777fa 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -47,7 +47,6 @@
 #![feature(rustc_diagnostic_macros)]
 #![feature(rustc_attrs)]
 #![feature(slice_patterns)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(specialization)]
 #![feature(unboxed_closures)]
 #![feature(thread_local)]
diff --git a/src/librustc_codegen_llvm/lib.rs b/src/librustc_codegen_llvm/lib.rs
index b605badc153..e344f8732f8 100644
--- a/src/librustc_codegen_llvm/lib.rs
+++ b/src/librustc_codegen_llvm/lib.rs
@@ -17,7 +17,6 @@
 #![feature(nll)]
 #![feature(range_contains)]
 #![feature(rustc_diagnostic_macros)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(optin_builtin_traits)]
 #![feature(concat_idents)]
 #![feature(link_args)]
diff --git a/src/librustc_codegen_ssa/lib.rs b/src/librustc_codegen_ssa/lib.rs
index a083bd5d8d1..9e174445146 100644
--- a/src/librustc_codegen_ssa/lib.rs
+++ b/src/librustc_codegen_ssa/lib.rs
@@ -6,7 +6,6 @@
 #![feature(libc)]
 #![feature(rustc_diagnostic_macros)]
 #![feature(in_band_lifetimes)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(nll)]
 #![allow(unused_attributes)]
 #![allow(dead_code)]
diff --git a/src/librustc_driver/lib.rs b/src/librustc_driver/lib.rs
index 990ad4ada01..e022d3a3818 100644
--- a/src/librustc_driver/lib.rs
+++ b/src/librustc_driver/lib.rs
@@ -10,7 +10,6 @@
 #![cfg_attr(unix, feature(libc))]
 #![feature(nll)]
 #![feature(rustc_diagnostic_macros)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(set_stdio)]
 #![feature(no_debug)]
 #![feature(integer_atomics)]
diff --git a/src/librustc_metadata/lib.rs b/src/librustc_metadata/lib.rs
index a3490b7fea5..b4f68399d9f 100644
--- a/src/librustc_metadata/lib.rs
+++ b/src/librustc_metadata/lib.rs
@@ -6,7 +6,6 @@
 #![feature(proc_macro_internals)]
 #![feature(proc_macro_quote)]
 #![feature(rustc_diagnostic_macros)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(crate_visibility_modifier)]
 #![feature(specialization)]
 #![feature(rustc_private)]
diff --git a/src/librustc_mir/lib.rs b/src/librustc_mir/lib.rs
index 909f9695669..e0fee10cd00 100644
--- a/src/librustc_mir/lib.rs
+++ b/src/librustc_mir/lib.rs
@@ -7,7 +7,6 @@ Rust MIR: a lowered representation of Rust. Also: an experiment!
 #![feature(nll)]
 #![feature(in_band_lifetimes)]
 #![feature(slice_patterns)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(box_patterns)]
 #![feature(box_syntax)]
 #![feature(crate_visibility_modifier)]
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index fbed1145cd1..1a7744786d8 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -4,7 +4,6 @@
 #![feature(label_break_value)]
 #![feature(nll)]
 #![feature(rustc_diagnostic_macros)]
-#![feature(slice_sort_by_cached_key)]
 
 #![recursion_limit="256"]
 
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index 7055218577c..2dcb48692f6 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -67,7 +67,6 @@ This API is completely unstable and subject to change.
 #![feature(refcell_replace_swap)]
 #![feature(rustc_diagnostic_macros)]
 #![feature(slice_patterns)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(never_type)]
 
 #![recursion_limit="256"]
diff --git a/src/librustdoc/lib.rs b/src/librustdoc/lib.rs
index ddb730672d2..0b34a27794f 100644
--- a/src/librustdoc/lib.rs
+++ b/src/librustdoc/lib.rs
@@ -7,7 +7,6 @@
 #![feature(box_syntax)]
 #![feature(nll)]
 #![feature(set_stdio)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(test)]
 #![feature(vec_remove_item)]
 #![feature(ptr_offset_from)]
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index 36488b3a69f..a6145d5dcb3 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -14,7 +14,6 @@
 #![feature(nll)]
 #![feature(rustc_attrs)]
 #![feature(rustc_diagnostic_macros)]
-#![feature(slice_sort_by_cached_key)]
 #![feature(step_trait)]
 #![feature(try_trait)]
 #![feature(unicode_internals)]