如何搜索具有特定字段值的記錄的通用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來獲得由集合自動管理的項目的生命週期（只記得如果它在多個集合中，則只有一個集合管理對象的生命週期）。