How do you remove/insert elements in a dynamic array without allocating?

[Malte Skarupke]

On Tuesday, 6 November 2012 at 01:25:39 UTC, Jonathan M Davis 
wrote:
> On Tuesday, November 06, 2012 02:11:06 Malte Skarupke wrote:
>> Following code:
>> 
>> void main()
>> {
>> import core.memory;
>> GC.disable();
>> scope(exit) GC.enable();
>> 
>> int[] a = [1, 2, 3, 4, 5];
>> foreach(i; 0 .. 1000000000)
>> {
>> --a.length;
>> a ~= i;
>> }
>> }
>> 
>> That loop will keep on allocating in every iteration until your
>> memory is full.
>> 
>> Is there a way to do something similar to this without
>> allocating? I have also tried slicing:
>> a = a[0 .. $ - 1]; // instead of (--a.length;)
>
> There's no real difference between those two.
>
>> But neither one works.
>> 
>> How do you work with the dynamic array without having to rely 
>> on
>> the GC all the time? I want something similar to the stl 
>> vector,
>> which only re-allocates once your array grows past a certain
>> size, not on every append.
>
> Arrays do work that way. They have capacity, and they have 
> reserve. They only
> append when they don't have enough memory or they're not the 
> last slice in the
> block. The problem is that if you remove elements, the runtime 
> doesn't know if
> there's another slice pointing to the element which was just 
> removed, so it
> has to assume that that there is, and it'll be forced to 
> reallocate when
> appending.
>
> If you _know_ that there are no slices of anything beyond the 
> end of the
> array, then you can call assumeSafeAppend on the array, and 
> then the runtime
> will mark it as the last slice in the block, and appending 
> won't reallocate
> unless it actually runs out of space in the block (or you end 
> up removing
> another element without calling assumeSafeAppend or you end up 
> with a slice
> which contains elements beyond the end of that array - e.g. if 
> you slice the
> array and then append to the slice). So, in this particular 
> case,
> assumeSafeAppend would solve your problem. Whether it works in 
> your program in
> general depends on what your program is doing. And if you want 
> to make sure
> that the array has enough space before appending to it a bunch, 
> then you can
> use reserve. However, if you're specifically building an array, 
> you should
> probably look at std.array.Appender. Don't remove elements from 
> that though.
> It's just for making appending more efficient, not for being 
> used once the
> array has been fully constructed.
>
> If you haven't read it yet, I'd strongly advise reading this 
> article on arrays
> in D:
>
> http://dlang.org/d-array-article.html
>
> - Jonathan M Davis

Thanks, that explains it well. I must admit that I didn't fully 
understand slices before. I've read the linked article and am 
baffled that this is seen as acceptable behavior. I will most 
certainly never use dynamic arrays or slices again for anything 
that needs to grow or shrink dynamically.