General Purpose Collection Sorter

• Download source files - 3 Kb
• Download demo project - 11 Kb

Introduction

Recently, I have been working on an application that maintains a series of linked lists as part of its general operations. A while back, I needed to sort the lists at certain points within the program, so I derived a new class from CList (I was using MFC) and added a sort method:

void Sort( );

At a later point, I required to search the list based upon a second search criteria, so I added another parameter to this function. However, it turns out that I in fact needed a third criteria as well, so I decided that instead of adding more and more constants to pass to the function I would create a general-purpose solution. The main motivation for this had been that I’d had to derive another class to sort a different kind of data.

First, I defined a set of requirements that I believed were necessary in such a general-purpose solution

• Support any kind of data that could be stored in a collection
• Support any kind of ordered collection
• Be as self-contained as possible

The second point pretty much ruled out inheritance as an option, which I wanted to avoid in any case because I didn’t want to have to mess about altering already-defined class hierarchies. Instead, I decided to use templates.

The solution

The solution that I have produced is completely general – it would work with any kind of collection, and any kind of data that could be stored in this collection. To this end, I have used several classes that work together to provide the sorting capability. All the functions are defined inline (i.e. in the header file) to increase speed.

The classes that make up the sorting system can be classified as shown below:

• The sorting class itself
• Collection accessor classes
• Item comparer classes.

The main class that you will be using will be CCollectionSorter. This class provides the Quick Sort algorithm itself, and uses the other two categories of classes to assist.

Using CCollectionSorter

Here is how you can use CCollectionSorter in your application to sort a collection:

1. Firstly, you need to declare a collection class. You may have already done this; here is the example we’ll be following through with.

   CList<int, int> MyIntegerList;

   Note that you could also simply further declarations of integer lists as follows:

   typedef CList<int, int> CIntList;

2. Now, in the file where the sorting code will be, you’ll need to include the CollectionSorter.h file:

   #include "CollectionSorter.h"

3. Next, you’ll need to declare a CCollectionSorter variable at the point where you wish to perform the sorting operation. This is a template with two arguments; TYPE and ARG_TYPE. These should be as specified in the declaration of the collection, and in the case of STL containers, they should both be the same:

   CCollectionSorter<int, int&gt IntSorter;

   Note that once again you can simplify further declarations of this as follows:

   typedef CCollectionSorter<int, int> CIntCollectionSorter;

   Further, I would recommend placing this new typedef along with the one above.

4. The next stage is to call one of the SortCollection methods. Which one you call will depend upon your situation. The two basic choices are SortCollection and SortPointerCollection. The difference between these is that SortPointerCollection will dereference the values stored in the collection before comparing them. This will produce unpredictable results if used incorrectly so please ensure you call the correct function. There are overloads of both functions for both CList and CArray collections. However, the CCollectionSorter class is much more flexible if you need it to be, so if these overloads don’t satisfy your requirements, please read on to the section entitled “Extending CCollectionSorter”. For the sake of our example, we will use the following function call:

   IntSorter.SortCollection(MyIntegerList);

   If the collection contains objects, it is required that operator >, operator < and operator == are defined in the classes contained. However, this can be avoided as described in the section “Extending CCollectionSorter”.

Extending CCollectionSorter

The example described above shows the use of this class at its simplest. However, it is possible to provide custom comparer classes, and custom collection accessor classes so that any type of ordered collection and data can be sorted.

Providing a custom comparer class

The purpose of the comparer class is to compare two values and return the result to the sorting routine. This function has been encapsulated into a class so that custom behaviour can be added as needed. For instance, you may wish to provide several comparer classes which all act on different fields of the same class. Then, the comparer class to be used is selected at runtime.

The comparer classes should be derived from the IComparer interface. You must override the following functions:

• virtual bool IsABigger() const
• virtual bool IsBBigger() const
• virtual bool Equal() const

The base class has two protected member variables of the type that was specified by the user of the CCollectionSorter class named m_cmpA and m_cmpB. These will be set by the sorting function, and then the three functions above will be used to compare the two values.

You should derive a comparer class from IComparer, and if the class is for a specific type only, declare it as shown below:

class CMyComparer : public IComparer<type>

You should replace 'type' with the type of data that you are writing the class to compare. If it is to be a general-purpose comparer (like the two supplied), then use the following syntax:

