CSortedArray / CSortedArrayEx v1.55

CSortedArray is a class derived from the MFC template class "CArray" or ATL template class "CAtlArray". It provides for ordered insertion of items into an array as well as searching and sorting of its items. The compare function used to determine ordering in the array can be easily customised at run-time.

CSortedArrayEx is a specialized version of CSortedArray which uses functors rather than a standard comparison function. Using this version provides up to a 300% speed improvement because functors allow function inlining in optimizing compilers while a raw function pointer can never be inlined.

Features

Usage

History

API Reference

Contacting the Author

Features

In MFC mode, CSortedArray(Ex) is publicly derived from CArray meaning than all the functionality of CArray is available in addition to its own functionality.
Instances which currently use CArray can be very easily changed to use CSortedArray(Ex) by simply replacing the text "CArray", "CSimpleArray" or "CAtlArray" with "CSortedArray(Ex)" and modifying their template parameters as necessary.
How items are sorted in CSortedArray can be easily changed at runtime via its SetCompareFunction method or via a functor in CSortedArrayEx.

Usage

To use CSortedArray in your code simply include "SortedArray.h" in your project and #include it in which ever modules you want to instantiate it in.
You can include the class in ATL or MFC projects.
If you want to force the classes to exclude the MFC functionality, you can define the preprocessor value "SORTEDARRAY_ATL_ONLY".
As of v1.50, the classes are now designed for VC 2017 or later. They will not compile on earlier releases of VC.
Please note that like any standard C++ collection class, your class which is being stored in the array should include copy constructor and operator= methods. This general rule applies to anytime when anything more complicated than plain old data types are being stored.

Copyright

You are allowed to include the source code in any product (commercial, shareware, freeware or otherwise) when your product is released in binary form.
You are allowed to modify the source code in any way you want except you cannot modify the copyright details at the top of each module.
If you want to distribute source code with your application, then you are only allowed to distribute versions released by the author. This is to maintain a single distribution point for the source code.

History

v1.55 (2 April 2022)

Updated copyright details.
Updated the code to use C++ uniform initialization for all variable declarations.

v1.54 (10 May 2020)

Fixed more Clang-Tidy static code analysis warnings in the code.

v1.53 (23 March 2020)

Updated copyright details.
Fixed more Clang-Tidy static code analysis warnings in the code.

v1.52 (23 December 2019)

Fixed various Clang-Tidy static code analysis warnings in the code.

v1.51 (22 September 2019)

Replaced enum with enum class throughout the code
Updated copyright details.

v1.50 (26 December 2018)

Updated copyright details.
Fixed a number of C++ core guidelines compiler warnings. These changes mean that the code will now only compile on VC 2017 or later.
Replaced BOOL with bool throughout the codebase

v1.49 (19 November 2017)

Updated the code to compile cleanly when _ATL_NO_AUTOMATIC_NAMESPACE is defined
Replaced NULL with nullptr throughout the codebase. This means that the code now requires VC 2010 at a minimum to compile.

v1.48 (27 April 2017)

Updated copyright details.
Updated the code to compile cleanly using /permissive-.

v1.47 (31 January 2016)

Updated copyright details.
Updated the code and sample app to clean compile on VC 2015
Added SAL annotations to all the code.

v1.46 (24 January 2015)

Updated copyright details.
Updated the code and sample app to clean compile on VC 2013

v1.45 (20 April 2012)

Addition of a FindOrderedInsertIndex method. This new method returns the index which an item would be inserted at if OrderedInsert was called with the same element without actually inserting the item. Thanks to Michael Stephenson for providing this nice addition.

v1.44 (16 March 2012)

Updated copyright details.
Addition of a InsertionBehaviour parameter to the OrderedInsert method. This new enum allows you to specify what should happen if a duplicate item is found at the tentative insertion point. This new enum can have the values: AllowDuplicate (which is the normal behavior), OverwriteIfDuplicate, LeaveIfDuplicate & FailIfDuplicate. Thanks to Michael Stephenson for providing this nice addition.

