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