Change insert/erase as specified in n2369, the implementation and tests.
I accidently only checked in the documentation from these changes in the last check in. This contains the rest of it.