v1.43 (6 November 2010)

Sort method now internally uses std::sort for sorting. This leads to dramatic improvements as the size of the array increases. It also means that issues with stack sizes due to recursion are now gone. Here is some before and after figures in ms for sorting an array of integers as obtained from the sample app (Note please do not compare the absolute values from one row to another as I shrunk down the number of array loops to keep the measured times reasonable as the array element size increased):

Elements	Before (Function pointer array)	Before (Functor)	After (Function Pointer array)	After (Functor)
100	34	7	x2.125	6 (x1.16)
1000	517	176	295 (x1.75)	84 (x2.09)
10000	7896	2398	3525 (x2.23)	1098 (x2.18)
100000	2696	529	336 (x8.03)	97 (x5.45)
1000000	21017	3284	378 (x55)	125 (x26)
10000000	208768	30605	899 (x232)	458 (x66)

I believe the reason we see a dramatic improvement in performance as the array size increases is the fact that br>std::sort uses an introsort algorithm (which is a quicksort which switches to a heapsort when the recursion reaches a certain depth). The more expert C++ developers out there may ask why not just use the standard STL collection classes instead of the old style MFC CArray classes. In my case, many of my classes are pure MFC classes and at the time of their initial development the MFC classes were the number one choice. Now if you are writing new code it really does make sense to use the STL classes but it is still nice to have the familiarity of the MFC collection classes with the performance of their STL brethren.

StableSort method now internally uses std::stable_sort. Again this has lead to pretty substantial performance improvements as the size of the array increases (Again note please do not compare the absolute values from one row to another as I shrunk down the number of array loops to keep the measured times reasonable as the array element size increased):

Elements	Before (Function pointer array)	Before (Functor)	After (Function Pointer array)	After (Functor)
100	249	80	246 (x1.01)	109 (x0.773)
1000	1005	274	275 (x3.65)	120 (x2.28)
10000	913	229	45 (x20.29)	13 (x17.61)
50000	22587	5655	172 (x131)	74 (x76)
100000	90484	22683	379 (x238)	154 (x147)
300000	81606	20420	111 (x735)	48 (x425)

v1.42 (11 July 2010)

Updated copyright details
Updated sample app to compile cleanly on VC 2010
Optimized code in the Sort method which remembers the "key" element while the quicksort is being performed. Thanks to Michael Stephenson for reporting this optimization.

v1.41 (7 September 2009)

OrderedInsert and Find methods are now Non-const methods. This allows the code to call the non const versions of CArray::GetData which helps avoids compiler errors in some client scenarios.

v1.40 (11 August 2009)

Following testing of the Sort method to ensure correctness, this method has been completely reimplemented. When using the functor version of this method, it is now nearly 20% faster compared to the previous version as well as addressing some sorting errors for specific arrays.
Fixed a bug in UniqueSort where it incorrectly used the pointer returned by GetData when calling the comparison function. If you called UniqueSort with a nHighIndex < GetUpperBound() for the array then the value returned by GetData could become corrupt if the array was realloc'ed.
Addition of an IsSorted simple helper method
Updated the code in the test app to better exercise the functionality of the class
Please note that since the implementation of the Sort method is implemented recursively, you can run out of Win32 stack space if you use the code to sort extra large sized arrays. Some informal testing indicates that with a standard Win32 1 MB stack, you will hit a stack overflow with an array containing random values from 0 to 1000 at roughly 2.9 million elements. Bear in mind that the amount of stack space used will depend on the actual values and their positions in your arrays. You will need to be aware of this issue if you will be using the code for array sizes upwards of a few
hundred thousand. I may consider reimplementing the code to avoid using the Win32 stack to implement the recursion if anyone things this would be a useful addition.
Addition of a StableSort method. Unlike the "Sort" method which internally uses the quicksort algorithm which is not stable, StableSort internally uses an insertion sort algorithm which is. Thanks to "yv" for prompting this update.

