Sort Objects in C++ List Through Compare Predicate - With Example

Updated on February 5, 2018
sirama profile image

I am a software engineer. I have been working with C++, MFC, and .net technologies for 15 years. I like playing video games & reading books.

1. What is the need for Compare Predicate?

We know that sorting can be performed by comparing two elements and arranging the elements either in ascending order or in descending order. For any programming API, this will be an easy task when the elements fall under standard data types like integers, floats, etc. Now, when the type is user-defined, say for example; class instance, the API may not know how to sort the elements. Or, even if it does it may not be the way we want it. And, this is where the need for the “Compare Predicate” comes into the picture.

In this article, we will create a Department class and sort the instances of it through a couple of compare predicates. Let us start.

2. The Department Class - To Explain C++ List Sort

The below code shows the complete department class:

//ListSort 01: Department class fot this Hub
class Department
{
private:
	//1.1: Private Members
	int m_DeptID;
	string m_DeptName;
	int m_NumberOfStaffs;

public:
	//1.2: Department Class Constructor
	Department(int id, string name, int total_emp)
	{
		m_DeptID = id;
		m_DeptName = name;
		m_NumberOfStaffs = total_emp;
	}

	//1.3: Getter Functions
	int GetDeptId() 
	{
		return m_DeptID;
	}

	int GetNumberOfStaffs()
	{
		return m_NumberOfStaffs;
	}

	//1.4: Print Content of the Department Class
	void Print_Department()
	{
		cout << "Department - " << m_DeptName << "  ID:"
			<< m_DeptID << ", Total Staffs - " 
			<< m_NumberOfStaffs << endl;
	}
};

Code snippet 1.1: Members

The department class has three members to store department id, name and number of staff employed by the department. This is shown in the code snippet 1.1

Code snippet 1.2: Department constructor

The constructor takes three parameters and uses those passed-in parameters to initialize all its members. Note that our class does not have any other constructors and there is no default constructor as well. This will make sure initializing all the data member with the valid data during construction itself.

Code Snippet 1.3: Getter Functions

We gave two getter functions which will return the private members m_DeptID and m_NumberOfStaffs.

Code Snippet 1.4: Printing the Department information

The Print_Department() member of the Department class prints the Department data into the console output window. Here, we are using the C++ iosteam to list of out the members along with the concatenated string. That’s all about the Department class and let us explore some of the global function that deals with this department class instances and c++ standard list.

3. Adding Department class instance to C++ List

The global function Add_ListElements takes the C++ Standard List as parameter and adds the department instances into it. Function code is below:

//ListSort 02: Function to Push some values to List
void Add_ListElements(list<Department>& listParam)
{
	//2.1: Clear the List
	listParam.clear();

	//2.2: Create Department Objects
	const Department D1(3, "Civil           ", 20);
	const Department D2(1, "Mechanical      ", 60);
	const Department D3(5, "Electrical      ", 22);
	const Department D4(4, "Chemical        ", 34);
	const Department D5(2, "Computer Science", 35);

	//2.3: Add Department Objects to List
	listParam.push_back(D1);
	listParam.push_back(D2);
	listParam.push_back(D3);
	listParam.push_back(D4);
	listParam.push_back(D5);
}

Code Snippet 2.1

Whenever we call the Add_ListElements(), it should add five default departments to the supplied C++ list for demo purpose. Hence, first, we are clearing the list by calling the standard list clear() function.

Code Snippet 2.2

Five department objects are constructed and note that all the instances are kept constant as we are not going to change the instance members and we will perform only sorting on this demo departments.

Code Snippet 2.3

We are storing the departments one by one into the c++ standard list by making use of the push_back() function call.

4. Iterating Department class Instances in C++ List

The Print_List() is written to iterate through the supplied list and prints information about the department class in the console window. In each iteration, we retrieve the Department class instance and make a call to its member Print_Department() to print the department information Id, Name etc. The function below:

//ListSort 03: Function to Print the Values in List
void Print_List(list<Department> listParam)
{
	list<Department>::iterator listItr;
	printf("\nThe contents of the Lists are:\n");
	for (listItr = listParam.begin();
		listItr != listParam.end();
		listItr++)
	{
		(*listItr).Print_Department();
	}
}

5. Compare Predicates for sorting Departments in the List

The Standard list “sort()” function does not know how to sort C++ user-defined types say Structures, Class objects, etc. Through “Compare Predicates”, we can teach the Sort() function when it should perform the swapping.

