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

Такое решение всем хорошо. По ID через мапу мы спокойно узнаём итератор. А по итератору уже поднимаясь по данному дереву за logN находим его позицию относительно начала. Но тут есть тоноксть, что дерево должно балансироваться. Во время балансировки ноды будут сильно перемещаться, и все итераторы на них будут инвалидироваться, что повлечёт за собой необходимость также изменения значения итераторов в std::map<key, value>. Значит нужно менять в мапе наши value. Будет что-то около logN запросов на смену итератора в std::map. То есть log^2(N) (тут мог напутать. Поправьте, если неправ).

Такое решение всем хорошо. По ID через мапу мы спокойно узнаём итератор. А по итератору уже поднимаясь по данному дереву за logN находим его позицию относительно начала. Но тут есть тоноксть, что дерево должно балансироваться. Во время балансировки ноды будут сильно перемещаться, и все итераторы на них будут инвалидироваться, что повлечёт за собой необходимость также изменения значения итераторов в std::map<key, value>. Значит нужно менять в мапе наши value. Будет что-то около logN запросов на смену итератора в std::map. То есть log^2(N)