如何在通用TList中搜索具有特定字段值的记录？

Question

有关泛型TList的所有内容。我有这样的结构：

Type
  TExtract = record
    Wheel: string;
    Extract: array [1..5] of Byte;
  end;

  TExtractList = TList<TExtract>

  TEstr = record
    Date: TDate;
    Extract: TExtractList;
  end;

  TEstrList = TList<TEstr>;

主列表是TExtrList，在这个列表中我有所有的日期，对于日期，所有的轮子都有那个日期。我想搜索一下日期是否存在。如果不存在，我会在从TEstr中提取信息的子列表TExtractList中添加。当我在TExtrList中搜索时，Delphi会问我关于TEstr类型的问题。我只需要搜索Date。那么，如何在通用TList中搜索单个字段呢

附言:我删除了上一篇文章，因为我在这里试着解释得更好。

Answer 1

再来一次。

您应该使用内置的TList<T>.BinarySearch()函数，即使它正确地要求将TEstr记录作为参数。您首先需要使用TList<T>.Sort()按照与搜索相同的标准对列表进行排序，然后调用BinarySearch()查找您的记录。

下面是一个同时执行这两个任务的函数(排序和搜索)：

uses Generics.Defaults; // this provides TDelegatedComparer
uses Math; // this provides Sign()

function SearchList(Date:TDate; Sort:Boolean; List:TList<TEstr>): Integer;
var Comparer: IComparer<TEstr>;
    Dummy: TEstr;
begin
  // Prepare a custom comparer that'll be used to sort the list
  // based on Date alone, and later to BinarySearch the list using
  // date alone.
  Comparer := TDelegatedComparer<TEstr>.Construct(
    function (const L, R: TEstr): Integer
    begin
      Result := Sign(L.Date - R.Date);
    end
  );

  // If the list is not sorted, sort it. We don't know if it's sorted or not,
  // so we rely on the "Sort" parameter
  if Sort then List.Sort(Comparer);

  // Prepare a Dummy TEstr record we'll use for searching
  Dummy.Date := Date;

  // Call BinarySearch() to look up the record based on Date alone
  if not List.BinarySearch(Dummy, Result, Comparer) then
    Result := -1;
end;

BinarySearch假设列表是排序的(这就是二进制搜索的本质！)。在第一次调用时，您需要设置Sort=True，以便对列表进行正确排序。在后续调用中，Sort应为False。当然，在实际使用中，您可能会有不同的例程来进行搜索和排序，并且您可能会将它们作为从TList<TEstr>继承下来的类的方法(以使事情更容易)。出于演示的目的，我将这两个函数放在同一个例程中。

Answer 2

您还可以像这样声明一个助手类，以避免IComparer的要求，即比较的左侧和右侧都必须是专用类型：

type
  TLeftComparison<T> = reference to function(const Left: T; var Value): Integer;

  TListHelper<T> = class
  public
    class function BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
      Comparison: TLeftComparison<T>; Index, Count: Integer): Boolean; overload;
    class function BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
      Comparison: TLeftComparison<T>): Boolean; overload;
    class function Contains(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Boolean;
    class function IndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
    class function LastIndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
  end;

class function TListHelper<T>.BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
  Comparison: TLeftComparison<T>; Index, Count: Integer): Boolean;
var
  L, H: Integer;
  mid, cmp: Integer;
begin
  Result := False;
  L := Index;
  H := Index + Count - 1;
  while L <= H do
  begin
    mid := L + (H - L) shr 1;
    cmp := Comparison(Instance[mid], Value);
    if cmp < 0 then
      L := mid + 1
    else
    begin
      H := mid - 1;
      if cmp = 0 then
        Result := True;
    end;
  end;
  FoundIndex := L;
end;

class function TListHelper<T>.BinarySearch(Instance: TList<T>; var Value; out FoundIndex: Integer;
  Comparison: TLeftComparison<T>): Boolean;
begin
  Result := BinarySearch(Instance, Value, FoundIndex, Comparison, 0, Instance.Count);
end;

