Complexity guaranties of array append operator

[Jonathan M Davis via Digitalmars-d-learn]

On Thursday, November 06, 2014 03:48:26 Dmitriy via Digitalmars-d-learn 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).
>
> 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)?

They should both be an amortized O(1). As I understand it, the problem with
~= over using Appender is the extra checks that the runtime has to do with
~= to see whether there's room to append anything without reallocating, and
because Appender is free to assume that the whole block of memory is for its
personal use rather than having to worry about other dynamic arrays which
are backed by slices of the same block of memory extending into that memory
first, it's able to check for available capacity much faster. So, it's the
coefficient that changes, not the overall complexity. For the complexity to
change, you'd have to get behavior like ~= _always_ reallocating (and thus
having to copy all of the elements every time) rather than just when there
isn't any extra capacity, and that's not the case at all.

- Jonathan M Davis