二进制排序到 std::list

引言

没有勺子。神谕会现在见你。

问题

最近，我需要对一个 STL 文件名列表按文件日期降序进行插入排序。其中一个规则是我不能更改为 de-queue 或 queue - 我必须坚持使用列表。这应该表明您没有其他选择。另一个规则（与本文无关，但为了完整起见而包含）是我必须将列表分成两个部分 - 一个包含 BMP 文件，另一个包含所有其他文件（对于这项特定任务，子文件夹的存在不予考虑）。

如果您还不知道，C 运行时库的 findnext 函数将按照文件写入磁盘的顺序查找文件。在一个仅由您的应用程序创建文件的原始环境中，您可以几乎保证当您对硬盘驱动器执行 findnext 时，将按照写入它们的日期/时间升序找到文件。请注意，我说的是“几乎保证”。

如果您作为程序员已经花了一些时间，您就会知道没有什么是绝对有保障的结果，或者至少您不应该认为该保障总是有效的。所以我没有。

就我而言，首先确定文件是否为 BMP 文件，确定文件日期/时间，然后找到将其插入列表中的位置非常耗时。我最初的想法是只从列表的顶部开始，并迭代到列表的末尾，直到找到插入文件名的合适位置。问题是，对于 100 个 BMP 文件，这个过程需要大约 75 秒。

我想我应该借此机会提到，该程序正在一个 SH3 处理器上运行，在基于 Windows CE 2.12 的改版实现下运行，并且正在从 FlashCard 读取文件。 这不是我所说的快速系统。

解决方案

我决定如果我能实现二进制插入排序，而不是我已经在执行的简单排序，那会更快。 在 STL 列表上实现二进制排序的问题是您不能通过诸如以下方式来移动迭代器

    iter += 5;

您实际上必须一次一个位置地移动迭代器，直到它位于列表中的正确位置。 相信我，这真是令人头疼。

我不能发布比这更多的代码（专有内容），但它应该为您提供在您自己的 STL 列表上实现二进制插入排序的基础。

// CFileData is a class I wrote to hold the WIN32_FIND_DATA structure 
// that's populated by a call to findnext

typedef std::list < CDiskFile* > FileList;
FileList m_FileList;

void MyListMgr::SortIntoList(CDiskFile* pFile)
{
	// Find a place to start and stop.  In my case, I had to maintain 
	// an iterator that tracked the begining of the section that was 
	// not BMP files (iEnd was NOT guaranteed to be the absolute end 
	// of the list), but for this example, it's not neccesary.
	FileList::iterator iBegin  = m_FileList.begin();
	FileList::iterator iEnd    = m_FileList.end();
	FileList::iterator iSorter = iBegin;
	int                steps   = m_FileList.size();

	// Find a place to put the file. The list is sorted in descending 
	// date order.
	while (iBegin != iEnd)
	{
	  // start with the iterator at the current beginninf of the list
	  iSorter = iBegin;
	  // find the middle
	  steps = (int)(steps / 2);
	  // move the iterator to the middle
	  for (int i = 0; i < steps; i++)
	  {
		 ++iSorter;
	  }
	  // if the date of the file being inserted is earlier or equal 
	  // to the date of the ciurrent iterator position
	  if (pFile->dateIsEarlierOrEqual((*iSorter)))
	  {
		 // change the beginning of the list to the current  
		 // iterator position
		 iBegin = iSorter;
		 // if we didn't move at all, and if we aren't at the  
		 // end of the list,  move the beginning one more step.
		 if (steps == 0 && iBegin != iEnd)
		 {
			++iBegin;
		 }
		 // we need to do it this way because eventually, you just 
		 // run out of "steps" (it's equal to 0), and the routine 
		 // would just sit there on the same iterator forever.  If 
		 // it gets to this point, it's safe to assume that simply 
		 // moving the iterator one more step in the appropriate 
		 // direction will locate the correct insertion point.
	  }
	  else
	  {
		 iEnd = iSorter;
		 if (steps == 0 && iEnd != iBegin)
		 {
			--iEnd;
		 }
	  }
	}
	iSorter = iEnd;
	m_FileList.insert(iSorter, pFile);
}

最后

这并不是火箭科学，但如果你必须使用列表并且你需要快速插入到该列表中，那么它是一个有用的技术。哦，是的，如果您想知道，使用这种技术对同一组 BMP 文件进行排序所需的时间减少到 2.5 秒（在前面描述的手持设备上）。 在我的 P3/450 工作站上，它花费的时间不到一秒钟。