2

我的问题最好用一个代码示例来说明，所以让我们开始吧：

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.
}

现在我想做的是制作这个 Game 类的深拷贝。我创建了一个新向量，其中包含新的 shared_ptrs，它指向新的 Card 对象，它们是原始 Card 对象的副本。那部分很容易。

然后麻烦开始了，m_ptrs 的指针应该更新为指向 m_cards 中的卡片，这不是简单的任务。

我能想到的唯一方法是创建一个映射并在复制 m_cards（带有map[oldPtr] = newPtr）期间填充它，然后使用它来更新 m_ptrs。但是，这只是O(m * log(n))（m = m_ptrs.size(); n = m_cards.size()）。因为这将是一个非常常规的操作*我想有效地做到这一点，我觉得O(m)使用自定义指针应该是可能的。但是，我似乎无法找到一种有效的方法来做到这一点。有谁会吗？

*它用于为人工智能创建一个测试平台，让它“尝试”不同的动作

编辑：我想补充一点关于接受答案，因为我还没有。我一直在等我回到这个项目（因为我在这个项目上工作了太多，所以我走上了旁道——如果你这样做是为了好玩，那就必须保持乐趣），所以在我接受之前可能需要一段时间答案。不过，我会在一段时间内接受答案，所以不要担心：P

编辑 nr 2：我还没有回到这个项目。现在，我正在考虑只是采取O(m * log(n))方式而不是抱怨，然后看看是否需要更快。然而，由于我最近花了一些时间来学习我的模式，我也认为我真的需要一些时间来重构这个项目。哦，我可能会花一些时间利用我掌握的所有新知识来解决这个问题。由于没有答案说“只需坚持使用哈希图，稍后再看看它是否真的需要更快”（如果有的话，我实际上会非常失望，因为这不是我问题的答案），我是推迟选择答案，直到我回到这个项目。

编辑 nr 3：我仍然没有回到这个项目。更准确地说，它已被无限期搁置。我很确定我现在不会让我的头太低O(m * log(n))，然后如果结果证明是个问题，也许以后再看看。但是，这并不是我的问题的好答案，因为我明确要求更好的性能。不想让答案不再被接受，我选择了最有帮助的答案并接受了它。

4

3 回答 3

3

将指针存储为索引。正如您所说，它们都指向 m_Cards 这是一个可以索引的向量（这是正确的英语吗？）。要么您这样做只是为了存储并将它们转换回加载时的指针。或者您可能会想到通常使用索引而不是指针。

于 2010-08-23T10:07:37.077 回答
0

如何保持卡片元素索引而不是指针：

矢量<int> m_indexes;

...

卡片* ptr = &m_cards[m_indexes[0]];

带有索引的向量可以被复制而无需更改。

于 2010-08-23T10:08:46.147 回答
0

我最近遇到了一个非常相似的问题：将指针和 std::vector 实现的类内部结构克隆为对象存储。

首先（尽管与问题无关），我建议要么坚持使用智能指针，要么坚持使用简单的结构。vector<weak_ptr<Card> > m_ptrs在您的情况下，这意味着使用而不是原始指针更有意义。

关于问题本身 - 另一种可能的解决方法是在复制构造函数中使用指针差异。我将针对对象向量演示它，但使用共享指针将利用相同的原理，唯一的区别在于复制 m_cards（如果您想要对象克隆，则不应简单地使用赋值，而是m_cards逐个元素地复制） .

非常重要的是，该方法仅适用于保证存储元素的容器（向量、数组）。

另一个非常重要的时刻是m_ptrs元素应该只代表内部 Card结构，即它们必须只指向内部m_cards元素。

// assume we store objects directly, not in shared pointers
// the only difference for shared pointers will be in
// m_cards assignment
// and using m_cards[...].get() instead of &m_cards[...]
vector<Card> m_cards;
vector<Card*> m_ptrs;

在这种情况下，您的指针数组可以通过使用线性时间的指针算法轻松计算。在这种情况下，您的复制构造函数将如下所示：

Game::Game(const Game &rhs) {
  if (rhs.m_cards.empty())
    return;

  m_cards = rhs.m_cards;

  // if we have vector of shared pointers
  // and we need vector of pointers to objects clones
  // something like this should be done
  // for (auto p: rhs.m_cards) {
  //   // we must be certain here that dereferencing is safe,
  //   // i. e. object must exist. If not, additional check is required.
  //   // copy constructor will be called here:
  //   m_cards.push_back(std::make_shared<Card>(*p));
  // }

  Card *first = &rhs.m_cards[0];
  for (auto p: rhs.m_ptrs) {
    m_ptrs.push_back(&m_cards[p - first]);
  }
}

基本上，在这种 deepcopy 方法中，您仍将使用索引，但您保留了在其他类方法中使用指针的便利，而无需单独存储索引。

m_cards无论如何，对于使用这种结构，您应该确切地知道您对类成员做了什么以及为什么，这需要更多的手动控制（例如，至少应该有意识地添加/删除元素，在其他情况下m_ptrs即使不复制对象也很容易损坏）。

于 2020-09-21T14:26:34.510 回答