ListBuffer ++= ListBuffer O(1) time


So as I understand it, ListBuffers leverage the hidden mutable state of lists to permit O(1) operations for stuff like appending, prepending taking the size of a list etc.

However, as far as I can tell, ++= is not specialised for a ListBuffer? ++= is O(n) in the size of the first collection usually, but surely if we append two list buffers we can do it in O(1) time;

b ++= c
b.last.t1 = c.start

with obviously the extra cases for empty lists etc. Is there any reason why this isn’t done in the STL at the moment?



The contract of ListBuffer does not allow it to irreversibly consume the contents of the argument to ++=. So you can’t do it the way you stated; then further modifications to c would also modify b (or, worse, leave b in an inconsistent buggy state).


Not necessarily though right? When we call toList on a buffer and make
further edits the list we extracted doesn’t change. The buffer has a flag
to keep track of when the buffer’s contents need to be deepcopied. This
flag will be set on rhs after ++=.