How to store dynamic arrays in a TList?

Question

I need to store an unknown number of groups. Each group has an unknown number of elements/items. This is my 'group':

 TGroup= array of Integer;     <------ dynamic array (as you can see) :)

I want to use a TList to hold my groups. The idea is that I may want to access the groups later and add more items to them.

I have this code, but I can't make it work:

TYPE
   TGroup= array of Integer;                              // Each group has x items (x can be from 1 to 10000)


procedure TForm1.FormCreate(Sender: TObject);
VAR CurGroup: TGroup;
    grp, item: Integer;
    Groups: TList;                                        // can contain up to 1 million groups
begin
 Groups:= TList.Create;

 { Init }
 for grp:= 1 to 4  DO                                     // Put a dummy item in TList
  begin
   SetLength(CurGroup, 1);                                // Create new group
   Groups.Add(@CurGroup);                                 // Store it
  end;

 CurGroup:= NIL;                                          // Prepare for next use

 for grp:= 1 to 4  DO                                     // We create 4 groups. Each group has 3 items
  begin
    CurGroup:= Groups[Groups.Count-1];                    // We retrieve the current group from list in order to add more items to it

    { We add few items }
    for item:= 0 to 2  DO
     begin
       SetLength(CurGroup, Length(CurGroup)+1);           // reserve space for each new item added
       CurGroup[item]:= Item;
     end;

    Groups[Groups.Count-1]:= @CurGroup;                   // We put the group back into the list
  end;

 { Verify }
 CurGroup:= NIL;
 CurGroup:= Groups[0];
 Assert(Length(CurGroup)> 0);                             // FAIL
 if  (CurGroup[0]= 0)
 AND (CurGroup[1]= 1)
 AND (CurGroup[2]= 2)
 then Application.ProcessMessages;                        

 FreeAndNil(Groups);
end;

Note: The code is complete. You can paste it in your Delphi (7) to try it.

Roberson

And by "group" you mean an associative magma with an identity element and such that every element has an inverse? – Counterirritant

@Andreas - No. For me the group is just a list (array) of numbers. This is my definition of 'group': TGroup= array of Integer; – Roberson

Answer 1

I've created a wrapper around dynamic array RTTI.

It's just a first draft, but it was inspired by your question, and the fact that the TList methods are missing.

type
  TGroup: array of integer;

var 
  Group: TGroup;
  GroupA: TDynArray;
  i, v: integer;
begin
  GroupA.Init(TypeInfo(TGroup),Group); // associate GroupA with Group
  for i := 0 to 1000 do begin
    v := i+1000; // need argument passed as a const variable
    GroupA.Add(v);
  end;
  v := 1500;
  if GroupA.IndexOf(v)<0 then // search by content
    ShowMessage('Error: 1500 not found!');
  for i := GroupA.Count-1 downto 0 do
    if i and 3=0 then
      GroupA.Delete(i); // delete integer at index i
end;

This TDynArray wrapper will work also with array of string or array of records... Records need only to be packed and have only not reference counted fields (byte, integer, double...) or string reference-counted fields (no Variant nor Interface within).

The IndexOf() method will search by content. That is e.g. for an array of record, all record fields (including strings) must match.

See TDynArray in the SynCommons.pas unit from our Source Code repository. Works from Delphi 6 up to XE, and handle Unicode strings.

And the TTestLowLevelCommon._TDynArray method is the automated unitary tests associated with this wrapper. You'll find out here samples of array of records and more advanced features.

I'm currently implementing SaveToStream and LoadToStream methods...

Perhaps a new way of using generic-like features in all Delphi versions.

Edit:

I've added some new methods to the TDynArray record/object:

• now you can save and load a dynamic array content to or from a string (using LoadFromStream/SaveToStream or LoadFrom/SaveTo methods) - it will use a proprietary but very fast binary stream layout;
• and you can sort the dynamic array content by two means: either in-place (i.e. the array elements content is exchanged) or via an external integer index look-up array (using the CreateOrderedIndex method - in this case, you can have several orders to the same data);
• you can specify any custom comparison function, and there is a new Find method will can use fast binary search if available.

Here is how those new methods work:

var
  Test: RawByteString;
...
  Test := GroupA.SaveTo;
  GroupA.Clear;
  GroupA.LoadFrom(Test);
  GroupA.Compare := SortDynArrayInteger;
  GroupA.Sort;
  for i := 1 to GroupA.Count-1 do
    if Group[i]<Group[i-1] then
      ShowMessage('Error: unsorted!');
  v := 1500;
  if GroupA.Find(v)<0 then // fast binary search
    ShowMessage('Error: 1500 not found!');

Still closer to the generic paradigm, faster, and for Delphi 6 up to XE...

Photocell

Answer 2

Oh, this would be sooooo much nicer in newer versions of Delphi... You'd use the generic, TList<T>. var Groups: TList<TGroup>;

You're best bet is to use another dynamic array: Groups: array of TGroup;

The reason is that dynamic arrays are compiler managed and reference counted. TList only operates on Pointers. There is no straight forward way to keep the reference counts sane when trying to put the dynarrays into the TList.

Another issue you're having is that you're adding the stack address of the dynamic array variable to the TList, and not the actual array. The expression @CurGroup is the "address of the CurGroup variable" which being a local variable, is on the stack.

Circumstantial

+1. I have given up finding solutions for things that work out of the box with a recent Delphi. – Fluoride

I used 'array of TGroup' and it worked. But I just 'upgraded' from 'array of TGroup' as you propose to TList. I want to make it work also with TList. – Roberson

