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.

Solution 1

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.)

Solution 2

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 (break the list order). When the user its done editing (after multiple deletes), you present it with a button called "Sort list". 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.

Solution 3

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).

Solution 4

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?

Solution 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.

View more solutions

Comments

[Phantom]

For performance reason because my array would be possible to be filled with huge amount of items. I realize that TStringList.Capacity will help, but TStringList will still do unnecessary checking--according to the documentation-- "... assigning a value smaller than Count removes strings from the end of the list. Assigning a value greater than Count allocates space for more strings to be added." In my case, I don't need such a check.

[Andreas Rejbrand]

@Phantom: Well, as long as you measure the actual overhead of the TStringList approach. Many people are surprisingly tolerant to delays of a few milliseconds.

[Mason Wheeler]

@Phantom: Fair enough, but there are other performance implications to take into account. For example, if you have to fill your array with a huge number of strings, are you using SetLength(MyArray, length(MyArray) + 1) every time? That's a huge number of reallocs and copies, and it can really drag performance down. To head this issue off, you have to allocate more space than you're using, so you need something to keep track of capacity and current count. To manage that, you should encapsulate it within an object... and then you're well on the road to reinventing the TStringList. :P

[Andreas Rejbrand]

Yes, Mason is absolutely right. The example in his comment is one of the most common and severe Delphi performance issues. But, @Phantom, since you are talking about Move, I'd guess that you already are aware of this issue.

[Phantom]

@Mason, No, I will allocate memory, just said, for 16384 items, and will allocate more 16384 if it is apparently needed.

[Phantom]

@Mason, I doesn't intend to reinvent TStringList. There are so many feature in TStringList which I don't need to work in this array. To be honest, the array will be fild with all files in all hard-drives attached to a computer.

[Andreas Rejbrand]

@Phantom: But you do need to reorder the items of the array?

[Phantom]

@PatrickvL: So, do you still recommend me to use TStringList even if for my case, that is, the array will be filled with all files in all hard-drives attached to a computer. Will TStringList be fast enough?

[Phantom]

@Andreas, No, the items doesn't need to be sorted.

[Phantom]

AFAIK, because either deletion or insertion items to an array doesn't need any sorting/indexing mechanism.

[Phantom]

@Andreas, TStringList use System.Move() instead of such a for loop. Looking TStringList implementation at a glance, I couldn't grasp the real requirements to use Move() on reference-counted data types. However, it seems I need to study it deeper, and also the @PatrickvL's comment.

[Mason Wheeler]

@Phantom: TStringList was designed for handling large numbers of strings. If you have Delphi you've got Classes.pas; browse through the code to TStringList and TStrings and see how many bits of code you can find that are there specifically for performance reasons. It's one of the most used classes in the entire RTL, and it's been tested extensively for 15 years now. You'd have to work pretty hard to come up with any solution that's noticeably faster than TStringList at string handling. If you want to know if it's slow, try using it and see if it feels slow or not.

[Andreas Rejbrand]

@Phantom: TStringList (of course!) only uses Move if it needs to change the order of the strings, for instance, if you insert a string in the middle of the array (for then all strings after the newly inserted one need to move down the array). If you simply add a string to the bottom of the array, no Move is needed, neither in a array of string nor in a TStringList!

[Rob Kennedy]

-1 for suggesting manual modification of internal, implementation-defined data structures. You could have just assigned SomeString := '' and let the compiler take care of the zero-reference-count situation, as well as thread-safety.

[Rob Kennedy]

"Fat chance" means something is unlikely. For example: "Do you think our boss will give us a bonus this year?" "Fat chance!" Calling UniqueString is exactly what Delete and Insert will do when changing the character contents of a string. There's no need to call it when changing the element contents of a dynamic array, though.

[Phantom]

@Andreas, oops, I misunderstood what you meant, now I catch it. :-)

[Phantom]

thank you very much. :-) I will try your snippet code, and will accept this as accepted answer if it succeeds. But I have to go to the office now. :-)

[Marco van de Voort]

Oops, expressions are always pain in foreign languages :-) Anyway, I missed the "array of" bit. Then just finalizing the deleted bits and initializing the non deleted bits (or filling them with zero) would do

[PatrickvL]

@Rob : I was just answering Phantom's question how to decrease a reference count manually. I believe that's a valid question to answer - even when it's not advisable to do so! (Didn't I mention that in my last statement?) Sure, setting Somestring := '' works too, but that relies on compiler magic again, so my answer has some credibility, don't you think?

[Rob Kennedy]

No, Patrick, the question did not ask how to reduce the reference count of a string. Phantom merely indicated that he knew reference-counting was an issue to be concerned with when using Move, so he asked how to use Move to adjust an array of strings. There was nothing to suggest the array was actually just a blob of untyped memory, so there's no reason to think compiler magic's not available.

[Phantom]

just a suggestion, or maybe a request, we will be happy if you please to update your mentioned article to also include insertion. I like your webpage design.

[jep]

I modified Rob's code to provide a way of doing this using the newer TArray<T> construction. What do you think, Rob? Any problems I missed?

[Rob Kennedy]

You attempted to make too many changes at once. Making my code use generic TArray would have been fine, but you decided to add another feature, and in doing so, you broke the whole thing. I don't think there's any input that makes this function work.

[jep]

Do you have anything more specific to say than that? I actually fixed the one error that I believe is there (I had my 0/1 transposed on the if Index = 0 then conditional). I'm actually using it right now and it's seemingly working fine. If there's an error, it's definitely not very obvious at debug/runtime. Constructive criticism welcome.

[Ken White]

Can you explain how this addresses the question of "Using Move() to insert/delete items from a dynamic array of string"? I see an iterative loop that has nothing to do with using Move whatsover, doesn't address a dynamic array of string (a generic TArray<string> is not a dynamic array of string), and the question specifically asks not to use a loop, because the poster already knows how to do so. IOW, this has absolutely zero pertinence to the question asked here; posting random non-related answers to questions isn't really how SO works.

[Rob Kennedy]

Transposing didn't help. Any time Index is nonzero, you end up writing to A[-1]. The first spot you write to should always be A[Index]. Look at my code. Why is the starting index ever conditional in the first place? You could get closer to your intended feature set by going back to my code and replacing each occurrence of 1 with Count.

[jep]

Thanks, that was more constructive. Actually, it was mainly looking at my code after a night's sleep and going "wait, why did I write THAT?" I have no idea at this point but the answer was pretty obvious. I've went through several rounds of pen and paper walkthroughs, so I'm confident that it's right at this point.

[inzKulozik]

Should be: TailElements := ALength - Index - 1; in DeleteX()