v1.39 (26 July 2009)

The code now natively uses INT_PTR for the index values
Updated the sample app's project settings to more modern default values.
If the code is compiled in ATL mode only, CSortedArrayBase (and ultimately CSortedArray/Ex) are now derived from the ATL class CAtlArray instead of the author's CSimpleArrayEx class. The CSimpleArrayEx class is now not included in the download and should be considered defunct. Thanks to Anatoly Ivasyuk for prompting this update.
Reordered the template parameters for CSortedArrayEx to use a default parameter for ARG_TYPE = const TYPE&. You will need to change the ordering of the template parameters in any client code which uses CSortedArrayEx.

v1.38 (29 June 2008)

Updated copyright details
Code now compiles cleanly using Code Analysis (/analyze)
Updated the sample app to clean compile on VC 2008
The code now only supports VC 2005 or later.

v1.37 (29 July 2006)

Provided a new UniqueSort method which in addition to performing the standard sorting of the array also removes any duplicates found. Thanks to John Cullen for suggesting this new feature.

v1.36 (7 July 2006)

Updated copyright details.
Minor update to the sample app to allow it to clean compile on VC 2005.
Updated the documentation to use the same style as the web site.

v1.35 (12 October 2005)

Updated the Find function to allow <0, 0 and >0 values to be allowed for the return value from the comparison function / functor. This allows CString::Compare to be easily used for comparison. Thanks to Serhiy Pavlov for reporting this.
Removed unused constructor from CSimpleArrayEx class.
Updated copyright details.

v1.34 (22 December 2004)

ASSERT / ATLASSERT and INT_PTR / int typedefs are now all done in one place. Thanks to Serhiy Pavlov for suggesting this.
All functions are now declared in the class declaration
Reworked the classes to break the actual comparison code into a new traits class. You now have the choice of using a traits class which specifies the comparison function via a function (CSortedArrayCompareFunction) or via a functor (CSortedArrayCompareFunctor). Backward compatibility is kept by defined a class called CSortedArray which uses a traits class which uses a function. If you want to use the new faster functor version of the class then simply replace all instances of CSortedArray with CSortedArrayEx. Thanks to Serhiy Pavlov for this really nice addition.
Made CSortedArray::Find method non const again to allow use of GetData function.
Updated the sample app to perform some speed tests on ATL Vs MFC and function pointer Vs Functor implementations.

v1.33 (16 October 2004)

Class now compiles cleanly on VC 7 if "Detect 64 bit portability issues" is enabled as well as "Force conformance in for loops" is enabled.

v1.32 (13 November 2003)

Now includes a new class "CSimpleArrayEx" which provides InsertAt support for ATL's CSimpleArray class. This is now used by CSortedArray, rather than directly using CSimpleArray

v1.31 (18 August 2003)

Made the class optionally independent of MFC. If the class detects than MFC is not being included, then the code will use CSimpleArray instead of CArray. This is a class provided in ATL as a substitute for CArray. Please note that the method "OrderedInsert" is not available when using CSimpleArray as the parent class, as CSimpleArray does not implement an "InsertAt" method.

v1.30 (24 January 2003)

Made CSortedArray::Find method const. Thanks to Serhiy Pavlov for reporting this.

v1.29 (11 December 2002)

Optimized code by replacing all calls to CArray<>::ElementAt with CArray<>::GetData

v1.28 (6 December 2002)

Rewrote the Sort method following reports of further problems by Serhiy Pavlov and Brian Rhodes.

v1.27 (29 May 2002)

Fixed a problem in CSortedArray::OrderedInsert. Thanks to John Young for spotting and fixing this problem.
Updated copyright and usage instructions

v1.26 (16 February 2002)

Updated copyright message
Updates to CTreeFileCtrl companion class.

v1.25 (24 December 2001)

Updates to CTreeFileCtrl companion class.

v1.24 (26 October 2001)

