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

[Jonathan M Davis]

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