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