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.
The enclosed zip file contains source
code for the class and also includes a VC 2017 MFC / ATL project file to demonstrate
the code.
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.
Updates
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 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.