Seltsames Verhalten von IndexOf bei sortierter generischer Liste

[Sir Rufo]

Ich habe hier mal ein ganz merkwürdenes Verhalten bei einer generischen sortierten Liste.
Die Einträge werden sehr hübsch sortiert ... aber fragt man jetzt nach dem Index von einem Element, dann kommt die Liste wohl etwas durcheinander.

Hier mal die Ausgabe von dem Programm:

Code:

  ID  Value  List.IndexOf
  ==  =====  ============
  20   4080             0
  12   4081             1
  11   4081             1
  19   4081             1
  13   4081             1
   1   4081             1
  10   4082             6
   3   4272             7
   2   4272             7
  16   4272             7
   5   4272             7
   7   4272             7
  21   4272             7
   4   4273            13
   9   4304            14
  17   4313            15
   8   4313            15
   6   4313            15
  14   4313            15
  15   4314            19
  18   4314            19
  22  38892            21

Irgendwie seltsam ... hätte ich auf jeden Fall nicht so erwartet, zumal die Sortierung auch manuell angestossen werden muss ... fügt man weitere Elemente hinzu, so ist die Liste nicht automatisch sortiert, aber für die Bestimmung des Item-Index wird der Comparer bemüht ...

Hat jemand dafür eine Erklärung und ist das ein gewolltes Verhalten?

Hier der Source:

Delphi-Quellcode:

program SortList;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils,
  System.Generics.Collections, System.Generics.Defaults;

type
  TItem = class
  private
    FValue : Integer;
    FID :    Integer;
  public
    constructor Create( AID, AValue : Integer );

    property ID : Integer read FID write FID;
    property Value : Integer read FValue write FValue;
  end;

  { TItem }

constructor TItem.Create( AID, AValue : Integer );
begin
  inherited Create;
  FID    := AID;
  FValue := AValue;
end;

procedure TestRun;
var
  LList : TList<TItem>;
  LItem : TItem;
begin
  LList := TObjectList<TItem>.Create( TComparer<TItem>.Construct(
        function( const L, R : TItem ) : Integer
    begin
      Result := L.Value - R.Value;
    end ) );

  LList.Add( TItem.Create( 1, 4081 ) );
  LList.Add( TItem.Create( 2, 4272 ) );
  LList.Add( TItem.Create( 3, 4272 ) );
  LList.Add( TItem.Create( 4, 4273 ) );
  LList.Add( TItem.Create( 5, 4272 ) );
  LList.Add( TItem.Create( 6, 4313 ) );
  LList.Add( TItem.Create( 7, 4272 ) );
  LList.Add( TItem.Create( 8, 4313 ) );
  LList.Add( TItem.Create( 9, 4304 ) );
  LList.Add( TItem.Create( 10, 4082 ) );
  LList.Add( TItem.Create( 11, 4081 ) );
  LList.Add( TItem.Create( 12, 4081 ) );
  LList.Add( TItem.Create( 13, 4081 ) );
  LList.Add( TItem.Create( 14, 4313 ) );
  LList.Add( TItem.Create( 15, 4314 ) );
  LList.Add( TItem.Create( 16, 4272 ) );
  LList.Add( TItem.Create( 17, 4313 ) );
  LList.Add( TItem.Create( 18, 4314 ) );
  LList.Add( TItem.Create( 19, 4081 ) );
  LList.Add( TItem.Create( 20, 4080 ) );
  LList.Add( TItem.Create( 21, 4272 ) );
  LList.Add( TItem.Create( 22, 38892 ) );

  LList.Sort;

  WriteLn( 'ID':4, 'Value':7, 'List.IndexOf':14 );
  WriteLn( '==':4, '=====':7, '============':14 );
  for LItem in LList do
    begin
      WriteLn( LItem.ID : 4, LItem.Value : 7, LList.IndexOf( LItem ) : 14 );
    end;

end;

begin
  try

    TestRun;

  except
    on E : Exception do
      WriteLn( E.ClassName, ': ', E.Message );
  end;

  Readln;

end.

[Bummi]

Wenn man sich die Implementierung von
function TList<T>.IndexOf(const Value: T): Integer; anschaut ....
Gegf. könntest Du

Delphi-Quellcode:

function( const L, R : TItem ) : Integer
    begin
      Result := L.Value - R.Value;
    end )

erweitern um einen Vergleich von ID wenn Value identisch ist.....

[SirThornberry]

Sieht aus als ob IndexOf nicht nach dem Pointer(Objektinstanz) in der Liste schaut sondern per Comparer nach Übereinstimmung sucht und dann den ersten Index zurück gibt bei dem die Werte übereinstimmen.

