[fpc-devel] Do we need a TFPGMap.IsSorted method?

Amir amir at aavani.net
Wed Sep 2 00:38:15 CEST 2020

Hi there,

   The other day, I wanted to write a code to memorize and search some 
values (something like the following):

     MyMap := TIntIntMap.Create;
     for  i := 1 to ABigNumber do

To have fast lookup, I had to set myMap.Sorted := True. But then noticed 
that setting this property, in the worst case, requires O(ABigNumber^2) 
step:  TFPSMap.SetSorted is implemented as:
   if Value = FSorted then exit;
   FSorted := Value;
   if Value then Sort;

The keys are sorted and Sort is a quick sort (which sucks if the input 
data is already sorted).

Wondering if it makes sense to change the implementation to
   if Value = FSorted then exit;
   FSorted := Value;
   if Value and not IsSortedFunc then

The other option could be to add a new read-only MyMap.IsSorted where 
the getter is implemented as:

   if FSorted then
   FSorted := IsSortedFunc;
   Result := FSorted;


More information about the fpc-devel mailing list