Custom Comparators in C++

Custom Comparators are used to compare the members or objects of user-defined containers (class/data structure). For example:
Consider a struct Node,

struct Node {
    int i;
    char ch;
};

Note:
Structures (also called structs) are a way to group several variables into a single data structure. Each variable in the structure is known as a member of the structure. A structure unlike vectors can contain members of different data types (int, char, etc.). The amount of memory storage used by a structure is equal to the total sum of memory storage used by each of its member variables.

Now, let’s create a custom comparator for struct Node:

//Custom comparator 
bool cmp (const Node &a, const Node &b) {
    return a.i < b.i;
}

The above comparator method cmp() take two members of struct Node (a & b) and return true if
(int) i of a < (int) i of b or a.i < b.i

And, the above custom comparator cmp when passed to the C++ STL sort method to sort an array of Node: Node a[3];
will sort the members of array a[] in a way such that ai will appear before aj in sorted a[] if:
ai.i < aj.i

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int i;
    char ch;
};

//Custom comparator 
bool cmp (const Node &a, const Node &b){
    return a.i < b.i;
}

void printArr (Node *a, int N) {
	
	for (int i=0; i<N; i++) {
	  cout<<a[i].i<<" "<<a[i].ch<<endl;
	}
	
}

int main() {

	int N = 3;
	
	Node a[N];
	a[0].i = 2;
	a[0].ch = 'b';
	a[1].i = 1;
	a[1].ch = 'a';
	a[2].i = 3;
	a[2].ch = 'c';
	
	cout<<"Array before sorting:"<<endl;
	printArr(a, N);
	
	sort(a, a+N, &cmp);
	
	cout<<"Array after sorting:"<<endl;
	printArr(a, N);

	return 0;
}

Output

Array before sorting:
2 b
1 a
3 c
Array after sorting:
1 a
2 b
3 c

Here’s a working example: Custom Sort

These are some articles utilising Custom Comparators:

  • Array Manipulation | HackerRank
    Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.
  • C++ Standard Template Library (STL) – [Linked List]
    The C++ Standard Template Library (STL) is a powerful library of C++ template classes that provide general-purpose classes and functions. 
  • Activity Selection problem
    Activity selection problem is the problem of selecting the largest set of mutually exclusive activities.
  • Tower of Babylon Solution – SPOJ
    Given n different types of blocks. Each one of them may be duplicated as many times as you like. Each type has a height y, a width x and a depth z. The blocks are to be stacked one upon each other so that the resulting tower is as high as possible.

Leave a Reply

Your email address will not be published. Required fields are marked *