The Compare Predicate expects two parameters and returns a Boolean. Let us say the parameters are First and Second and the body of the predicate should tell this order is right or wrong. When we say the order is right, we should return true otherwise false. When the predicate returns false, the sort() function of the standard list knows that Second and First should be swapped so that Second goes first in the sorting order.

Note that the First and Second parameter should match with the data type of the container (In this example it is Department).

5.1 Compare Predicate – Sort By Department ID

Our first predicate function tells how to sort the department by its department id. Have a look at the predicate function below:

//ListSort 04a: Predicate function to sory by 
// Department IDs in Ascending order
bool Compare_IDS_Predicate_Asc(
	Department First, Department Next)
{
	//First Argument Stays First (Return true)
	if (First.GetDeptId() < Next.GetDeptId()) 
		return true; 

	//First Argument goes Next (Swap) (Return false)
	if (First.GetDeptId() > Next.GetDeptId()) 
		return false;

	//a==b. First Argument Stays first 
	//(No need to Swap)
	return true;
}

In the above code, we are telling how to sort the department id in Ascending Order. When parameter First is lower than parameter Second, we don’t want to swap it, and hence we return true. When the first parameter is higher than the second one, we return false a statement that swapping is required. When both parameters First and Second has same value, we return false stating that no swapping is required. We can even return true, but the swapping has no effect here.

5.2 Compare Predicate – Sort By Number of Staffs

The second predicate is written to perform the sorting in Descending Order. Note that how the operator "<" and ">" is used and how it different perform the previous predicate function which performs sorting in Ascending Order. The code for the second predicate is given below:

//ListSort 04b: Predicate function to sort by
// NumberOf Employees - descending
bool Compare_TotEmps_Predicate_Desc(
	Department First, Department Next)
{
	//First Argument Stays First (Return true)
	if (First.GetNumberOfStaffs() > 
		Next.GetNumberOfStaffs()) 
		return true;

	//First Argument goes Next 
	//(Swap) (Return false)
	if (First.GetNumberOfStaffs() < 
		Next.GetNumberOfStaffs()) 
		return false;

	//a==b. First Argument Stays 
	//first (No need to Swap)
	return true;
}

OK. Now it is time to create the C++ List, store the Department instances in it and perform sorting through our predicate functions. Let us move ahead!

6. C++ Compare Predicate in action

OK. First, let us prepare the List and print it on the console output window. First, we used our global function Add_ListElements() by passing the C++ Standard List as a parameter. The function packs five same Department in the passed-in list. Next, we are supplying Department packed list to the global function Print_List() to print the content of the List. The code is below:

//3.1 Create list and iterator
list<Department> theList;
Add_ListElements(theList);
Print_List(theList);

At this stage, we have a C++ Standard List which has five Department object in it. This is shown in below picture:

Department Class Object Stored in C++ Std. List
Department Class Object Stored in C++ Std. List | Source

Next, we are sorting Department objects by its ID. To sort the department by ID, we are passing the Predicate function Compare_IDS_Predicate_Asc to "Sort()" method of the List. Now, sort method knows how to sort the department object. It iterates through the C++ List and makes use of the predicate function Compare_IDS_Predicate_Asc to decide the order between to side-by-side department object in the list. After the call to Sort(), the Departments in the lists are ordered in Ascending by it department IDs, and We print the list to console output window.

The same way by making use of the predicate function Compare_TotEmps_Predicate_Desc, we are calling the sort() method again. This time the list will be sorted by the Number Of Staffs in the department in descending order. The code snippet is below:

//3.2 Sort the List by IDs
printf("\nSorting List By ID:\n");
theList.sort(Compare_IDS_Predicate_Asc);
Print_List(theList);

//3.3 Sort the List by Department
printf("\nSorting List By Number of Staffs\n");
theList.sort(Compare_TotEmps_Predicate_Desc);
Print_List(theList);

The two sort operation is illustrated as shown below:

C++ Objects Sorted by Compare predicates & Std List Sort() Function
C++ Objects Sorted by Compare predicates & Std List Sort() Function | Source

The complete code Example - C++ List Sort() with Compare Predicates

//ListSort00: Required Includes
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <list>
#include <string>

using namespace std;

//ListSort 01: Department class fot this Hub
class Department
{
private:
	//1.1: Private Members
	int m_DeptID;
	string m_DeptName;
	int m_NumberOfStaffs;

public:
	//1.2: Department Class Constructor
	Department(int id, string name, int total_emp)
	{
		m_DeptID = id;
		m_DeptName = name;
		m_NumberOfStaffs = total_emp;
	}

