Introduction
There is no spoon. The Oracle will see you now.
The Problem
Recently I had a need to perform an insertion sort on a STL list of filenames
in descending file date order. One of the rules was that I could not change to
a de-queue or queue - I had to stick with the list. This should be an indication
to you that there were no other options available. The other rule (and one
that is completely unrelated to this article but that is included for
completeness) was that I had to sort the list into two sections - one that
contained BMP files, and one that contained all other files (the existence of
sub-folders was not a consideration for this particular task).
If you aren't already aware, the C runtime library's findnext
function will find files in the order they were written to the disk. In a
pristine environment where files are only created by your application, you can
almost be guaranteed that when you perform a findnext
on your disk drive, the
files will be found in ascending date/time order in which they were written.
Notice that I said "almost guaranteed".
If you've spent any time as a programmer, you know there's no such thing as a
guaranteed outcome, or at least you shouldn't assume that the guarantee is
always valid. So I didn't.
In my case, the act of first determining if the file was a BMP, what the file
date/time was, and then finding where to insert it into the list was
time-consuming. My original thought was to just start at the top of the list
and iterate to the end of the list until I found the proper place to insert the
filename. the problem was that for 100 BMP files, this process required about
75 seconds.
I guess I should take this opportunity to mention that the program
is running on an SH3 processor under a bastardized implementation Windows CE
2.12, and is reading files off a FlashCard. This is not what I would call a
speedy system.
The Solution
I decided that it would be faster if I could implement a binary insertion sort
instead of the simple sort that I was already performing. The problem with
implementing a binary sort on a STL list is that you can't move the iterator
by saying something like
iter += 5;
You actually have to move the iterator one position at a time until it's in the
correct position in the list. Believe me when I say this is a royal pain in the
rear.
I can't post more code than this (proprietary stuff), but it should give you a basis for
implementing a binary insertion sort on your own STL list.
typedef std::list < CDiskFile* > FileList;
FileList m_FileList;
void MyListMgr::SortIntoList(CDiskFile* pFile)
{
FileList::iterator iBegin = m_FileList.begin();
FileList::iterator iEnd = m_FileList.end();
FileList::iterator iSorter = iBegin;
int steps = m_FileList.size();
while (iBegin != iEnd)
{
iSorter = iBegin;
steps = (int)(steps / 2);
for (int i = 0; i < steps; i++)
{
++iSorter;
}
if (pFile->dateIsEarlierOrEqual((*iSorter)))
{
iBegin = iSorter;
if (steps == 0 && iBegin != iEnd)
{
++iBegin;
}
}
else
{
iEnd = iSorter;
if (steps == 0 && iEnd != iBegin)
{
--iEnd;
}
}
}
iSorter = iEnd;
m_FileList.insert(iSorter, pFile);
}
In Closing
This isn't rocket science, but it is a useful technique if you're
stuck with having to use a list and you need a fast insertion sort
into that list. Oh yeah, in case you were wondering, the time required to sort the
same list of BMP files using this technique was reduced to 2.5
seconds (on the handheld device described earlier). It took less than
one second on my P3/450 at work.