Updates to CTreeFileCtrl companion class.

v1.23 (1 October 2001)

Fixed another bug in CSortedArray::Sort!. Thanks to Jim Johnson for spotting this.

v1.22 (11 August 2001)

Updates to CTreeFileCtrl companion class.

v1.21 (11 August 2001)

Updates to CTreeFileCtrl companion class.

v1.2 (5 August 2001)

Updates to CTreeFileCtrl companion class.

v1.15 (5 May 2001)

Updated copyright message.

v1.14 (2 October 2000)

Updates to CTreeFileCtrl companion class.

v1.13 (20 September 2000)

Updates to CTreeFileCtrl companion class.

v1.12 (5 September 2000)

Updates to CTreeFileCtrl companion class.

v1.11 (27 August 2000)

Fixed another stack overflow problem in CSortedArray::Sort.
Fixed a problem in CSortedArray::Sort where the comparison function was returning negative values, 0 and positive values instead of -1, 0 & 1. Thanks to Ted Crow for finding both of these problems.
Updated the documentation for SetCompareFunction on what values are expected to be returned from it.

v1.10 (24 July 2000)

Updates to CTreeFileCtrl companion class.

v1.09 (18 July 2000)

Updates to CTreeFileCtrl companion class.

v1.08 (13 May 2000)

Updates to CTreeFileCtrl companion class.

v1.07 (2 April 2000)

Updates to CTreeFileCtrl companion class.

v1.06 (29 February 2000)

Fixed a problem in CSortedArray::Sort when there are no items in the array

v1.05 (22 February 2000)

Fixed a problem in CSortedArray::Find when there are no items in the array

v1.04 (21 February 2000)

Fixed a number of problems in CSortedArray::Find

v1.03 (31 January 2000)

Updates to CTreeFileCtrl companion class.

v1.02 (25 January 2000)

Updates to CTreeFileCtrl companion class.

v1.01 (12 January 2000)

Fixed a stack overflow in CSortedArray::Sort.

API Reference

The following functions are provided by CSortedArray and the functor version CSortedArrayEx:

CSortedArray::OrderedInsert
CSortedArray::FindOrderedInsertIndex
CSortedArray::Sort
CSortedArray::StableSort
CSortedArray::UniqueSort
CSortedArray::Find
CSortedArray::SetCompareFunction
CSortedArray::GetCompareFunction
CSortedArrayEx::SetCompareFunction
CSortedArrayEx::GetCompareFunction

CSortedArray::OrderedInsert

INT_PTR OrderedInsert(ARG_TYPE newElement, INT_PTR nCount = 1, CSortedArrayEnums::InsertionBehaviour behavior = CSortedArrayEnums::AllowDuplicate);

Return Value

The index where the item has been inserted.

Parameters

element The item to add to the array. Its type is determined when the class is instantiated as with the parent class CArray.

nCount The number of times this element should be inserted (defaults to 1).

behaviour The behavior to use if a duplicate element already exists in the array. Can be "AllowDuplicate", "OverwriteIfDuplicate", "LeaveIfDuplicate" or "FailIfDuplicate".

Remarks

Inserts the element into the array. The code internally uses a binary search to determine where the item should be inserted. This assumes that the elements in the array are already ordered. If they are not then you should call the Sort method first. Because the class is publicly derived from CArray / CAtlArray, you can call all of parents methods in addition to the methods implemented in CSortedArray.

CSortedArray::FindOrderedInsertIndex

INT_PTR FindOrderedInsertIndex(ARG_TYPE element, CSortedArrayEnums::InsertionBehaviour behavior = CSortedArrayEnums::AllowDuplicate);

Return Value

The index where the item has been inserted.

Parameters

element The item to add to the array. Its type is determined when the class is instantiated as with the parent class CArray.

behaviour The behavior to use if a duplicate element already exists in the array. Can be "AllowDuplicate", "OverwriteIfDuplicate", "LeaveIfDuplicate" or "FailIfDuplicate".

