在处理文件排序问题时，经常需要考虑性能和效率。在本文中，将探讨如何在C++中使用STL列表进行二分插入排序，以优化文件排序的性能。这种方法特别适用于需要在内存中对大量文件进行排序的场景。
在一次项目中，需要对一个STL列表中的文件名进行排序，排序的依据是文件的创建日期，要求按照降序排列。同时，还需要将列表分为两部分：一部分包含BMP文件，另一部分包含其他类型的文件。由于项目要求不能使用队列或双端队列，只能使用STL列表。
最初，尝试使用简单的插入排序算法，但这种方法效率非常低。对于100个BMP文件，排序过程需要大约75秒。考虑到程序运行在SH3处理器上，并且是在Windows CE 2.12系统下读取FlashCard上的文件，这样的性能显然是不可接受的。
为了提高排序效率，决定采用二分插入排序算法。然而，STL列表的迭代器不支持直接移动多个位置，这使得实现二分插入排序变得复杂。尽管如此，还是找到了一种方法来实现这一算法。
首先定义了一个CFileData类，用于存储由findnext函数填充的WIN32_FIND_DATA结构。然后，创建了一个STL列表FileList，用于存储CDiskFile指针。
在排序函数SortIntoList中，首先初始化两个迭代器iBegin和iEnd，分别指向列表的开始和结束。然后，使用一个while循环来找到插入新文件的正确位置。在每次迭代中，计算列表的中间位置，并移动迭代器到该位置。如果新文件的日期早于或等于当前迭代器指向的文件日期，则将iBegin更新为当前迭代器的位置；否则，将iEnd更新为当前迭代器的位置。
通过这种方式，可以在每次迭代中将搜索范围减半，从而大大提高了排序效率。最终，将新文件插入到正确的位置。
采用二分插入排序算法后，排序100个BMP文件的时间从75秒缩短到了2.5秒，这是一个显著的性能提升。在更强大的硬件上，如P3/450处理器，排序时间甚至可以缩短到1秒以下。
typedef std::list 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 = static_cast(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);
}