Updating pointers to elements in array when array content changes

Question

Say I have a simple contiguous array or vector containing some elements of type T

std::vector<T> someVector;

I have several raw pointers to the insides of the vector distributed around the application.

T* pointerOne = &someVector[5];
T* another = &someVector[42];
T* evenMore = &someVector[55];

However, the elements in the vector sometimes move around in the application, which can invalidate pointers (as in: doesn't point to what it's supposed to point at anymore):

std::swap(someVector[4],someVector[5]); //Oops! pointerOne now essentially points to whatever was in someVector[4], and the correct object that was in someVector[5] has moved places

What's an efficient (in terms of performance and memory footprint [although that probably goes hand in hand]) system for keeping these pointers updated when the contents of the array move around?

Some notes:

• elements switch their positions very infrequently. num(location changes) << num(accesses to elements). This means that I'd like to keep pointers which are updated instead of introducing some other system that abstracts this problem away, because dereferencing a pointer is as fast as I can get in the application, and performance is very important here.
• all of the Ts will always be inside a contiguous array. It won't at some point in development change to become some other container type, like a map.
• I do know (and can modify) the code parts where the Ts are moved around inside the array. In fact that happens inside a single function. I.e. the system doesn't need to monitor the memory and somehow automatically detect at runtime if the contents of the array changes.

Answer 1

An idea similar to user3678664's suggestion optimised for the case when there are many elements in the vector and few pointers:

Create a function that uses a

multimap<int, T**> ptrmap;

to save the addresses of the pointers.

void RegisterPointer(int pos, T** ptr)
{
    ptrmap.insert(pair<int, T**>(pos, ptr));
}

Then write a function void UpdateSwappedPtrs(int pos, int newpos) that updates the swapped pointers by iterating through all the pointers in the ptrmap at pos and newpos.

Answer 2

How about holding a reverse map to the pointers. This could be an array (or vector) in the length of your original array that holds pointers to the pointers you created. For instance at index 5 of this reverse map, you will have pointers to all the pointers that point at element 5 in the original array. Now if element 5 is swapped with say element 6, just go over all the pointers in the reverse map at index 5, set them to point at element 6 in the original array and also move all these pointers to index 6 of the reverse map. You can do this work from the single point in your code that moves stuff around.