1

私のC++アプリケーションには、 sPodに関する情報をMonkeyベクトルに内部的に格納するオブジェクトがあります。MonkeyInternalサルに関する多くの特性を持つ大きなクラスです...

ここでの私の意図はMonkey、プライベートベクターに格納されているより多くの情報にアクセスするために使用できるインデックスを格納するだけの軽量プロキシオブジェクトを作成することですPod（サルは気まぐれで、プロパティが変更される可能性があり、プログラム内のサルオブジェクトは常に最新の状態にしてください。）

class Pod {
  public:
    typedef Monkey monkey_type;

    Monkey monkey(int monkey_index) {
      return Monkey(this, monkey_index);
    }

    // Lightweight proxy Monkey object that can be passed around easily.
    class Monkey {
      public:
        Monkey(Pod* pod, int monkey_index) {
          pod_ = pod;
          monkey_index_ = monkey_index;
        }
      private:
        Pod* pod_;
        int monkey_index_; // To get monkey internal info, index into pod.
        friend class Pod; // Monkey is a proxy that delegates to Pod.
    }

  private:
    // MonkeyInternal objects stores hefty data about monkeys.
    vector<MonkeyInternal> monkeys_;
}

これらのデータ構造により、サルの内部情報にランダムに簡単にアクセスできます。また、別のサルを効率的にポッドに簡単に挿入できます（O（1）償却済み）。

ただし、すべてのサルを左にシフトする必要があるため、サルを削除するとO（n）になります。unordered_map（またはいくつかの優れたハッシュテーブル）-O（n）を使用することで、削除を少し効率的にすることができますが、サルのO（1）削除をサポートするようにデータ構造を整理する方法はありますか？

おそらく私は巧妙なデザインパターンを使用できますか？

4

1 に答える 1

1

あなたのMonkeyクラスは事実上スマートポインタです-ユーザーが彼らが扱っているものに対して正しいメンタルモデルを持っているように、それを構文的にも1つのように振る舞わせるのは良いかもしれません。

削除に関しては、ベクトルに値で格納されているMonkeyInternalを削除していると思いますか？MonkeyInternalのコピーに費用がかかる場合、保存する最善の方法は、代わりにMonkeyInternal *のように、ベクターに安価なものを格納することです。

このルートをたどると、Monkeyタイプをstd :: shared_ptrのようなものに置き換えて、それで済ませたほうがよい場合があります。

ところで、コピーが安価である限り、CPUメモリ予測が実際に何が起こっているかをうまく理解できるので、線形メモリアクセスはかなり安価です。ポインタを追跡する必要がある場合、これは崩壊するため、挿入と削除の技術的にはO（1）ではなくO（n）ですが、std::vectorの方がstd::listよりも高速であることがわかります。

于 2013-02-08T06:16:44.283 に答える