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 2005 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.01 (12 January
2000)
- Fixed a stack overflow in CSortedArray::Sort.
v1.02 (25 January
2000)
- Updates to CTreeFileCtrl companion class.
v1.03 (31 January
2000)
- Updates to CTreeFileCtrl companion class.
v1.04 (21 February
2000)
- Fixed a number of problems in CSortedArray::Find
v1.05 (22 February
2000)
- Fixed a problem in CSortedArray::Find when there are no items in the array
v1.06 (29 February
2000)
- Fixed a problem in CSortedArray::Sort when there are no items in the array
v1.07 (2 April
2000)
- Updates to CTreeFileCtrl companion class.
v1.08 (13 May
2000)
- Updates to CTreeFileCtrl companion class.
v1.09 (18 July
2000)
- Updates to CTreeFileCtrl companion class.
v1.10 (24 July
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.12 (5 September
2000)
- Updates to CTreeFileCtrl companion class.
v1.13 (20 September
2000)
- Updates to CTreeFileCtrl companion class.
v1.14 (2 October
2000)
- Updates to CTreeFileCtrl companion class.
v1.15 (5 May 2001)
- Updated copyright message.
v1.2 (5 August 2001)
- Updates to CTreeFileCtrl companion class.
v1.21 (11 August 2001)
- Updates to CTreeFileCtrl companion class.
v1.22 (11 August 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.24 (26 October 2001)
- Updates to CTreeFileCtrl companion class.
v1.25 (24 December 2001)
- Updates to CTreeFileCtrl companion class.
v1.26 (16 February 2002)
- Updated copyright message
- Updates to CTreeFileCtrl companion class.
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.28 (6
December 2002)
- Rewrote the Sort method following reports of further
problems by Serhiy Pavlov and Brian Rhodes.
v1.29 (11
December 2002)
- Optimized code by replacing all calls to CArray<>::ElementAt
with CArray<>::GetData
v1.30 (24
January 2003)
- Made CSortedArray::Find method const. Thanks to Serhiy
Pavlov for reporting this.
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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.