Hot take: using `+` as the "concatenation operator" is evil. `+` should form an abelian group. `*` is obviously the natural choice for concatenation, as it only needs to form a monoid.
With a proper language and guaranteed optimization, it need not be quadratic. But with naive implementation/without combining multiple concatenations, it necessarily is.
-
-
I don't believe so? Assuming ownership semantics, `a + b + c` will be equivalent to `a.extend(b); a.extend(b); a`, which is amortized O(N)
-
Unless you resize the buffer speculatively (possibly wasting lots of memory when not needed) or have lookahead for final needed size, you need a realloc (thus memcpy) for each concatenation.
-
Ends up being O(nm) for total length n, m concatenations.
-
that assumes that we're resizing it each time tho. Let's say we implement it as for (el in other) a.push(el); each push is amortized O(1); this means that n pushes is O(n), so it'll be amortizer O(final_len - initial_len)
-
*amortized
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.