Arrays are sufficient for ArrayLists? Really??

[Andrei Alexandrescu]

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. It is 
possible a reallocation does occur even if the capacity would be 
sufficient, but that's a rare phenomenon caused by implementation 
paraphernalia. The formal guarantee is that ~= takes amortized constant 
time.

If you need an absolute guarantee that the array stays as initially 
allocated, you can't use ~=, but you can still use std.algorithm.remove.


Andrei