Question about SparseMultiSet

Does anyone know if an insertion invalidates the end() iterator? The documentation in ADT/SparseMultiSet.h mentions that removal only invalidates the iterator of the object being removed, but nothing on insertion. My understanding from reading the code seems to me that it doesn’t invalidate it, but I want to make sure as I’m not 100% sure here.

Thanks,

Micah

Sorry for the late reply.

Does anyone know if an insertion invalidates the end() iterator? The documentation in ADT/SparseMultiSet.h mentions that removal only invalidates the iterator of the object being removed, but nothing on insertion. My understanding from reading the code seems to me that it doesn’t invalidate it, but I want to make sure as I’m not 100% sure here.

You are correct.

From the documentation:
  The doubly linked list is implemented circular in Prev indices, and INVALID-terminated in Next indices.

Insertion will modify the Next index of the tail of the list for that key, and assigning it the index of the newly inserted entry.

Of course, if you had walked an iterator off the end of one of these lists (and thus, it's INVALID/equal to end()), that iterator will not be magically updated to point to the newly inserted value. This behavior is consistent with other set-like data structures.

Feel free to ask me if you have any questions.

Thanks for the clarification.

Micah