template<class TYPE>
class CMyComparer: public IComparer<TYPE>

You should then pass the new comparer to the SortCollection function as shown below:

Sorter.SortCollection(myCollection, CNewComparer());

You may require that additional initialisation be done before the comparer class is used, in which case you must declare it as a variable, initialise it, then use it, as shown below:

CNewComparer Comp;
// *** initialise Comp here ***
Sorter.SortCollection(myCollection, Comp);

Example – a general compare class

Here is the code for a class which sorts a series of values into descending (rather than ascending) order, derived from the CDefaultComparer class:

#pragma once

#include "DefaultComparer.h"

template<class TYPE>
class CReverseComparer : public CDefaultComparer<TYPE>
{
public:
	CReverseComparer() {}
	virtual ~CReverseComparer() {}

	bool IsABigger() const
	{
		return CDefaultComparer<TYPE>::IsBBigger();
	}
	bool IsBBigger() const
	{
		return CDefaultComparer<TYPE>::IsABigger();
	}
	bool Equal() const
	{
		return (m_cmpA == m_cmpB);
	}
};

Note that, for instance, in the IsABigger function, we cannot use the following:

return !CDefaultComparer<TYPE>::IsABigger();

This is because we must remember that we want m_cmpA < m_cmpB, and that, as shown by the equation below, the above line of code would result in the incorrect answer:

!(m_cmpA > m_cmpB) == (m_cmpA <= m_cmpB)

Now, to use the new comparer class, you'd do the following:

CCollectionSorter<int, int> MyIntListSorter;
MyIntListSorter.SortCollectino(myList, CReverseComparer<int>());

Example: a comparer class specific for one type

Another time when you might need to code your own comparer class is if you wanted to compare different members of the same object type in different parts of your program. Let’s assume you were creating a contact-management program: you might want to sort by either name, or by age. Here’s your CPerson class:

class CPerson
{
public:
	// constructors here…

	UINT GetAge() { return m_nAge; }
	CString GetName() { return m_strName; }

	// etc…

private:
	UINT m_nAge;
	CString m_strName;
};

You’d declare the list as follows:

typedef CList<CPerson *, CPerson *> CPersonList;
typedef CCollectionSorter<CPerson *, CPerson *> CPersonCollectionSorter;

CPersonList g_Contacts;

Obviously this might not be a global variable in an actual application, but I’ve declared it as such here for simplicity. Now, to implement the two comparer classes:

class CPersonAgeComparer : public IComparer<CPerson *>
{
public:
	CPersonAgeComparer() {}
	virtual ~CPersonAgeComparer() {}

	bool IsABigger() const
	{
		return (m_cmpA->GetAge() > m_cmpB->GetAge());
	}
	bool IsBBigger() const
	{
		return (m_cmpB->GetAge() > m_cmpA->GetAge());
	}
	bool Equal() const
	{
		return (m_cmpA->GetAge() == m_cmpB->GetAge());
	}
};

/////////////////////////////

class CPersonNameComparer : public IComparer<CPerson *>
{
public:
	CPersonNameComparer() {}
	virtual ~CPersonNameComparer() {}

	bool IsABigger() const
	{
		return (m_cmpA->GetName() > m_cmpB->GetName());
	}
	bool IsBBigger() const
	{
		return (m_cmpB->GetName() > m_cmpA->GetName());
	}
	bool Equal() const
	{
		return (m_cmpA->GetName() == m_cmpB->GetName());
	}
};

Now, you can use the two classes as follows:

CPersonCollectionSorter sorter

// By age:
sorter.SortCollection(g_Contacts, CPersonAgeComparer());

// Or by Name:
sorter.SortCollection(g_Contacts, CPersonNameComparer());

That’s it for the Comparer classes!

Providing a custom accessor class

Up to now, we’ve primarily used MFC collection classes. However, it is perfectly feasible to provide your own collection accessor class to access any kind of collection. The process is quite simple, and simply involves deriving a new class from the ICollectionAccessor interface and defining the three functions described below:

• virtual TYPE GetAt(long nIndex) – this function is used to retrieve the element at a given zero-based index in the collection.
• virtual long GetCount() – this function is used to determine the number of elements in the collection.
• virtual void Swap(int nFirst, int nSecond) – this function is used to swap the elements at the given zero-based indices nFirst and nSecond.

