C++: Updating pointers in deep copy (efficiently)

Question

My question is best illustrated with a code sample, so let's just start off with that:

class Game
{
    // All this vector does is establish ownership over the Card objects
    // It is initialized with data when Game is created and then is never
    // changed.
    vector<shared_ptr<Card> > m_cards;

    // And then we have a bunch of pointers to the Cards.
    // All these pointers point to Cards from m_cards.
    // These could have been weak_ptrs, but at the moment, they aren't
    vector<Card*> m_ptrs;

    // Note: In my application, m_ptrs isn't there, instead there are
    // pointers all over the place (in objects that are stored in member
    // variables of Game.
    // Also, in my application, each Card in m_cards will have a pointer
    // in m_ptrs (or as I said, really just somewhere), while sometimes
    // there is more than one pointer to a Card.
}

Now what I want to do is to make a deep copy of this Game class. I make a new vector with new shared_ptrs in it, which point to new Card objects which are copies of the original Card objects. That part is easy.

Then the trouble starts, the pointers of m_ptrs should be updated to point to the cards in m_cards, which is no simple task.

The only way I could think of to do this is to create a map and fill it during the copying of m_cards (with map[oldPtr] = newPtr) and then to use that to update m_ptrs. However, this is only O(m * log(n)) (m = m_ptrs.size(); n = m_cards.size()). As this is going to be a pretty regular operation* I would like to do this efficiently, and I have the feeling that it should be possible in O(m) using custom pointers. However, I can't seem to find an efficient way of doing this. Anybody who does?

*it's used to create a testbed for the AI, letting it "try out" different moves

---

Edit: I would like to add a bit on accepting an answer, as I haven't yet. I am waiting until I get back to this project (I got on a side track as I had worked too much on this project - if you do it for fun it's got to stay fun), so it may be a while longer before I accept an answer. Nevertheless, I will accept an answer some time, so don't worry :P

Answer 1

Store the pointers as indexes. As you say they all point to m_Cards which is a vector that can be indexed (is that correct English?). Either you do that only for storing and convert them back to pointers at loading. Or you may think of using indices generally instead of pointers.