ListBuffer ++= ListBuffer O(1) time


#1

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?

Jamie


#2

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).


#3

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 ++=.