История изменений

Че то как то сложно...

КОнтейнер пар ключ-значение (например банальный список) не меняющий адреса элементов при модификации, дерево по ключам с пойнтерами на элементы контейнера и любой ассоциативный массив с пойнтерами на элементы контейнера не покатят?

Правда при извлечении ключей сложность может оказаться хуже за счет перебалансировки дерева, но тут как ты правильно сказал проще отмечать элемент как удаленный и хранить скажем итератор на первый актуальный элемент. Тогда можно вообще никого не удалять, а просто в контейнере завести еще флаг валидности элемента.

Че то как то сложно...

КОнтейнер пар ключ-значение (например банальный список) не меняющий адреса элементов при модификации, дерево по ключам с пойнтерами на элементы контейнера и любой ассоциативный массив с пойнтерами на элементы контейнера не покатят?

Правда при извлечении ключей сложность может оказаться хуже за счет перебалансировки дерева, но тут как ты правильно сказал проще отмечать элемент как удаленный и хранить скажем первый актуальный элемент. Тогда можно вообще никого не удалять, а просто в контейнере завести еще флаг валидности элемента.