slice::sort_by_key

slice methods · Collections

Level: reference · for working programmers

One line: Sort in place by a key you extract from each element.

pub fn sort_by_key<K, F>(&mut self, f: F)
where
    F: FnMut(&T) -> K,
    K: Ord,

Stable since 1.7.0.

words.sort_by_key(|w| w.len()) reads as what it is, where the sort_by spelling, |a, b| a.len().cmp(&b.len()), makes you check that a and b are on the right sides. Stable: two elements with the same key keep their order.

Descending is Reverse ↗ around the key: sort_by_key(|w| Reverse(w.len())). A tuple key sorts by several fields at once, |p| (p.dept, p.name.clone()).

Two things about the key:

• It is computed at every comparison, about n log n times, not once per element. For a cheap key — a length, a field — that is nothing. For an expensive one, to_lowercase() on every string, sort_by_cached_key ↗ computes each key once.
• It cannot borrow from the element. sort_by_key(|p| &p.0) is refused with "lifetime may not live long enough": K has no lifetime tied to the &T, so the key must be an owned value. Clone a small key, or fall back to sort_by(|a, b| a.0.cmp(&b.0)), which compares in place.

Example

slice_sort_by_key.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

use std::cell::Cell;
use std::cmp::Reverse;

fn main() {
    let mut words = vec!["pear", "fig", "apple", "kiwi"];
    words.sort_by_key(|w| w.len());
    println!("{words:?}   <- stable: pear stays before kiwi");

    words.sort_by_key(|w| Reverse(w.len()));
    println!("{words:?}   <- Reverse for descending");

    // A tuple key sorts by two fields at once.
    let mut staff = vec![("ops", "Cara"), ("dev", "Ben"), ("ops", "Ada")];
    staff.sort_by_key(|&(dept, name)| (dept, name));
    println!("{staff:?}");

    // The key is recomputed at every comparison, not once per element.
    let calls = Cell::new(0);
    let mut nums = vec![8, 3, 5, 1, 9, 2, 7, 4, 6, 0];
    nums.sort_by_key(|n| {
        calls.set(calls.get() + 1);
        *n
    });
    println!("{nums:?}   key computed more times than there are elements: {}",
             calls.get() > nums.len());

    // The key cannot borrow from the element: `|p| &p.0` is refused
    // ("lifetime may not live long enough"). Compare in place instead.
    let mut pairs = vec![(String::from("b"), 2), (String::from("a"), 1)];
    // pairs.sort_by_key(|p| &p.0);
    pairs.sort_by(|a, b| a.0.cmp(&b.0));
    println!("{pairs:?}");
}

Verified output of slice_sort_by_key.rs — regenerated by tools/run_examples.py, never hand-typed.

["fig", "pear", "kiwi", "apple"]   <- stable: pear stays before kiwi
["apple", "pear", "kiwi", "fig"]   <- Reverse for descending
[("dev", "Ben"), ("ops", "Ada"), ("ops", "Cara")]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]   key computed more times than there are elements: true
[("a", 1), ("b", 2)]

See also

• slice::sort_by — the comparison form, which can compare in place
• slice::sort — no key at all
• slice::sort_unstable — sort_unstable_by_key is the no-allocation twin

slice::sort_by_key in the standard library ↗