Problem overview
Rust can sort numbers and strings on its own because it knows which of two of them comes first. For a struct of your own it doesn't, until the struct says so. You write a Student struct that can compare itself with another student, and a function rank_students that sorts a vector of students with the vector's own sort() and returns their names.
The rule: a student comes first if their grade is higher. When two grades are equal, the name that comes first alphabetically comes first. For Ana (90), Bob (85) and Cid (90), the answer is Ana Cid Bob: Ana and Cid tie on 90, and Ana's name is first.
Approach: implement Ord, then call sort()
A vector's sort() compares elements with the trait Ord. If Student implements it, no comparison needs to be written at the call and no sorting loop is needed. The cost is the sort's own: O(n log n) comparisons for n students, each taking constant time.
Rust's comparison traits come as a family. Ord requires PartialOrd and Eq, and those require PartialEq. The two equality traits are derived with #[derive(PartialEq, Eq)], so two students are equal when every field is. PartialOrd just asks cmp, so the rule lives in one place.
Step by step
- Declare the fields:
nameas aStringandgradeas ani32. - Write
new. It makes the&strparameter into aStringwithto_string()and stores the grade.gradealone is short forgrade: grade. - Handle different grades in
cmp.cmpreturnsOrdering::Lesswhenselfcomes first. To put the higher grade first, compare in reverse:other.grade.cmp(&self.grade). - Break ties by name. With equal grades, return
self.name.cmp(&other.name). Strings compare letter by letter, so names go from A to Z. - Write
partial_cmpasSome(self.cmp(other)). Students can always be compared, so it never returnsNone. - Sort in
rank_students. The vector is taken asmutand sorted withstudents.sort(). - Collect the names. Loop over the sorted students and push each
student.nameonto a new vector. The loop owns the students, so each name moves into the new vector without a copy.
The solution in Rust
use std::cmp::Ordering;
#[derive(PartialEq, Eq)]
struct Student {
name: String,
grade: i32,
}
impl Student {
fn new(name: &str, grade: i32) -> Student {
Student { name: name.to_string(), grade }
}
}
impl Ord for Student {
fn cmp(&self, other: &Self) -> Ordering {
if self.grade != other.grade {
return other.grade.cmp(&self.grade);
}
self.name.cmp(&other.name)
}
}
impl PartialOrd for Student {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Solution {
fn rank_students(mut students: Vec<Student>) -> Vec<String> {
students.sort();
let mut names = Vec::new();
for student in students {
names.push(student.name);
}
names
}
}
A small program that uses it, with the types above in the same file and struct Solution; added:
struct Solution;
fn main() {
let students = vec![Student::new("Ana", 90), Student::new("Bob", 85), Student::new("Cid", 90)];
println!("{}", Solution::rank_students(students).join(" "));
let ana = Student::new("Ana", 90);
let bob = Student::new("Bob", 85);
println!("{} {}", ana < bob, ana > bob);
println!("{:?} {:?}", ana.cmp(&bob), bob.cmp(&ana));
}
Ana Cid Bob
true false
Less Greater
Ana is "less than" Bob in this ordering, because "less" means "comes first". The < and > operators use partial_cmp, which asks cmp.
Rust details worth knowing
- Reversing a comparison. Swapping the two sides,
other.grade.cmp(&self.grade), turns an ascending order into a descending one. - Early return. The
ifreturns right away for different grades. The last line has no semicolon, so its value is whatcmpreturns for equal grades. - Consuming the vector.
for student in studentstakes each student out of the vector. After the loop,studentscan't be used again.
Edge cases and common mistakes
- Comparing the grades the wrong way round.
self.grade.cmp(&other.grade)would rank the lowest grade first. - Names that start alike. For equal grades,
Anncomes beforeAnna: the shorter name wins when it is the start of the other. For Max, Leo, Anna and Ann, all with 88, the order isAnn Anna Leo Max. - Different grades. Eve (55), Dan (100), Bea (0) and Cal (99) come out as
Dan Cal Eve Bea: only the grades decide. - Forgetting the derive. Without
#[derive(PartialEq, Eq)], theimpl Ordblock doesn't compile, becauseOrdneedsEq. - Writing a loop to sort. The point of the lesson is that the struct knows its own order and the language's sort does the rest.
Complexity
Sorting n students takes O(n log n) comparisons, and each call to cmp compares two grades and, at worst, two short names, so it takes constant time for names of at most 10 letters. Building the list of names is one more pass, O(n). Nothing in cmp allocates: it only borrows the two students.
What else you get from Ord
Once Student implements Ord, other standard tools work on it too, not just sort(). For the students Eve (55), Dan (100), Bea (0) and Cal (99):
let students = vec![
Student::new("Eve", 55),
Student::new("Dan", 100),
Student::new("Bea", 0),
Student::new("Cal", 99),
];
println!("{}", students.iter().min().unwrap().name);
println!("{}", students.iter().max().unwrap().name);
println!("{}", Student::new("Ann", 88) < Student::new("Anna", 88));
println!("{}", Student::new("Ann", 88) == Student::new("Ann", 88));
Dan
Bea
true
true
Here min() returns the student who comes first (Dan, the top grade) and max() the one who comes last (Bea). That can look odd at first: in this ordering, "smaller" means "ranks earlier". The ordering is whatever cmp says it is, and the standard library follows it everywhere.
One rule to keep in mind: the comparison should agree with equality. Here two students are equal when both fields match, and cmp returns Ordering::Equal only when both the grades and the names match, so the two agree. Because no two students share a name, the sort has no ties to worry about.