Remarks

CSortedArray::Sort

void Sort(INT_PTR nLowIndex = 0, INT_PTR nHighIndex = -1);

Parameters

nLowIndexThe index of the first element in the array to sort.

nHighIndex The index of the last element in the array to sort. The default value of -1 represents the last element in the array.

Remarks

Performs a sort of the specified elements in the array. Internally the code will use the "Quicksort" algorithm to do the sort.

CSortedArray::StableSort

void StableSort(INT_PTR nLowIndex = 0, INT_PTR nHighIndex = -1);

Parameters

nLowIndexThe index of the first element in the array to sort.

nHighIndex The index of the last element in the array to sort. The default value of -1 represents the last element in the array.

Remarks

Performs a sort of the specified elements in the array. Internally the code will use the "Insertion Sort" algorithm to do the sort. This method performs a "stable" sort of the table unlike "Sort" which is an unstable algorithm.

CSortedArray::UniqueSort

void UniqueSort(INT_PTR nLowIndex = 0, INT_PTR nHighIndex = -1);

Parameters

nLowIndexThe index of the first element in the array to sort.

nHighIndex The index of the last element in the array to sort. The default value of -1 represents the last element in the array.

Remarks

Performs a sort of the specified elements in the array and removes any duplicates found. Internally this method calls the standard "Sort" method and then removes any duplicates found.

CSortedArray::Find

INT_PTR Find(ARG_TYPE element, INT_PTR nLowIndex = 0, INT_PTR nHighLowIndex = -1);

Return Value

The index of the item if found otherwise -1 if not.

Parameters

element The item to search for in the array.

nLowIndex The index of the first element in the array to search.

nHighIndex The index of the last element in the array to search. The default value of -1 represents the last element in the array.

Remarks

Searches for an item in the array. The code internally uses a binary search to determine if the element is present or not.

CSortedArray::SetCompareFunction

void SetCompareFunction(LPCOMPARE_FUNCTION lpfnCompareFunction);

Parameters

lpfnCompareFunction The new function to use for comparisons to determine the ordering of elements in the array.

Remarks

This sets the function which is used internally for item comparisons. LPCOMPARE_FUNCTION is a pointer to a function as defined:

typedef int COMPARE_FUNCTION(ARG_TYPE element1, ARG_TYPE element2);
typedef COMPARE_FUNCTION* LPCOMPARE_FUNCTION;

The comparison function should operate the same way as the qsort "C" runtime function, i.e. it should return a negative value when element1 is logically less than element2, 0 for equality and a positive value when element1 is logically greater than element2. Note that prior to v1.35 of the code, the code incorrectly handled return values from the Compare function and in fact only handled -1, 0 and 1!.

CSortedArray::GetCompareFunction

LPCOMPAREFUNCTION GetCompareFunction() const;

Return Value

A pointer to the function which is currently used to determine the ordering of elements in the array.

Remarks

This is the corollary function to the SetCompareFunction function.

CSortedArrayEx::SetCompareFunction

void SetCompareFunction(const COMPARE_TYPE& pCompareFunctor);

Parameters

pCompareFunctor The new comparison functor to use for comparisons to determine the ordering of elements in the array.

Remarks

This sets the functor which is used internally for item comparisons.

The comparison functor should operate the same way as the qsort "C" runtime function, i.e. it should return a negative value when element1 is logically less than element2, 0 for equality and a positive value when element1 is logically greater than element2. Note that prior to v1.35 of the code, the code incorrectly handled return values from the Compare function and in fact only handled -1, 0 and 1!.

CSortedArrayEx::GetCompareFunction

COMPARE_TYPE GetCompareFunction() const;

Return Value

the functor which is currently used to determine the ordering of elements in the array.

Remarks

This is the corollary function to the SetCompareFunction function.

Contacting the Author

PJ Naughter
Email: pjna@naughter.com
Web: http://www.naughter.com
2 April 2022