Comparator in C++
In C++, a comparator is a function or a function (an object that acts like a function) that is used to compare elements. It is widely used in sorting algorithms or in data structures like std::sort or std::priority_queue to define custom sorting orders. It can be used to define specific rules for comparing elements, influencing the order in which they appear.
The comparator function generally takes two parameters (values to compare) and returns a boolean value based on their comparison. Such functions are also called binary predicate. Although, there is no limitation on the number or parameters the comparator function can take.
How to Create a Comparator in C++?
In C++, we can create a comparator function using four methods. They are:
- Using Function Pointer
- Using Lambda Expression
- Using Functors
1. Comparator Using Function Pointer
In this method, we define a function that implements the comparison logic and returns some value. Then we use the pointer to this function as the comparator.
Example
The below example shows the program to create a comparator using a function pointer.
C++
// C++ program to create comparator using function pointer #include <algorithm> #include <iostream> #include <vector> using namespace std; // Custom comparison function bool customComparison( int a, int b) { // Custom comparison logic return a < b; // it sorts in ascending order } int main() { // Creating a vector of integers vector< int > myVec = { 7, 5, 2, 1, 4, 3 }; // Using sort with a function pointer sort(myVec.begin(), myVec.end(), customComparison); // Displaying the sorted vector cout << "Sorted Vector: " ; for ( int num : myVec) { cout << num << " " ; } cout << endl; return 0; } |
Sorted Vector: 1 2 3 4 5 7
2. Comparator Using Lambda Expression
Lambda expressions can be used to declare the inline function definitions. We can also use the lambda expression to create a comparator just like we can do with function. Moreover, we can declare the lambda expression in a place where the comparator is required.
Example
The below example shows the program to create a comparator using the lambda function.
C++
// C++ program to create comparator using Lambda function #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { // Creating a vector of integers vector< int > myVec = { 4, 3, 8, 1, 7, 2 }; // Using sort() with a lambda function sort(myVec.begin(), myVec.end(), []( int a, int b) { // Custom comparison logic return a < b; // this sorts in ascending order }); // printing sorted vector cout << "Sorted Vector: " ; for ( int i : myVec) { cout << i << " " ; } cout << endl; return 0; } |
Sorted Vector: 1 2 3 4 7 8
3. Comparator Using Functor (Function Object)
A functor (Function Object) is a class or struct that overloads the operator() such that it behaves as a function when called. We can also use such objects as a comparator by defining the comparison logic inside the () operator overloading function.
Example
The below example shows the program to create a comparator using a functor.
C++
// C++ program to create comparator using functor #include <algorithm> #include <iostream> #include <vector> using namespace std; // defining Functor (Function Object) struct Comparator { bool operator()( int a, int b) const { // Custom comparison logic return a < b; // this sorts in ascending order } }; int main() { // Creating a vector of integers vector< int > myVec = { 9, 2, 4, 1, 6, 3 }; // Using sort() with a functor (function object) sort(myVec.begin(), myVec.end(), Comparator()); // Printing the sorted vector cout << "Sorted Vector: " ; for ( int i : myVec) { cout << i << " " ; } cout << endl; return 0; } |
Sorted Vector: 1 2 3 4 6 9
4. Function Object with State (Using a Class)
In this method, we create a functor with a parameterized constructor that stores additional state information for comparison. This information can be anything that you want to use as a metric for state.
Example
The below example shows a program to create custom comparator using a class.
C++
//C++ program to create custom comparator using a class. #include <iostream> #include <vector> #include <algorithm> using namespace std; // Function object with state class CustomComparator { public : CustomComparator( int baseValue) : baseValue_(baseValue) {} bool operator()( int a, int b) const { // Custom comparison logic involving state return (a % baseValue_) < (b % baseValue_); } private : int baseValue_; }; int main() { // Creating a vector of integers vector< int > myVector = {12, 24, 8, 13, 27, 40}; // Using sort with a function object with state sort(myVector.begin(), myVector.end(), CustomComparator(5)); // printing the sorted vector cout << "Sorted Vector: " ; for ( int num : myVector) { cout << num << " " ; } cout << endl; return 0; } |
Sorted Vector: 40 12 27 8 13 24
Application of Comparator in C++
In C++, comparator is widely used in many different cases. Some of the common application of comparators is as follows:
1. Sort the Characters in increasing frequency.
It can be used to count and sort characters in the string based on increasing frequency using a custom comparator.
Example
The below example demonstrates the use of comparator to sort the characters in increasing frequency.
C++
// C++ program to demonstrate the use of comparator to sort the characters in increasing frequency. #include <iostream> #include <map> #include <algorithm> using namespace std; int main() { string s = "Heellloooo" ; // Creating a map to store the frequency of each character map< char , int > mp; // Counting the frequency of each character in the string for ( int i = 0; i < s.length(); i++) { mp[s[i]]++; } // Lambda function 'compare' to serve as a custom comparator for sorting auto compare = [&]( char a, char b) { return mp[a] > mp[b]; }; // Sort the string based on character frequency using the custom comparator sort(s.begin(), s.end(), compare); // Display the sorted string based on character frequency cout << s; return 0; } |
oooollleeH
Explanation
The above program defines a lambda function called compare that takes two characters a and b as parameters.The lambda function compares the frequencies of characters a and b based on their occurrences in the above-used map. It returns true if the frequency of character a is greater than the frequency of character b. If ‘true’ arises from the comparator, then ‘a’ precedes ‘b’ in this example. Otherwise, if ‘false’, the order reverses—’b’ precedes ‘a’ it then sorts the string and print it.
2. Sort characters in increasing frequency and same frequency in decreasing alphabetical order.
It can be used to count and sort characters in the string based on increasing frequency and same frequency using a custom comparator.
Example
The below example demonstrates the use of comparator to sort the characters in increasing frequency and same frequency in decreasing alphabetical order.
C++
// C++ program to demonstrate the use of comparator to sort // the characters in increasing frequency and same frequency // in decreasing alphabetical order. #include <iostream> using namespace std; #include <algorithm> #include <map> int main() { // Input string string s = "hellloooo geek" ; // Creating a map to store the frequency of each // character map< char , int > mp; // Counting the frequency of each character in the // string for ( int i = 0; i < s.length(); i++) { mp[s[i]]++; } // here Lambda function 'compare' to serve as a custom // comparator for sorting auto compare = [&]( char a, char b) { if (mp[a] == mp[b]) { return a > b; } return mp[a] > mp[b]; }; // Sort the string based on character frequency using // the custom comparator sort(s.begin(), s.end(), compare); // print sorted string based on character frequency cout << s; return 0; } |
oooollleeekhg
Explanation
auto compare = [&](char a, char b) { /* … */ }: Defines a lambda function called compare that takes two characters a and b as parameters.Inside the lambda it checks if the frequencies of characters a and b are equal.return a > b;: If frequencies are equal, sorts the characters in descending order.return mp[a] > mp[b];: Otherwise, sorts characters by their frequencies, with higher frequencies coming first.If ‘true’ arises from the comparator, then ‘a’ precedes ‘b’ in this example. Otherwise, if ‘false’, the order reverses—’b’ precedes ‘a’.
3. Sort numbers by increasing set bit count
It is used to sort a vector of integers based on the number of set bits using a lambda function as the custom comparator.
Example
The below example shows a program to sort a vector by increasing set bit count.
C++
#include <iostream> using namespace std; #include <bits/stdc++.h> int main() { // Initializing a vector of integers vector< int > p = { 1, 5, 8, 13, 2, 17 }; // Lambda function 'lamda' to compare integers based on // the number of set bits (population count) auto lamda = [&]( int a, int b) { return __builtin_popcount(a) < __builtin_popcount(b); }; // Sort the vector 'p' based on the number of set bits // using the custom lambda comparator sort(p.begin(), p.end(), lamda); // print the sorted vector for ( auto it : p) { cout << it << " " ; } return 0; } |
1 8 2 5 17 13
Explanation
In above example __builtin_popcount(a): It returns the number of set bits (1s) in the binary representation of integer a. __builtin_popcount(b): Returns the number of set bits (1s) in the binary representation of integer b.The lambda function compares the number of set bits in integers a and b and returns true if the number of set bits in a is less than the number of set bits in b.If ‘true’ arises from the comparator, then ‘a’ precedes ‘b’ in this example. Otherwise, if ‘false’, the order reverses—’b’ precedes ‘a’. Here, the sorting process and comparator work collectively, examining every possible pair and arranging the elements accordingly.
4. Segregate even odd numbers and even numbers first.
We can used comparator to sort a vector of integers to segregate even and odd numbers, placing even numbers before odd numbers.
Example
The below example shows a program to Segregate even odd numbers and even numbers before odd numbers.
C++
// C++ program to Segregate even odd numbers and even // numbers before odd numbers. #include <iostream> using namespace std; #include <algorithm> #include <vector> int main() { // Initialize a vector of integers vector< int > p = { 1, 2, 3, 4, 5, 6, 7 }; // Lambda function 'compare' to segregate even and odd // numbers, placing even numbers before odd numbers auto compare = [&]( int a, int b) { return a % 2 < b % 2; }; // Sort the vector 'p' based on the segregation criteria // using the custom lambda comparator sort(p.begin(), p.end(), compare); // printing vector after segregation cout << "after segregation: " ; for ( auto it : p) { cout << it << " " ; } return 0; } |
after segregation: 2 4 6 1 3 5 7
Explanation
Lambda function named compare takes two integers a and b as parameters and compares a%2 with b%2 and return a % 2 < b % 2. This comparison places even numbers before odd numbers because even numbers have a remainder of 0 when divided by 2, while odd numbers have a remainder of 1. If ‘true’ arises from the comparator, then ‘a’ precedes ‘b’ in this example. Otherwise, if ‘false’, the order reverses—’b’ precedes ‘a’.
Conclusion
In conclusion, comparators in C++ are very important, mainly in sorting algorithms and data structures. There are various methods to create comparators like using Function Pointer, Lambda Function, Functor (Function Object, and Function Object with State (Using a Class) etc. Each method has a unique approach to customize the sorting logic according to the requirement.
Contact Us