Arrays are sufficient for ArrayLists? Really??

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon May 16 12:38:04 PDT 2011


On 5/16/11 2:31 PM, Mehrdad wrote:
> On 5/16/2011 12:25 PM, Andrei Alexandrescu wrote:
>> On 5/16/11 2:25 PM, Timon Gehr wrote:
>>> Mehrdad 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
>>>
>>> Total memory usage is at most 2 times the maximum size the array
>>> reaches during
>>> its lifetime. Test it.
>>
>> Testing would also reveal that this is a buggy replica of
>> std.algorithm.remove. At best we should suggest reusing library code
>> over attempting to reinvent it.
>>
>>
>> Thanks,
>>
>> Andrei
>>
>
> Oh, I see.
> Wait, what bug are you referring to, though?

I was mistaken and removed my post. The code ingeniously redefines the 
problem - instead of removing from the array by shifting its tail 
downwards, it shifts elements upwards from the head of the array. A nice 
hack, but I don't think it does a lot in helping your situation.

There's a bit of history wrt ~=. Initially the behavior was to never 
reallocate if there was enough capacity. But that caused a stomping 
issue - people would create an array, pass a slice of it to a function, 
and then the function would clobber elements in the arrays outside the 
slice. This was a major breakage of modular behavior so we decided to 
change the behavior: as long as you keep references to the original 
array, appending to a slice of it will cause reallocation of the array.

One thing you could do is to think of what you're trying to achieve on a 
larger scale. Assuming a slice to grow over the original array is 
arguably a bad behavior that I'm sure could be fixed by small changes in 
the design.


Andrei


More information about the Digitalmars-d mailing list