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 クラスのディープ コピーを作成することです。元の Card オブジェクトのコピーである新しい Card オブジェクトを指す、新しい shared_ptrs を含む新しいベクトルを作成します。その部分は簡単です。

その後、問題が発生します。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)カスタムポインターを使用することでそれが可能になるはずだと感じています。しかし、これを行う効率的な方法を見つけることができないようです。する人はいますか？

* AI のテストベッドを作成するために使用され、さまざまな動きを「試す」ことができます

編集：まだ回答を受け入れていないので、回答を受け入れることについて少し追加したいと思います。私はこのプロジェクトに戻るまで待っています (私はこのプロジェクトにあまりにも多くの時間を割いていたので脇道に逸れました - あなたが楽しみのためにそれをするなら、それは楽しみであり続けなければなりません)、私が受け入れるまでにはもう少し時間がかかるかもしれません.答え。それにもかかわらず、私はいつか答えを受け入れるので、心配しないでください:P

編集番号 2: 私はまだこのプロジェクトに戻っていません。今のところ、O(m * log(n))文句を言うのではなく、ただ道をたどることを考えています。しかし、私は最近自分のパターンを学ぶのに時間がかかったので、このプロジェクトをしばらくリファクタリングする必要があると考えています. ああ、それと、私が持っているすべての新しい知識を使って、この問題に取り組むことに少し時間を費やすかもしれない. 「ハッシュマップに固執して、本当に高速化する必要があるかどうかを後で確認してください」という回答がないため（私の質問に対する回答ではないため、実際にあった場合はかなりがっかりします）、私はこのプロジェクトに戻るまで、回答の選択をもう少し延期します。

編集番号 3: 私はまだこのプロジェクトに戻っていません。より正確には、それは無期限に棚上げされました。今は頭を下げすぎず、O(m * log(n))後で問題が発生した場合は後で確認することはないと確信しています。ただし、パフォーマンスの向上を明示的に求めたので、それは私の質問に対する良い答えではありませんでした。回答をこれ以上受け入れないままにしたくないので、最も役立つ回答を選択して受け入れました。

4

3 に答える 3

3

ポインターをインデックスとして格納します。あなたが言うように、それらはすべて、インデックス付けできるベクトルである m_Cards を指しています (それは正しい英語ですか?)。保存するためだけにそれを行い、ロード時にそれらをポインターに戻します。または、ポインターの代わりに一般的にインデックスを使用することを考えるかもしれません。

于 2010-08-23T10:07:37.077 に答える
0

ポインターの代わりにカード要素のインデックスを保持するのはどうですか:

vector<int> m_indexes;

...

Card* ptr = &m_cards[m_indexes[0]];

インデックス付きのベクトルは変更せずにコピーできます。

于 2010-08-23T10:08:46.147 に答える
0

私は最近、非常によく似た問題に遭遇しました: オブジェクトストレージとしてポインタと std::vector によって実装されたクラスの内部構造を複製します。

まず第一に（質問とは関係ありませんが）、スマートポインターまたは単純な構造を使用することをお勧めします。vector<weak_ptr<Card> > m_ptrsあなたの場合、生のポインターの代わりに使用する方がはるかに理にかなっていることを意味します。

質問自体について-もう1つの可能な回避策は、コピーコンストラクターでポインターの違いを使用することです。オブジェクトのベクトルについてデモンストレーションしますが、共有ポインターを使用する場合は同じ原則を利用します。唯一の違いは m_cards のコピーです (オブジェクトのクローンが必要な場合は、単に代入を使用するのではなく、m_cards要素ごとにコピーする必要があります) 。 .

このメソッドは、要素が結果的に格納されることが保証されているコンテナー (ベクター、配列) に対してのみ機能することが非常に重要です。

もう 1 つの非常に重要なポイントは、要素が内部m_ptrs構造のみを表す必要があることです。つまり、内部要素のみを指す必要があります。 Cardm_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]);
  }
}

基本的に、このディープコピー メソッドでは引き続きインデックスを操作しますが、インデックスを個別に保存することなく、他のクラス メソッドでポインターを操作する利便性を維持します。

とにかく、その種の構造を使用するには、クラスメンバーで何をしているのか、そしてその理由を正確に知る必要がありますm_cards。m_ptrsオブジェクトをコピーしなくても簡単に壊れる可能性があります)。

于 2020-09-21T14:26:34.510 に答える