Я считаю, что C ++ 03 не дает никаких гарантий стабильности данных в памяти , и это будет деталью реализации (и на самом деле это не то, что вы можете безопасно предположить без тестирования).
Обратите внимание, что сохранение итераторов на карте и расположение фактического вектора в памяти - это совершенно разные вещи .Действительность итераторов четко определена (когда они действительны, а когда нет) в спецификации C ++, но фактическое внутреннее поведение дерева - нет.
Тем не менее, любой достойный компилятор(для релизных сборок / с включенной оптимизацией) реализация оптимизировалась бы так, чтобы фактически не копировать вектор при его перемещении в дереве, а реализации C ++ 11 std::map будут использовать семантику перемещения для гарантии такого поведения.
Чего вы не можете предположить, так это того, что перемещаются только внутренние указатели.