Complexity guaranties of array append operator

[Steven Schveighoffer via Digitalmars-d-learn]

On 11/5/14 10:48 PM, Dmitriy wrote:
> Hello, I'm in the middle of learning D. I can't find any definitive
> information about what is the complexity of operator ~= when used for
> adding an element to an array. Is it amortized O(1) or is it
> implementation defined? (I hope it at worst O(n) though I haven't seen
> any information about that either).

It's amortized O(1).

>
> Also documentation to std.array.Appender says that "it is more
> efficient" to use Appender "when appending many elements". Does it imply
> that Appender.put has amortized O(1)?

As Jonathan said, it's because array append needs to look up information 
in the GC, which can be costly (we have mechanisms to mitigate this 
somewhat, but it can't be inlined). The Appender has all the information 
it needs handy, and can be inlined. The disadvantage is that the 
Appender may have higher up-front costs, and does not have some of the 
same properties as a builtin array.

You may find this article helpful: http://dlang.org/d-array-article.html

-Steve