How to sort a Vec of structs by a field

Short answer: people.sort_by_key(|p| p.age) sorts a Vec of structs by one field. The closure has to return an owned key — one that doesn’t borrow from the element it was handed — so |p| &p.name doesn’t compile. For a field that isn’t Copy, sort_by(|a, b| a.name.cmp(&b.name)) does it without cloning.

sort_by_key when the field copies out

From a fresh project (cargo new sort-structs), put this in src/main.rs and run cargo run:

struct Person {
    name: String,
    age: u32,
}

fn main() {
    let mut people = vec![
        Person { name: "Grace".to_string(), age: 85 },
        Person { name: "Ada".to_string(), age: 36 },
        Person { name: "Edsger".to_string(), age: 92 },
        Person { name: "Barbara".to_string(), age: 85 },
    ];
    people.sort_by_key(|p| p.age);
    for p in &people {
        println!("{} ({})", p.name, p.age);
    }
}

▶Run this in the Rust Playground

Ada (36)
Grace (85)
Barbara (85)
Edsger (92)

The closure receives a &Person; p.age copies the u32 out, so the key is an owned u32. Grace and Barbara are both 85, and Grace stays first: the sort is stable, so equal keys keep their input order. How to sort a Vec covers the stability promise on plain values.

The borrow that gets in the way

Change the key to name and nothing runs:

struct Person {
    name: String,
    age: u32,
}

fn main() {
    let mut people = vec![
        Person { name: "Grace".to_string(), age: 85 },
        Person { name: "Ada".to_string(), age: 36 },
        Person { name: "Edsger".to_string(), age: 92 },
        Person { name: "Barbara".to_string(), age: 85 },
    ];
    people.sort_by_key(|p| &p.name);
    for p in &people {
        println!("{} ({})", p.name, p.age);
    }
}

▶Run this in the Rust Playground

error: lifetime may not live long enough
  --> src/main.rs:13:28
   |
13 |     people.sort_by_key(|p| &p.name);
   |                         -- ^^^^^^^ returning this value requires that `'1` must outlive `'2`
   |                         ||
   |                         |return type of closure is &'2 String
   |                         has type `&'1 Person`

There’s no E-code here; it’s a lifetime error, and it’s about the closure’s shape, not String. sort_by_key’s signature says the closure returns a K that stands on its own: the sort rearranges the Vec while the comparator runs. A key pointing into an element would dangle as soon as that element moved, so the compiler refuses to tie the returned reference to its argument. How long does a borrow last? explains the rule.

The same rejection hits a field that copies in one instruction:

struct Person {
    name: String,
    age: u32,
}

fn main() {
    let mut people = vec![
        Person { name: "Grace".to_string(), age: 85 },
        Person { name: "Ada".to_string(), age: 36 },
        Person { name: "Edsger".to_string(), age: 92 },
        Person { name: "Barbara".to_string(), age: 85 },
    ];
    people.sort_by_key(|p| &p.age);
    for p in &people {
        println!("{} ({})", p.name, p.age);
    }
}

▶Run this in the Rust Playground

error: lifetime may not live long enough
  --> src/main.rs:13:28
   |
13 |     people.sort_by_key(|p| &p.age);
   |                         -- ^^^^^^ returning this value requires that `'1` must outlive `'2`
   |                         ||
   |                         |return type of closure is &'2 u32
   |                         has type `&'1 Person`
   |
help: dereference the return value
   |
13 |     people.sort_by_key(|p| *&p.age);
   |                            +

So the rule isn’t about String: the key can’t borrow from the element. The compiler’s own help names the fix — drop the &, and p.age is the owned key sort_by_key wants.

sort_by: a comparator instead of a key

For a field that isn’t Copy, the comparator form takes no key at all. Replace the sort line with this and run it again:

struct Person {
    name: String,
    age: u32,
}

fn main() {
    let mut people = vec![
        Person { name: "Grace".to_string(), age: 85 },
        Person { name: "Ada".to_string(), age: 36 },
        Person { name: "Edsger".to_string(), age: 92 },
        Person { name: "Barbara".to_string(), age: 85 },
    ];
    people.sort_by(|a, b| a.name.cmp(&b.name));
    for p in &people {
        println!("{} ({})", p.name, p.age);
    }
}

▶Run this in the Rust Playground

Ada (36)
Barbara (85)
Edsger (92)
Grace (85)

sort_by hands the closure two &Persons and wants an Ordering back. Nothing is extracted, so nothing has to be owned: the comparison borrows both names and clones nothing. sort_by_key(|p| p.name.clone()) compiles, but it allocates a String per call to the key function — the last section counts them, 12 on the four-element listing. When should you clone? covers what that costs.

Two fields

Sorting by age, then by name for ties, chains two comparators:

struct Person {
    name: String,
    age: u32,
}

fn main() {
    let mut people = vec![
        Person { name: "Grace".to_string(), age: 85 },
        Person { name: "Ada".to_string(), age: 36 },
        Person { name: "Edsger".to_string(), age: 92 },
        Person { name: "Barbara".to_string(), age: 85 },
    ];
    people.sort_by(|a, b| a.age.cmp(&b.age).then_with(|| a.name.cmp(&b.name)));
    for p in &people {
        println!("{} ({})", p.name, p.age);
    }
}

▶Run this in the Rust Playground

Ada (36)
Barbara (85)
Grace (85)
Edsger (92)

cmp returns an Ordering, and then_with runs the second comparison only when the first came out Equal. Barbara now precedes Grace: the secondary key decides the tie that stability left in input order. Plain then always computes the second comparison — same result, more work when the first key usually decides.

When the key costs something to compute

The standard library documents sort_by_key as O(m · n · log n) worst case in the key function: it is recomputed for every comparison. sort_by_cached_key calls it once per element and remembers the results. Counting the calls:

#[derive(Clone)]
struct Person {
    name: String,
    age: u32,
}

fn main() {
    let people = vec![
        Person { name: "ada".to_string(), age: 36 },
        Person { name: "Grace".to_string(), age: 85 },
        Person { name: "Edsger".to_string(), age: 92 },
        Person { name: "Barbara".to_string(), age: 85 },
    ];

    let mut by_key = people.clone();
    let mut calls = 0usize;
    by_key.sort_by_key(|p| {
        calls += 1;
        p.name.to_lowercase()
    });
    println!("sort_by_key:        {} key calls", calls);

    let mut cached = people.clone();
    let mut calls = 0usize;
    cached.sort_by_cached_key(|p| {
        calls += 1;
        p.name.to_lowercase()
    });
    println!("sort_by_cached_key: {} key calls", calls);

    for p in &cached {
        println!("{} ({})", p.name, p.age);
    }
}

▶Run this in the Rust Playground

sort_by_key:        12 key calls
sort_by_cached_key: 4 key calls
ada (36)
Barbara (85)
Edsger (92)
Grace (85)

Twelve calls for four elements, four for the cached version, and the same case-folded order either way. The counts come from the pinned 1.99.0 toolchain; the standard library documents the call pattern, not the exact number. For a key as cheap as a field read, sort_by_key is still the faster of the two: the cached version pays for a temporary buffer of keys.

Related

• How to sort a Vec — sort, sort_by and sort_unstable on plain values
• When should you clone? — what a cloned key costs
• How long does a borrow last? — the lifetime the error enforces

Next in this chapter: how to deduplicate a Vec.