Move() to Insert/Delete item(s) from a dynamic array of string

Question

Using System.Move() to insert/delete item(s) from an array of string is not as easy as insert/delete it from other array of simple data types. The problem is ... string is reference counted in Delphi. Using Move() on reference-counted data types needs deeper knowledge on internal compiler behaviour.

Can someone here explain the needed steps for me to achieve that, or better with some snippet codes, or direct me to a good reference on the internet?

Oh, Please don't tell me to use the "lazy-but-slow way", that is, for loop, I know that.

Answer 1

You don't state if it is important for you to keep the array elements in the same order or not. If the order is not relevant, you can so something really really fast like this:

procedure RemoveRecord(Index: integer);  
begin
 FRecords[Index]:= FRecords[High(FRecords)];  { Copy the last element over the 'deleted' element }
 SetLength(FRecords, Length(FRecords)-1);     { Cut the last element }
end;

{ I haven't tested the code to see it compiles, but you got the idea anyway... }

Sorting the list
If you have a HUGE list that needs to be modified by the user, you can use methods similar to the one above that breaks the list order. When the user its done editing (after multiple deletes), you present it with a button called "Sort list" or simply "Apply changes". Now he can do the lengthy (sort) operation.
Of course, I assume above that your list can be sorted by a certain parameter.

Sorting the list automatically
An alternative is to automate the sorting process. When the user deleted stuff from the list, start a timer. Keep resetting the timer if the user keeps deleting items. When the timer manages to trigger an event, do the sorting, stop the timer.

Answer 2

Move() works fine with reference counted types like strings or interfaces, and actually used internally in Delphi's arrays and lists. But, now, in general case, Move() is no longer valid because of managed records feature.

Answer 3

Just wanting to add this for any people that come here in the future.

Modifying Rob's code, I came up with this way of doing it that uses the newer TArray<T> type constructions.

type
  TArrayExt = class(TArray)
    class procedure Delete<T>(var A: TArray<T>; const Index: Cardinal; Count: Cardinal = 1);
  end;

implementation

class procedure TArrayExt.Delete<T>(var A: TArray<T>; const Index: Cardinal;
    Count: Cardinal = 1);
var
  ALength: Cardinal;
  i: Cardinal;
begin
  ALength := Length(A);
  Assert(ALength > 0);
  Assert(Count > 0);
  Assert(Count <= ALength - Index);
  Assert(Index < ALength);

  for i := Index + Count to ALength - 1 do
    A[i - Count] := A[i];

  SetLength(A, ALength - Count);
end;

A similar thing can be done for the insert.

(Not looking for this to get marked as the answer, just looking to provide an example that was too long to fit in the comments on Rob's excellent answer.)

(Fixed to address Rob's comments below.)

Answer 4

I've demonstrated how to delete items from a dynamic array before:

• Delphi Q&A: How do I delete an element from an array?

In that article, I start with the following code:

type
  TXArray = array of X;

procedure DeleteX(var A: TXArray; const Index: Cardinal);
var
  ALength: Cardinal;
  i: Cardinal;
begin
  ALength := Length(A);
  Assert(ALength > 0);
  Assert(Index < ALength);
  for i := Index + 1 to ALength - 1 do
    A[i - 1] := A[i];
  SetLength(A, ALength - 1);
end;

You cannot go wrong with that code. Use whatever value for X you want; in your case, replace it with string. If you want to get fancier and use Move, then there's way to do that, too.

procedure DeleteX(var A: TXArray; const Index: Cardinal);
var
  ALength: Cardinal;
  TailElements: Cardinal;
begin
  ALength := Length(A);
  Assert(ALength > 0);
  Assert(Index < ALength);
  Finalize(A[Index]);
  TailElements := ALength - Index;
  if TailElements > 0 then
    Move(A[Index + 1], A[Index], SizeOf(X) * TailElements);
  Initialize(A[ALength - 1]);
  SetLength(A, ALength - 1);
end;

Since X is string, the Finalize call is equivalent to assigning the empty string to that array element. I use Finalize in this code, though, because it will work for all array-element types, even types that include records, interfaces, strings, and other arrays.

For inserting, you just shift things the opposite direction:

procedure InsertX(var A: TXArray; const Index: Cardinal; const Value: X);
var
  ALength: Cardinal;
  TailElements: Cardinal;
begin
  ALength := Length(A);
  Assert(Index <= ALength);
  SetLength(A, ALength + 1);
  Finalize(A[ALength]);
  TailElements := ALength - Index;
  if TailElements > 0 then begin
    Move(A[Index], A[Index + 1], SizeOf(X) * TailElements);
  Initialize(A[Index]);
  A[Index] := Value;
end;

Use Finalize when you're about to do something that's outside the bounds of the language, such as using the non-type-safe Move procedure to overwrite a variable of a compiler-managed type. Use Initialize when you're re-entering the defined part of the language. (The language defines what happens when an array grows or shrinks with SetLength, but it doesn't define how to copy or delete strings without using a string-assignment statement.)

Answer 5

Call UniqueString() on it, before messing with it.

http://docwiki.embarcadero.com/VCL/en/System.UniqueString

Then you have a string with a single reference.

Fat chance that that is what delete and insert do too, and I doubt you'll be faster.

Answer 6

If you use System.Move to put items into an array of string, you should be aware that the strings that where there before the Move (and now overwritten), had a reference count of either -1 for constant strings, or > 0 for variable strings. Constant strings should not be altered, but variable strings should be treated accordingly: You should manually lower their reference-count (before they're overwritten!). To do that, you should try something like this:

Dec(PStrRec(IntPtr(SomeString)-12).refCnt);

But if the reference-count reached zero, you should also finalize the associated memory - something Delphi itself does a whole lot better if you let it work it's compiler-magic for strings. Oh, and also : if the strings you're copying come from the same array as your writing into, the needed administration becomes very cumbersome, very quickly!

So if it's in some way possible to avoid all this manual housekeeping, I would advise to let Delphi handle it itself.

Answer 7

If I wanted to insert a string into the middle of a list of strings, I'd use TStringList.Insert. (It does it quickly using System.Move.)

Any particular reason why you're using an array instead of a TStringList?

Answer 8

To insert a string, simply add a string (the lazy way) to the end of the array (which is an array of pointers), and then use Move to change the order of the elements of this array (of pointers).