Stable, Fast: Sort by Multiple Fields with Lambdas

Chapeau

Sorting data by multiple fields ensures that the primary field is sorted first, and then any ties are resolved by the secondary field. This approach is particularly useful for maintaining order in complex datasets.

Content

Let's start by defining a struct that represents our data:

struct Person {
    std::string name;
    int age;
};
    

Next, we'll create a vector of `Person` objects and sort it by the `age` field first, then by the `name` field if there are ties. We'll use the `std::stable_sort` function to ensure that the relative order of equivalent elements is preserved:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 25},
        {"David", 30}
    };

    // Sort by age, then by name
    std::stable_sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        if (a.age == b.age) {
            return a.name < b.name;
        }
        return a.age < b.age;
    });

    for (const auto& person : people) {
        std::cout << person.name << " (" << person.age << ")" << std::endl;
    }

    return 0;
}
    

In this example, the `std::stable_sort` function is used with a lambda function as the comparator. The lambda first checks if the ages are equal. If they are, it sorts by name. Otherwise, it sorts by age.

Conclusion

Using lambdas in C++ provides a powerful and flexible way to sort data by multiple fields. The `std::stable_sort` function ensures that the sorting is stable, preserving the relative order of equivalent elements. This method is both efficient and easy to implement, making it an excellent choice for complex sorting tasks.