If you don’t know what “lexicographical” means, it’s just fancy talk for alphabetical order. And if you don’t know what an STL container is… well, I can’t help you there. Don’t Worry, bro, because we’re going to learn about lexicographical comparison in the context of STL containers!
First: why do we need this fancy talk? Well, sometimes when working with STL containers (like vectors or sets), we want to sort them based on some criteria. And if that criterion is alphabetical order, then we can use lexicographical comparison to our advantage!
So let’s say you have a vector of strings and you want to sort it in alphabetical order:
// This script demonstrates how to use lexicographical comparison to sort a vector of strings in alphabetical order.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // for std::sort()
int main() {
// create a vector of strings
std::vector<std::string> my_strings = {"apple", "banana", "cherry"};
// print the unsorted vector
std::cout << "Unsorted: ";
for (const auto& str : my_strings) {
std::cout << str << ' ';
}
std::cout << '\n'; // newline character to separate output
// sort the vector using lexicographical comparison
std::sort(my_strings.begin(), my_strings.end());
// print the sorted vector
std::cout << "Sorted: ";
for (const auto& str : my_strings) {
std::cout << str << ' ';
}
std::cout << '\n'; // newline character to separate output
return 0;
}
/* Output:
Unsorted: apple banana cherry
Sorted: apple banana cherry
*/
In this example, we’re using the `std::sort()` function from the STL library. This function takes two iterators (in our case, `my_strings.begin()` and `my_strings.end()`) to specify a range of elements that should be sorted. And because we want to sort based on alphabetical order, we don’t need to provide any additional arguments or comparison functions!
But what if you have a vector of structs instead? Let’s say each struct has two fields: `name` (a string) and `age` (an integer). And let’s say you want to sort the vector based on age, but in case there are multiple people with the same age, then sort them by name. This is called a “secondary” or “tie-breaking” criterion.
// This script is used to sort a vector of structs based on age, with a secondary criterion of sorting by name in case of same age.
#include <iostream>
#include <vector>
#include#include <string>
#include <algorithm> // for std::sort() and std::less<>
// Define a struct called Person with two fields: name (a string) and age (an integer)
struct Person {
std::string name;
int age;
};
// Define a function to compare two Person structs based on age and name
bool compare_people(const Person& a, const Person& b) {
if (a.age != b.age) {
return a.age < b.age; // sort by age first
} else {
return a.name < b.name; // tie-breaker: sort by name in case of same age
}
}
int main() {
// Create a vector of Person structs and initialize it with four elements
std::vector<Person> my_people = {{ "Alice", 25 }, {"Bob", 30 }, {"Charlie", 25 }, {"Dave", 28 }};
// Print the unsorted vector
std::cout << "Unsorted: ";
for (const auto& person : my_people) {
std::cout << person.name << ',' << person.age << ' ';
}
std::cout << '\n'; // newline character to separate output
// Sort the vector using the custom comparison function
std::sort(my_people.begin(), my_people.end(), compare_people);
// Print the sorted vector
std::cout << "Sorted: ";
for (const auto& person : my_people) {
std::cout << person.name << ',' << person.age << ' ';
}
std::cout << '\n'; // newline character to separate output
return 0;
}
In this example, we’re using a custom comparison function `compare_people()`. This function takes two arguments (in our case, `const Person& a` and `const Person& b`) that represent the elements being compared. And because we want to sort based on age first, but in case of same age then by name, we’re using an if-else statement inside the comparison function!