Start learning free

LESSON 562 OF 568 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Sort Your Own Objects in C++: operator< and std::sort

Practice O(n log n) Read the full explanation

A language can sort numbers and strings on its own: it already knows which of two of them comes first. For objects of your own class it doesn't, until the class tells it. Every language has a way for a class to say how two of its objects compare. Once a class has it, the language's own sort can sort a list of those objects, with no comparison written at the call.

Write:

  • a class Student, created by Student(name, grade), that can compare itself with another student: a student comes first if their grade is higher; when two grades are equal, the name that comes first in alphabetical order (A to Z) comes first;
  • a method rankStudents(students) in the class Solution, which sorts the students with your language's own sort, using that comparison, and returns their names in that order.

In C++, Student defines operator<: it returns true when this student comes before other. a < b calls it, and so does sort.

Don't write your own sorting loop. The program also checks your comparison directly: for each two neighbours in the list you return, it asks Student whether the first one comes before the second.

 

Example 1:

Input: students = [("Ana", 90), ("Bob", 85), ("Cid", 90)]
Output: Ana Cid Bob
Explanation: Ana and Cid have the highest grade, 90. They tie, so their names decide: Ana comes before Cid.
Bob, with 85, comes last.

Example 2:

Input: students = [("Eve", 55), ("Dan", 100), ("Bea", 0), ("Cal", 99)]
Output: Dan Cal Eve Bea
Explanation: All the grades are different, so only the grades decide, from 100 down to 0.

Example 3:

Input: students = [("Max", 88), ("Leo", 88), ("Anna", 88), ("Ann", 88)]
Output: Ann Anna Leo Max
Explanation: Everyone has the same grade, so the list is in alphabetical order.
"Ann" comes before "Anna": when one name is the start of the other, the shorter one comes first.

 

Constraints:

  • There are 1 to 100 students.
  • 0 <= grade <= 100
  • A name has 2 to 10 letters: a capital letter, then lowercase letters. No two students have the same name.
Note:

The language's sort takes O(n log n) comparisons for n students, and each comparison takes constant time.

STEP 1 OF 9
    Ctrl + Enter to check

    C++ · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Sort Your Own Objects in C++, explained

    Problem overview

    sort can order numbers and strings because C++ already knows which of two of them comes first. For objects of your own class it knows nothing, until the class says so. In C++ a class says so by defining operator<. Once it exists, sort can order a vector of those objects, and so can the expression a < b.

    You write two things:

    • a class Student, created with Student(name, grade), whose operator< says that a student comes first if the grade is higher, and, when the grades are equal, if the name comes first in alphabetical order;
    • the method rankStudents(students) in Solution, which sorts with the language's own sort and returns the names in the new order.

    For Ana (90), Bob (85) and Cid (90) the result is Ana Cid Bob. Ana and Cid tie at the highest grade, so their names decide, and Ana comes before Cid. Bob, with 85, comes last.

    Approach: define "comes before", then let sort do the work

    Writing a sorting loop would be extra work and an extra place for bugs. The better idea is to teach the class its own order and call sort with no comparison argument. sort uses < on the elements, so it picks up your operator<.

    What operator< must answer is: "does this student come before other?" That has two rules, in this order:

    1. If the grades differ, the higher grade comes first. So the result is whether grade > other.grade. Notice the direction: the operator is called <, but "less" here means "earlier in the ranking", so the higher grade is the one that is "smaller".
    2. If the grades are equal, the names decide. Comparing two strings with < goes letter by letter, so names go from A to Z. When one name is the start of another, the shorter one is first: Ann comes before Anna.

    The names are all different, so two students are never equal on both rules.

    Step by step

    1. Under public:, declare string name; and int grade;. They are public because rankStudents reads each name.
    2. In the constructor, store the parameters with this->name = name; and this->grade = grade;.
    3. In operator<, check whether the grades differ. If so, return grade > other.grade.
    4. Otherwise return name < other.name.
    5. In rankStudents, call sort(students.begin(), students.end()), with no third argument.
    6. Declare an empty vector<string> names and loop over the sorted students, pushing each student.name.
    7. Return names.

    The solution in C++

    class Student {
public:
    string name;
    int grade;

    Student(string name, int grade) {
        this->name = name;
        this->grade = grade;
    }

    bool operator<(const Student& other) const {
        if (grade != other.grade) {
            return grade > other.grade;
        }
        return name < other.name;
    }
};

class Solution {
public:
    vector<string> rankStudents(vector<Student> students) {
        sort(students.begin(), students.end());
        vector<string> names;
        for (Student& student : students) {
            names.push_back(student.name);
        }
        return names;
    }
};

    A run

    Ranking the students of the other two examples gives:

    Dan Cal Eve Bea
Ann Anna Leo Max

    The first list was Eve (55), Dan (100), Bea (0) and Cal (99). All the grades differ, so only the grades decide. In the second list all four students have 88, so the list is in alphabetical order.

    The operator also works by itself. With Student a("Ana", 90), Student c("Cid", 90) and Student b("Bob", 85), the expressions a < c, c < a, a < b, b < a and a < a give true, false, true, false and false. The last one matters: a student never comes before itself. That matches what sort expects of a comparison.

    Details that matter

    • The header. bool operator<(const Student& other) const takes the other student by reference, so nothing is copied, and the const after the parameter list promises that comparing doesn't change the student. Both are the usual way to write it.
    • Parameters and fields. They share their names in the constructor, so this->name is the field and plain name is the parameter.
    • The vector is a copy. rankStudents takes the vector by value, so sorting it doesn't change the caller's vector.
    • The loop variable. Student& student uses each element in place instead of copying it.

    Complexity

    For n students, sort makes O(n log n) comparisons, and each comparison takes constant time for names of at most 10 letters. Building the list of names takes O(n). The total is O(n log n) time. The copy of the vector and the vector of names take O(n) extra space.

    Edge cases and common mistakes

    • The wrong direction on grades. With grade < other.grade, the lowest grade ranks first. Ana, Bob and Cid come out as Bob Ana Cid instead of Ana Cid Bob.
    • The wrong direction on names. With name > other.name for equal grades, Ana and Cid swap, and the all-88 list comes out as Max Leo Anna Ann, from Z to A.
    • Forgetting the name rule. If the operator only compares grades, students with equal grades are considered equal, and sort doesn't promise any particular order for equal elements. The names must be the tie-breaker.
    • Returning true for equal students. An operator written with <= or >= breaks the rule that sort relies on: a value is never before itself. Use strict comparisons.
    • Writing your own sorting loop. The lesson wants sort with the class's own comparison.

    Testing

    StudentsResult
    Ana 90, Bob 85, Cid 90Ana Cid Bob
    Eve 55, Dan 100, Bea 0, Cal 99Dan Cal Eve Bea
    Max 88, Leo 88, Anna 88, Ann 88Ann Anna Leo Max
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free