How do I search a generic TList<T> collection? [duplicate]

Question

Possible Duplicate:
How can I search a generic TList for a record with a certain field value?

I have a collection of

TList<TActivityCategory>

TActivityCategory has a Name property of type string and I want to search the TList using the Name property.

I see BinarySearch in the TList<> but that would require an instance of TActivityCategory. I just want to pass the string for a name.

How would I go about doing this?

Heresiarch

I saw that one but it is not clear to me. BinarySearch is asking for an instance of the object being searched. I do not see how this can help when I'm looking for the object by passing a string. – Heresiarch

You have to pass a custom comparer, that performs the comparison based only on the string field. – Celsacelsius

That's what I was thinking. But, I'm not sure how to go about it. All sample TComparers that I have seen talk about sorting TList<>. None about searching. Would you happen to have an example? – Heresiarch

Take the Comparer in Cosmin's answer and replace the internals with Result := CompareText(L.Name, R.Name), or use CompareStr for case-sensitive comparison. Cosmin was talking about binary search. If you don't want to sort your container you are into linear search. Use IndexOf in that case. – Celsacelsius

May be some help here : docwiki.embarcadero.com/CodeExamples/en/… – Chronopher

@David: Is it possible to provide a custom comparer for IndexOf? I thought it would always do a byte-wise comparison. Since the OP wants to search only for the name field, he would have to implement the linear search on his own (as trivial as it is) – Adoration

@smasher I believe you can supply the comparer when you create the list, but I can't easily check to be 100% sure – Celsacelsius

Answer 1

When you create the list you can pass in a comparer. There are some comparer classes in the Generics.Defaults unit where you can pass in some anonymous method to compare two elements. They are used for several methods like IndexOf, Contains or Sort.

Example:

uses
  Generics.Defaults,
  Generics.Collections;

type
  TActivityCategory = class
  private
    FName: string;
  public
    constructor Create(const Name: string);
    property Name: string read FName write FName;
  end;

constructor TActivityCategory.Create(const Name: string);
begin
  FName := Name;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  activities: TList<TActivityCategory>;
  search: TActivityCategory;
begin
  activities := TObjectList<TActivityCategory>.Create(
    TDelegatedComparer<TActivityCategory>.Create(
      function(const Left, Right: TActivityCategory): Integer
      begin
        Result := CompareText(Left.Name, Right.Name);
      end));

  activities.Add(TActivityCategory.Create('Category B'));
  activities.Add(TActivityCategory.Create('Category C'));
  activities.Add(TActivityCategory.Create('Category A'));

  search := TActivityCategory.Create('Category C');
  if activities.Contains(search) then
    ShowMessage('found');

  ShowMessageFmt('Index: %d', [activities.IndexOf(search)]);
  activities.Sort;
  ShowMessageFmt('Index: %d', [activities.IndexOf(search)]);


  search.Name := 'Category D';
  if not activities.Contains(search) then
    ShowMessage('not found');

  search.Free;
  activities.Free;
end;

Thumbnail

You can pass in your comparer but IComparer requires that both sides of the comparison must be instances of the specialized type. If I understood it correctly, the OP wants to avoid creating an instance for the purpose of searching; here's my attempt (as an answer to a similar question). – Kazim

@TOndrej: My answer is considering the comments to Masons answer – Thumbnail

Answer 2

If you don't have an instance to search for, you have to do your own search. There are three basic ways to do this:

• Binary search: Implement your own binary search. This will only work if the list is sorted.
• Linear search: Implement your own linear search. This will always work, but on large lists it's significantly slower than a binary search.
• Dictionary lookup: Maintain a TDictionary<string, TActivityCategory> alongside the list. No searching required, though you need to write some code to keep the two in sync.

Molnar

TList<T> can do this fine with a custom comparer – Celsacelsius

I like the Dictionary lookup idea but it seems that there must be a more elegant solution. – Heresiarch

If you don't have an instance, you can just create one. You only have to set the fields you actually use in your provided comparer. – Adoration

Would you mind showing an example? – Heresiarch

Answer 3

To be perfectly frank, and considering all the boiler plate required for a comparer based approach, it may just be simplest to write your own search routine:

type
  TActivityCategoryList = class(TList<TActivityCategory>)
  public
    function Find(const Name: string): Integer;
  end;

function TActivityCategoryList.Find(const Name: string): Integer;
begin
  for Result := 0 to Count-1 do
    if Self[Result].Name=Name then
      exit;
  Result := -1;
end;

Celsacelsius

Yeah, and when you are done someone thinks it would be a nice idea to have that list sorted by category name... whoops – Thumbnail

@Stefan I suppose my answer is born of frustration from known what the solution would be in C#. Delphi and its library just aren't composable enough. The fact that the comparer has to be assigned at list creation time is a killer. How do you use that approach to search the same list by name and category? Is there a library function that we have missed? – Celsacelsius

No and that is why everyone that is seriously working with lists and doing more than storing things in it like searching by different criteria should forget about the built-in generic lists and look at Collections or Spring. They both have things similar to the IEnumerable<T> extension methods in C#. – Thumbnail

@Stefan Thanks a lot for the tip. I will take a look at those libraries. – Celsacelsius