class function TListHelper<T>.Contains(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Boolean;
begin
  Result := IndexOf(Instance, Value, Comparison) >= 0;
end;

class function TListHelper<T>.IndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
var
  I: Integer;
begin
  for I := 0 to Instance.Count - 1 do
    if Comparison(Instance[I], Value) = 0 then
      Exit(I);
  Result := -1;
end;

class function TListHelper<T>.LastIndexOf(Instance: TList<T>; var Value; Comparison: TLeftComparison<T>): Integer;
var
  I: Integer;
begin
  for I := Instance.Count - 1 downto 0 do
    if Comparison(Instance[I], Value) = 0 then
      Exit(I);
  Result := -1;
end;

然后你可以像这样使用它：

// TComparison (requires instances on both sides)
function CompareEstr(const Left, Right: TEstr): Integer;
begin
  if Left.Date < Right.Date then
    Exit(-1);
  if Left.Date > Right.Date then
    Exit(1);
  Result := 0;
end;

// TLeftComparison: requires instance only on the left side    
function CompareEstr2(const Left: TEstr; var Value): Integer;
begin
  if Left.Date < TDateTime(Value) then
    Exit(-1);
  if Left.Date > TDateTime(Value) then
    Exit(1);
  Result := 0;
end;

procedure Main;
var
  Date: TDate;
  Comparer: IComparer<TEstr>;
  List: TEstrList;
  Item: TEstr;
  Index: Integer;
  I: Integer;
begin
  Comparer := nil;
  List := nil;
  try
    // create a list with a comparer
    Comparer := TComparer<TEstr>.Construct(CompareEstr);
    List := TEstrList.Create(Comparer);
    // fill with some data
    Date := EncodeDate(2011, 1, 1);
    for I := 0 to 35 do
    begin
      Item.Date := IncMonth(Date, I);
      List.Add(Item);
    end;
    // sort (using our comparer)
    List.Sort;

    Date := EncodeDate(2011, 11, 1);
    Item.Date := Date;

    // classic approach, needs Item on both sides   
    Index := List.IndexOf(Item);
    Writeln(Format('TList.IndexOf(%s): %d', [DateToStr(Date), Index]));
    List.BinarySearch(Item, Index);
    Writeln(Format('TList.BinarySearch(%s): %d', [DateToStr(Date), Index]));
    Writeln;

    // here we can pass Date directly
    Index := TListHelper<TEstr>.IndexOf(List, Date, CompareEstr2);
    Writeln(Format('TListHelper.IndexOf(%s): %d', [DateToStr(Date), Index]));
    TListHelper<TEstr>.BinarySearch(List, Date, Index, CompareEstr2);
    Writeln(Format('TListHelper.BinarySearch(%s): %d', [DateToStr(Date), Index]));
    Readln;
  finally
    List.Free;
  end;
end;

这当然不是类型安全的(由于右侧的非类型化比较参数)，但需要允许比较不同类型的值。只要稍加小心，这应该不是问题。否则，您还可以为需要比较的大多数使用类型编写重载版本。

Answer 3

我发现只有一种方法可以搜索具有特定值的列表。

我将重用Cosmin Prund示例：

uses Generics.Defaults; // this provides TDelegatedComparer
uses Math; // this provides Sign()

function SearchList(Date:TDate; Sort:Boolean; List:TList<TEstr>): Integer;
var Dummy : TEstr;
begin
  // If the list is not sorted, sort it. We don't know if it's sorted or not,
  // so we rely on the "Sort" parameter
  if Sort then List.Sort(TDelegatedComparer<TEstr>.Construct(
    function (const L, R: TEstr): Integer
    begin
      Result := Sign(L.Date - R.Date);
    end
  );

  // Call BinarySearch() to look up the record based on Date alone
  if not List.BinarySearch(Dummy, Result, TDelegatedComparer<TEstr>.Construct(
      function (const L, R: TEstr): Integer
      begin
         //By implementation, the binarySearch Dummy parameter is passed in the "R" parameter of the Comparer function. (In delphi 2010 at least)
        Result := Sign(L.Date - Date); //Use the Date parameter instead of R.Date
      end) then
    Result := -1;
end;

然而，这种方法只在“通过实现”有效，而不是“通过设计”有效(据我所知)。换句话说，它很容易在不同版本Delphi之间中断。因此，只有在创建“性能昂贵”的项目时，才建议使用这种方法。如果您这样做了，我强烈建议在您的代码中添加类似这样的内容。

{$IF RTLVersion > *YourCurrentVersion*}
   {$MESSAGE WARNING 'Verify if BinarySearch implementation changed'}    
{$IFEND}

P这样，下次你在新版本的Delphi中构建这段代码时，你会自动得到一个警告，告诉你确保你的代码仍能像预期的那样工作。但是，如果您的代码需要同时支持多个版本的Delphi，这仍然会带来问题。