[fpc-pascal] TFPGMap retrieving values
Ryan Joseph
genericptr at gmail.com
Fri May 1 16:12:59 CEST 2020
I've been starting to use the RTL so I'm not very familiar with it but I thought TFPGMap was supposed to be a hash table for fast lookup, so why does TFPSMap.Find using a binary search instead of computing a hash key and indexing into the array like that? Is this not the type I should be using in the RTL for a generic hash table? What even is TFPGMap supposed to be if it isn't a hash table?
function TFPSMap.Find(AKey: Pointer; out Index: Integer): Boolean;
{ Searches for the first item <= Key, returns True if exact match,
sets index to the index of the found string. }
var
I,L,R,Dir: Integer;
begin
Result := false;
Index := -1;
if not Sorted then
raise EListError.Create(SErrFindNeedsSortedList);
// Use binary search.
L := 0;
R := FCount-1;
while L<=R do
begin
I := L + (R - L) div 2;
Dir := FOnKeyPtrCompare(Items[I], AKey);
if Dir < 0 then
L := I+1
else begin
R := I-1;
if Dir = 0 then
begin
Result := true;
if Duplicates <> dupAccept then
L := I;
end;
end;
end;
Index := L;
end;
Regards,
Ryan Joseph
More information about the fpc-pascal
mailing list