We still need more information about how you are using the map to give you a helpful answer.
Do you really need to put the pointers to the vector elements in the map? You are trying to setup the map so that you can iterate over to give the same sequence as the vector. In doing this, you propose to store a pointer to each element, this means that you need to do a pointer dereference for every element in the vector. Can you not simply iterate over the vector and then the map or vice versa? Can the elements in the map not be added to the vector?
You mention cache coherence so I'm assuming this is for performance purposes? Have you got a performance problem that needs resolving? Have you used a profiler to ensure you are 'optimising' the correct part of your program?