	//1.3: Getter Functions
	int GetDeptId() 
	{
		return m_DeptID;
	}

	int GetNumberOfStaffs()
	{
		return m_NumberOfStaffs;
	}

	//1.4: Print Content of the Department Class
	void Print_Department()
	{
		cout << "Department - " << m_DeptName << "  ID:"
			<< m_DeptID << ", Total Staffs - " 
			<< m_NumberOfStaffs << endl;
	}
};

//ListSort 02: Function to Push some values to List
void Add_ListElements(list<Department>& listParam)
{
	//2.1: Clear the List
	listParam.clear();

	//2.2: Create Department Objects
	const Department D1(3, "Civil           ", 20);
	const Department D2(1, "Mechanical      ", 60);
	const Department D3(5, "Electrical      ", 22);
	const Department D4(4, "Chemical        ", 34);
	const Department D5(2, "Computer Science", 35);

	//2.3: Add Department Objects to List
	listParam.push_back(D1);
	listParam.push_back(D2);
	listParam.push_back(D3);
	listParam.push_back(D4);
	listParam.push_back(D5);
}

//ListSort 03: Function to Print the Values in List
void Print_List(list<Department> listParam)
{
	list<Department>::iterator listItr;
	printf("\nThe contents of the Lists are:\n");
	for (listItr = listParam.begin();
		listItr != listParam.end();
		listItr++)
	{
		(*listItr).Print_Department();
	}
}

//ListSort 04a: Predicate function to sory by 
// Department IDs in Ascending order
bool Compare_IDS_Predicate_Asc(
	Department First, Department Next)
{
	//First Argument Stays First (Return true)
	if (First.GetDeptId() < Next.GetDeptId()) 
		return true; 

	//First Argument goes Next (Swap) (Return false)
	if (First.GetDeptId() > Next.GetDeptId()) 
		return false;

	//a==b. First Argument Stays first 
	//(No need to Swap)
	return true;
}

//ListSort 04b: Predicate function to sort by
// NumberOf Employees - descending
bool Compare_TotEmps_Predicate_Desc(
	Department First, Department Next)
{
	//First Argument Stays First (Return true)
	if (First.GetNumberOfStaffs() > 
		Next.GetNumberOfStaffs()) 
		return true;

	//First Argument goes Next 
	//(Swap) (Return false)
	if (First.GetNumberOfStaffs() < 
		Next.GetNumberOfStaffs()) 
		return false;

	//a==b. First Argument Stays 
	//first (No need to Swap)
	return true;
}

//ListSort 05: Let go Sort the Department List
void main()
{
	//3.1 Create list and iterator
	list<Department> theList;
	Add_ListElements(theList);
	Print_List(theList); 

	//3.2 Sort the List by IDs
	printf("\nSorting List By ID:\n");
	theList.sort(Compare_IDS_Predicate_Asc);
	Print_List(theList);

	//3.3 Sort the List by Department
	printf("\nSorting List By Number of Staffs\n");
	theList.sort(Compare_TotEmps_Predicate_Desc);
	Print_List(theList);

	_getch();
}

The output of the program result is shown below:

List Sort Compare Predicate Example Output
List Sort Compare Predicate Example Output

Comments

    0 of 8192 characters used
    Post Comment

    No comments yet.

    working

    This website uses cookies

    As a user in the EEA, your approval is needed on a few things. To provide a better website experience, turbofuture.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

    For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: https://turbofuture.com/privacy-policy#gdpr

    Show Details
    Necessary
    HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
    LoginThis is necessary to sign in to the HubPages Service.
    Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
    AkismetThis is used to detect comment spam. (Privacy Policy)
    HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
    HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
    Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
    CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
    Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
    Features
    Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
    Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
    Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
    Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
    Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
    VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
    PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
    Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
    MavenThis supports the Maven widget and search functionality. (Privacy Policy)
    Marketing
    Google AdSenseThis is an ad network. (Privacy Policy)
    Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
    Index ExchangeThis is an ad network. (Privacy Policy)
    SovrnThis is an ad network. (Privacy Policy)
    Facebook AdsThis is an ad network. (Privacy Policy)
    Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
    AppNexusThis is an ad network. (Privacy Policy)
    OpenxThis is an ad network. (Privacy Policy)
    Rubicon ProjectThis is an ad network. (Privacy Policy)
    TripleLiftThis is an ad network. (Privacy Policy)
    Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
    Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
    Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
    Statistics
    Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
    ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
    Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)