@Altar, What is it about TList that you feel is a superior solution? If the use of a dynamic array works, why not stick with that? Like I said, getting this to work with TList is likely going to be a more effort than it is likely worth. If you must use a TList, you're better off wrapping your TGroup in a TObject descendant and add that to the TList instead of the array. Then you just cast the TList "array" to your descendant object type to get at the dynarray. Have looked at the new Starter version of Delphi XE? only $149. – Circumstantial

@Allen: TList has several advantages over dynamic arrays, the most obvious being the Add, Remove and Insert methods. But as you pointed out, not having generics available makes using TList a real pain for managed data types. – Gingery

I think I will return to "array of TGroup". – Roberson

Answer 3

I don't have D7 on a machine here, but you might try something like this instead (console test app - it compiles in XE with no hints or warnings, but not sure how D7 will handle it):

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes;

type
  TGroup = array of Integer;
  THolder=class(TObject)
    Group: TGroup;
  end;

var
  GroupList: TList;
  i: Integer;

begin
  GroupList := TList.Create;
  for i := 0 to 2 do
  begin
    GroupList.Add(THolder.Create);
    with THolder(GroupList[GroupList.Count - 1]) do
    begin
      SetLength(Group, 3);
      Group[0] := i;
      Group[1] := i + 10;
      Group[2] := i + 20;
    end;
  end;
  for i := 0 to GroupList.Count - 1 do
  begin
    Writeln(i, ':0 ', THolder(GroupList[i]).Group[0]);
    Writeln(i, ':1 ', THolder(GroupList[i]).Group[1]);
    Writeln(i, ':2 ', THolder(GroupList[i]).Group[2]);
  end;
  // Not cleaning up list content, because we're exiting the app.
  // In a real app, of course, you'd want to free each THolder in 
  // the list, or use a TObjectList and let it own the objects.
  // You'd also want a try..finally to make sure the list gets freed.
  GroupList.Free;
  Readln;
end.

Indistinguishable

To me, a thoroughly reasonable approach in Delphi 7. – Silverman

Why didn't you use a TObjectList directly? – Photocell

@A.Bouchez, because that wasn't the question the OP asked. The question was specifically about TList. I added the suggestion for TObjectList as a comment in the code, though. – Indistinguishable

Answer 4

Another thing you may want to try is using a TObjectList. TObjectList is able to store a list of Objects, so you can create a new class descendant of TObject and then manage the TObjectList using these objects.

Something like (untested):

type TGroupArray : array of Integer;

type TGroup = class(Tobject)
  GroupArray : TGroupArray;
end;

GroupList : TobjectList;

procedure TForm1.FormCreate(Sender: TObject);                                        
var CurGroup : TGroup;
begin  

GroupList:= TObjectList.Create; 
CurGroup := TGroup.Create;
SetLength(CurGroup.GroupArray,1);
CurGroup.GroupArray[0] := 10;

GroupList.Add(CurGroup);

RetreiveGroup := GroupList.Items[0];
FreeandNil(GroupList);
end;

etc...

Eraser

I would do it this way. And when you need to add attributes like "Name:String" then you can just add it to TGroup which is a class. – Silverman

Answer 5

When you code:

 for grp:= 1 to 4  DO                                     // Put a dummy item in TList
  begin
   SetLength(CurGroup, 1);                                // Create new group
   Groups.Add(@CurGroup);                                 // Store it
  end;

in fact, SetLength(CurGroup) WON'T create a new group. It will resize the only one existing CurGroup.

So @CurGroup won't change: it will always be some address on the stack, where CurGroup is added. You add the same address to the list several times.

So You'll have to create a dynamic array of TGroup instances, like that:

var GroupArray: array of TGroup;

SetLength(GroupArray,4);
for grp := 0 to high(GroupArray) do
begin
  SetLength(GroupArray[grp],1);
  Groups.Add(@GroupArray[grp]);
end;

But of course, the GroupArray must remain allocated during all the time Groups will need it. So you'll have perhaps to put this GroupArray as a property in the class, because if you create this GroupArray on the stack, all GroupArray[] items will be released when the method exits and its stack is freed.

But of course, the GroupArray[] will be a more direct access to the TGroup items... Groups[i] will be equal to GroupArray[]... With no reference counting problem... Because e.g. if you resize for instance a TGroup item from its pointer in Groups[], I'm not sure that you won't have any memory leak...

Photocell

Hi Bouchez. "You'll have to create a dynamic array of TGroup instances" - - - Actually this is my initial code. It works perfectly. I just wanted to "upgrade" to TList which is less messy than array of array since it has the Add() method. – Roberson

"SetLength(CurGroup) WON'T create a new group" - - - You are right. I shrieked the code from a larger program to make it easier to read. In that code, the initialization of the list is actually correct since I don't use a loop to initialize it (I don't add the same element multiple times). - But thanks again! – Roberson

Answer 6

So, basically everybody suggests to create an array of array instead of using a TList. Well, I already have done that. I just wanted to "upgrade" from 'array of array' to a TList since it has Add(). It looks like I will return to my original code. Thank you all and +1 for each answer.

Roberson

Well, Allen suggest the new Delphi which makes this sort of code way cleaner. – Loxodromic

Yes. I know. But I don't have it. So, this solution is not at hand (for me). – Roberson

i suggested to use a TObjectList – Eraser

... and I just created a wrapper around any dynamic array to add Add() methods and such... :) – Photocell