CSortedArray is a class derived
from the MFC template class "CArray" or ATL template class "CSimpleArray". 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.
CSimpleArrayEx is a template class
derived from ATL's CSimpleArray and provides InsertAt support. It is used as a
base class for CSimpleArray when the MFC class CArray is not available
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.