如何搜索具有特定字段值的记录的通用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搜索德尔福问我关于TEstr类型。我只需要搜索Date。那么如何在通用TList中搜索单个字段？

PS：我删除了最后一个帖子，因为在这里我试图解释更好。

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>降序的类的方法（以使easyer变得简单）。我把这两个放在同一个例程中用于解密目的。

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

我认为你必须在TDynArrayHashed这个功能，在这个Post

Answer 4

的例子只有我发现在列表中有一个特定的值来搜索一个单一的方式。

我会重用科斯明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 这样一来，下一次你建立德尔福的较新版本的代码，你将自动获得一个警告信息，告诉你，以确保您的代码仍然可以正常工作。但是如果您的代码需要同时支持超过1个版本的Delphi，这仍然会导致问题。

Answer 5

是不是真的需要成为TList？ Imo，二进制搜索对此太复杂了。也许你可以简单地使用一个TDictionary：

type 
    TEstrCollection = TDictionary<TDate, TEstr>; 

var 
    EstrCollection: TEstrCollection; 
begin 
    EstrCollection := TEstrCollection.Create; 

    // Add an item 
    EstrCollection.Add(Date, TExtractList.Create) 

    // Search 
    ExtractList := EstrCollection[Date]; 
end; 

现在，这需要日期字段是唯一的，因为它是字典的关键。此外，这些项目没有特定的顺序。

如果顺序很重要，我会结合数据结构。例如，你可以让一个TList仅仅为了执行搜索而按顺序加上一个TDictionary，就像这样。

唯一是records不是指针。要添加您需要为他们

PEstr = ^TEstr 

创建的指针或者只是使用对象，因为它们是指针已经同两个截然不同的record数据结构。您可以使用TObjectList和TObjectDictionary来获得由集合自动管理的项目的生命周期（只记得如果它在多个集合中，则只有一个集合管理对象的生命周期）。