The interface does not provide a mechanism for storing the collection, as this would mean the sorter class would also have to know what kind of collection was being held. Therefore, it is up to you to provide such a method in your derived class. This also means that you can sort diverse collection types that cannot be stored in the normal way. For instance, in the example I’m about to demonstrate showing how to provide a custom accessor class, you’ll see that we need to store two pieces of data in order to provide access to the collection, not one. Should the base class have automatically handled storing a reference to collection, this wouldn’t have been as clean to implement. Further, the sorter class, which takes a reference to an ICollectionAccessor derived class, does not need to know anything about the collection that is being stored.

It is usual to provide a method named SetCollection to handle passing a pointer or reference to the collection class. If you decide to do this using a reference, you will either have to store a pointer (taking the address of the reference), or pass a reference to the constructor instead. In order to clarify this discussion, I have provided an example below:

Example – providing a collection accessor for a standard C array

Now, let’s assume that we have an array of ten integers that need sorting:

int nNumnbers[9]; // don’t forget nNumbers[0] is also valid

Neither of the pre-defined collection accessor classes will provide for accessing this kind of collection. Therefore, we need to provide our own. Here are a summary of its responsibilities and requirements:

1. It needs to store a pointer or reference to the array
2. It needs to be able to access any element of the array
3. It needs to be able to determine the number of items in the array
4. It needs to be able to swap two items of the array

As described above, we need to provide overrides for the three functions declared in the interface also.

The CList and CArray accessor classes store a pointer to the collection. However, doing this would only provide half of the functionality required, because those classes have a built in function for determining the size of the collection. Because we are using a raw array, we must also take this information as a parameter.

Note that, no matter what kind of elements we store in the array, the way it is accessed will be the same in 99% of cases. Therefore, we might as well write this as a template class so that we can use it for any kind of array in the future also.

Okay, here’s the class that I’ve defined:

template<class TYPE>
class CStdArrayAccessor : public ICollectionAccessor<TYPE>
{
public:

	CStdArrayAccessor() { m_pArray = NULL; m_nSize = 0; }
	CStdArrayAccessor(TYPE *pArray, long nSize)
	{
		SetCollection(pArray, nSize);
		ASSERT(m_pArray);
	}

	void SetCollection(TYPE *pArray, long nSize)
	{
		m_pArray = pArray;
		m_nSize = nSize;
		ASSERT(m_pArray);
	}

	TYPE GetAt(long nIndex)
	{
		ASSERT(m_pArray);
		return m_pArray[nIndex];
	}

	void Swap(long nFirst, long nSecond)
	{
		ASSERT(m_pArray);
		TYPE typeFirst = m_pArray[nFirst];

		// set the item at the first position to equal the second:
		m_pArray[nFirst] = m_pArray[nSecond];
		
		// now the second to equal the first:
		m_pArray[nSecond] = typeFirst;
	}

	long GetCount()
	{
		ASSERT(m_pArray);
		return m_nSize;
	}

protected:
	TYPE *m_pArray;
	long m_nSize;
};

Now, to use this accessor class, we must first initialise it:

CStdArrayAccessor<int> saa;
saa.SetCollection(nNumbers, 10); 

Notice that we provide 10 as the size because even though the upper bound of the array is 9, there are ten items because the index is always zero-based.

Now, we can sort the array:

CCollectionSorter&ltint, int> sorter;
sorter.SortCollection(saa);

Notice that we use the third overloaded version of the SortCollection method, which takes a collection accessor class as its first parameter rather than the collection itself. This eliminates the need for the sorting class to know about the collections it is sorting at all, and in fact you’ll see that the other overloaded version just end up calling this one anyway, but they are provided to add clarity to your code. Obviously, you could provide both a custom accessor and a custom comparer class, which the sorting function would then use instead of the defaults.

The demo project

The demo project is a very simple console application which takes a set of numbers, stores them in both a CArray and CList class, and then uses the methods of CCollectionSorter to sort both collections, then outputs them to the console. The aim of the project is purely to demonstrate the simplest usage of the class – hopefully after reading this article you will be able to easily implement sorting in your own application, providing custom accessor and/or comparer classes as needed.

Conclusion

Okay, that’s it folks! I hope that you will find this collection-sorting mechanism useful; I know it’s been useful to me since I wrote it a few weeks back. If you have any problems with the code, or want to make suggestions, feel free to e-mail me (click on my name at the top of the article).