D: Adding elements to array without copying

Question

I must be completely daft, since I just couldn't quite get this bit: How do I add elements to an array without it being copied.

In other words let's say I want to create a big list of something:

int[] arr;

while (...) { // 1,000,000 iterations
    ...
    arr ~= something;
    ...
}

I don't quite understand when ~= will just add to the array, and when it will create a copy of it.

To clarify, I'm looking for semantics like ArrayList in Java or C#, i.e some abstract container that I can put things into and will grow if needed, but generaly remain the same "object" (i.e if passed around etc).

Answer 1

It works pretty much the same as an ArrayList works in that it has a capacity which is the number of elements that it can grow to until it has to reallocate. However, it's complicated by the fact that passing an array to a function slices it rather than having it be the same array. If you're just using a local variable though and don't assign it to anything, it shouldn't matter when in reallocates, other than for efficiency.

The article that you should read is this: http://dlang.org/d-array-article.html

I think that it uses slightly wrong terminology, since it refers to the block of memory that the runtime manages as being the dynamic array rather than T[] - which is what the spec considers to be a dynamic array, whereas the block of memory just happens to be what's backing the array at the moment - but it does a great job of explaining a lot of the details of how arrays in D work. So, it should be quite enlightening.

Also, you should probably consider using std.array.Appender if you're doing a lot of appending. e.g.

auto app = appender!(int[])();

while (...) { // 1,000,000 iterations
    ...
    app.put(something);
    ...
}

int[] arr = app.data;

It will make appending more efficient. In general though, you'll probably do better if you create arrays and then operate on them rather than appending to them again later. Obviously, that doesn't fit all use cases, but if you do, then you never have to worry about whether one slice still refers to the same memory as another - either that or code in a way that you don't rely on two slices referring to the same memory.

An alternative would be to use std.container.Array which is a full reference type (instead of a half-reference type like D's dynamic arrays are). Certainly, if you want to be passing around an array, have multiple slices of it all referring to the same memory, and keep appending to it, you should probably consider using Array instead.