delphi - 在排序的 TStringList 中搜索带有前缀 (StartsText) 的条目

Question

我有一个已排序并包含唯一文件名的 TStringList。该列表可以是任意大小(因此可以是数十万个条目)。我想检查是否有任何条目以特定字符串开头(即文件是否位于子文件夹中)。连续扫描列表并使用 StartsText 很容易，但这不是一个理想的解决方案。

使用 TStringList.Find() 代码作为起点，我创建了一个我认为是解决方案的函数，但我想确定一下。不用担心以下内容不是类的成员(FList 是正在搜索的 TStringList 实例)，并且 StartsFilename 的工作方式与 StartsText 相同:

  function ShortcutFind(const S: string): Boolean;
  var
    L, H, I, C: Integer;
  begin
    Result := False;
    L := 0;
    H := FList.Count - 1;
    while L <= H do begin
      I := (L + H) shr 1;

      if TFilenameUtils.StartsFilename(FList[I], aFolder) then begin
        Result:=TRUE;
        Exit;
      end;

      C := FList.CompareStrings(FList[I], S);
      if C < 0 then
        L := I + 1
      else begin
        H := I - 1;
        if C = 0 then begin
          Result := True;
          if FList.Duplicates <> dupAccept then L := I;
        end;
      end;
    end;
  end;

基本上，唯一真正的变化是它在进入下一个条目进行比较之前进行检查。

请注意，从 TStringList 切换不是一个选项。

这个方法行得通吗？

谢谢

Answer 1

如果 TFilenameUtils.StartsFilename 与 StartsText 相同(并且您的第一段表明可能是)，那么您可以通过 使用 TStringList.Find而不是复制它:

var
  I: Integer;
begin
  Assert(not FList.CaseSensitive);
  Result := FList.Find(S, I) or ((I < FList.Count) and StartsText(S, FList[I]));
end;

这应该可行，因为当Find失败时，它仍然会告诉您所需字符串将出现在列表中的索引。当您搜索前缀字符串时，其位置将位于以该前缀开头的任何其他字符串之前，因此，如果存在任何具有该前缀的字符串，它们将立即出现在前缀本身的假设位置之后。

<小时/>

如果您想保留当前代码，则可以通过删除检查 C = 0 的条件来简化它。这种情况永远不会发生，除非您的 StartsFilename 函数被破坏。但是，如果该函数确实被破坏并且C可以为零，那么您至少可以在此时停止执行循环，因为您已经找到了您要查找的内容。无论哪种方式，您都不需要检查 Duplicates，因为您的函数没有与 Find 相同的要求来返回找到的项目的索引。