[Furtbichler]

Ich habe den Quellcode nicht, aber falls IndexOf iterativ umgesetzt ist, ist das Verhalten doch vollkommen ok.

Deine Ordnungsfunktion ist nicht vollständig implementiert, d.h. es gilt eben nicht: A != B => f(A) != f(B)

Lösung? => Bummi

Zitat von Sir Rufo:

... fügt man weitere Elemente hinzu, so ist die Liste nicht automatisch sortiert, aber für die Bestimmung des Item-Index wird der Comparer bemüht ...

Wieso erwartest Du, das die Liste automatisch sortiert ist? Das wäre doch performancetechnisch völliger Quark und ist außerdem nicht die Aufgabe einer Liste.

Die Liste ist ein Container für Elemente. Mit der Definition einer Ordnungsrelation ('Comparer') und der Sort-Methode kann eine totale Ordnung hergestellt werden. Nach dem Einfügen eines Elements kann die Ordnung zerstört werden.

Und natürlich muss der Comparer bemüht werden, woher sonst soll die Liste wissen, ob zwei Elemente 'gleich' sind? Das 'gleich' wird ja gerade durch den Comparer definiert.

Was passiert, wenn Du keine Ordnungsrelation angibst? Geht das?

[Sir Rufo]

Zitat von Furtbichler:

Zitat von Sir Rufo:

... fügt man weitere Elemente hinzu, so ist die Liste nicht automatisch sortiert, aber für die Bestimmung des Item-Index wird der Comparer bemüht ...

Wieso erwartest Du, das die Liste automatisch sortiert ist? Das wäre doch performancetechnisch völliger Quark und ist außerdem nicht die Aufgabe einer Liste.

Ich erwarte doch nicht, dass die Liste sich automatisch selber sortiert. Aber ich erwarte eben von einer Liste, dass ich mit IndexOf den Index des Elements in der Liste bekomme, also

Delphi-Quellcode:

MyIndex := 4;
Assert( MyList.IndexOf( MyList[MyIndex] ) = MyIndex );

Den Comparer habe ich jetzt erweitert zu

Delphi-Quellcode:

  LList := TObjectList<TItem>.Create( TComparer<TItem>.Construct(
        function( const L, R : TItem ) : Integer
    begin
      Result := L.Value - R.Value;
      if Result = 0
      then
        Result := Integer( L ) - Integer( R );
    end ) );

bzw. im originalen Code merke ich mir einfach den Index und der Kas ist gegessen.

[Elvis]

Wenn du über den Comparer gar nicht die Identität einer Instanz bestimmen willst, warum gibst du ihn der Liste mit?
Sortiere doch einfach nur danach und gut ist:

Delphi-Quellcode:

list.Sort(TComparer<TSample>.Construct(function(const l, r : TSample) : Integer
begin
  result := AnsiCompareStr(l.Text, r.Text);
end));

[Sir Rufo]

Zitat von Elvis:

Wenn du über den Comparer gar nicht die Identität einer Instanz bestimmen willst, warum gibst du ihn der Liste mit?
Sortiere doch einfach nur danach und gut ist:

Delphi-Quellcode:

list.Sort(TComparer<TSample>.Construct(function(const l, r : TSample) : Integer
begin
  result := AnsiCompareStr(l.Text, r.Text);
end));

Wenn das bei einer generischen Liste gehen würde ...

[Elvis]

Zitat von Sir Rufo:

Wenn das bei einer generischen Liste gehen würde ...

In meinem D2010 gates.

[stahli]

Zitat von Elvis:

In meinem D2010 gates.

[OT] [/OT]

[Stevie]

Zitat von Sir Rufo:

Zitat von Elvis:

Wenn du über den Comparer gar nicht die Identität einer Instanz bestimmen willst, warum gibst du ihn der Liste mit?
Sortiere doch einfach nur danach und gut ist:

Delphi-Quellcode:

list.Sort(TComparer<TSample>.Construct(function(const l, r : TSample) : Integer
begin
  result := AnsiCompareStr(l.Text, r.Text);
end));

Wenn das bei einer generischen Liste gehen würde ...

Tut es:

Delphi-Quellcode:

  LList.Sort( TComparer<TItem>.Construct(
    function( const L, R : TItem ) : Integer
    begin
      Result := L.Value - R.Value;
    end ) );

Generell würde ich aber empfehlen, in den Vergleich die ID mit aufzunehmen. Dann kannst du den Comparer beim Create schon übergeben.