Arrays are sufficient for ArrayLists? Really??

[Steven Schveighoffer]

On Mon, 16 May 2011 14:53:21 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 5/16/11 1:29 PM, Mehrdad wrote:
>>> As has been mentioned, std.algorithm.remove can be of help. You may  
>>> want to look at three of its
>> capabilities in particular: (a) remove multiple offsets in one pass,  
>> e.g. remove(a, 0, 4) removes
>> the first and fifth element, (b) you can remove subranges, e.g.  
>> remove(a, tuple(1, 3)) removes the
>> second through fourth element, and (c) if you don't care about the  
>> order in which elements are left
>> after removal you may want to look into unstable remove, which does  
>> considerably less work.
>>
>> Thanks for the idea. This seems great, except for a couple of things:
>>
>> - I _do_ need the order to stay the same, so I can't just put in the  
>> last element.
>
> Then you'd need to use the default swapping strategy.
>
>> - I only need to remove one element at a time.
>
> Then you may want to pass only one index.
>
>> - I still don't understand how this helps. Either this modifies the  
>> array directly, in which case
>> adding a new element to the array after a removal would still cause a  
>> reallocation every time, or
>> this returns a filtered range, in which case it doesn't do what I need  
>> (since it doesn't modify the
>> array directly)... am I missing something?
>
> After you remove some elements from an array by using  
> std.algorithm.remove, the array capacity stays the same. Appending to it  
> again will not reallocate the array if the capacity is sufficient.

This is not true.  In order to adjust the used array length, you must call  
assumeSafeAppend on the resulting array (which I would recommend you do  
after using remove in this case).  Remove can't do it for you, because it  
is a generic algorithm which takes a range, it doesn't "know" that it's  
working with an array.  Plus it doesn't know that it's working with a  
dynamic array.  Calling assumeSafeAppend could be a completely useless  
call.

For the OP, you may want to consider using ArrayList from dcollections,  
which supports removing an individual or range of elements, or using  
foreach to purge the list.  Note that this class does call  
assumeSafeAppend on its data storage since it can make more assumptions.

http://www.dsource.org/projects/dcollections

-Steve