Wednesday, February 2, 2011

How to use the quick-sort function to sort MFC CArray-derived classes on the MFC and Visual C++ run-time library

Tip- Need to sort a CArray-derived class? Use QuickSort of RT.

Details - Often we need to sort contents of a CArray Derived class. We can do it by using the sort algorithms that are readily available in runtime environment. The Visual C++ run-time library (MSVCRT) implements the quick-sort function

The following example shows you how to use this function to sort an MFC CArray class.
Although the following example uses a CString array, you can easily customize for other MFC CArray-derived classes, such as CByteArray, CDWordArray, CObArray, CPtrArray, CUintArray, and CWordArray.

1.       Derive your array data class from one of the CArray-derived classes. In our example, we use CStringArray as the base class for our class. The following is the declaration in the header file.

class CSortableStringArray : public CStringArray
{
public:
protected:
};

2.       To the public section of your class add the following function.
void Sort(STRINGCOMPAREFN pfnCompare = Compare);

3.  To the protected section of your class add the following static function.
static int __cdecl Compare(const CString * pstr1, const CString * pstr2);

4.  Now add the following two type defs above the declaration of your class. These typedefs later help us in passing pointers of the two functions that we declared in steps 2 and 3 to the Visual C++ run-time's qsort function.
typedef int (__cdecl *GENERICCOMPAREFN)(const void * elem1, const void * elem2);
typedef int (__cdecl *STRINGCOMPAREFN)(const CString * elem1, const CString * elem2);

5.       In your .cpp file, implement the two functions that you declared earlier.
int CSortableStringArray::Compare(const CString * pstr1, const CString * pstr2)
{
  ASSERT(pstr1);
  ASSERT(pstr2);
  return pstr1->Compare(*pstr2);
}

void CSortableStringArray::Sort(STRINGCOMPAREFN pfnCompare /*= CSortedStringArray::Compare */)
{
  CString * prgstr = GetData();
  qsort(prgstr,GetSize(),sizeof(CString),(GENERICCOMPAREFN)pfnCompare);
}

To use the array in your code, just declare it and call the Sort() function. The following example uses this array.
        srand( (unsigned)time( NULL ) ); // Generate seed for rand().
        CSortableStringArray arr;
        CString str;
        for (int i=0; i< 1000;i++)
        {
               str.Format("%6d", rand());// Get a random number string.            
               arr.Add(str);
               TRACE("%s\n", (LPCTSTR)str);
        }
        long ltim=GetTickCount();
        arr.Sort();
        for (i=0; i< 1000;i++)
        {
               TRACE("%s\n", (LPCTSTR)arr[i]);
        }

To implement a CArray type other than CString, just derive your class from the other array types and modify the Sort() and the Compare() functions accordingly.

Sounds similar… tweaked STRATEGY pattern.
You can even extend this by customizing the sort. Need to sort rectangles?  Can be on Length, Breadth, Area or Perimeter. Only thing is you have to move away from run time’s qsort implementation.

Reference   -

Posted By : Ajesh P.S

No comments:

Post a Comment