Arrays are sufficient for ArrayLists? Really??

[Steven Schveighoffer]

On Mon, 16 May 2011 15:16:16 -0400, %u <wfunction at hotmail.com> wrote:

> Timon:
>> What about:
> void removeAt(T)(ref T[] arr, size_t index)
> {
>    foreach (i, ref item; arr[1 .. index+1])
>         item = arr[i - 1];
>     arr = arr[1 .. $]; //note how no valid data is beyond the end of
> the array
> }
>
> Clever, but if you do this with a big enough number of items, you'll
> exhaust all memory. Be careful. :P

It should be fine, as long as you are using appending to grow the array.   
When an append requires a reallocation, it will only reserve enough space  
for the valid elements.  However, there are certain cases that will make  
the array continue to grow in place by adding more pages.  But this will  
only happen if you get more than half a page of data, and pages are  
available to concatenate.

It's actually a pretty clever way to avoid hitting the runtime when you  
need to remove an element.  As long as it doesn't invalidate other  
references to the array elements, you should be good.

> Steven:
>> 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.
>
> Ah, seems to be what I need.
>
> I guess I was also trying to argue this should really be part of the
> language too, though (not just Phobos), given that concatenation and
> even hashtables are also part of the language. It seems to be
> missing badly. :\

builtin arrays are full of features that are "good enough" for most  
usages.  Removing elements the way that is least confusing is inefficient,  
and removing elements the most efficient way can be confusing or incorrect  
depending on the application.  Rather than guess what the user expects,  
the runtime just leaves it up to the developer/standard lib.

-Steve