1

在我的 C++ 应用程序中，我有一些Pod对象在内部将有关Monkeys 的信息存储在向量中。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_;
}

通过这些数据结构，我可以很容易地随机访问猴子的内部信息。我还可以轻松地将另一只猴子有效地插入 pod（O(1) 摊销）。

然而，移除一只猴子是 O(n)，因为我必须把所有的猴子都移到左边。我可以通过使用unordered_map（或一些好的哈希表）-O(n) 来稍微提高移除效率，但是有什么方法可以组织我的数据结构以支持 O(1) 移除猴子？

也许我可以使用一个聪明的设计模式？

4

1 回答 1

1

你的 Monkey 类实际上是一个智能指针——让它在语法上表现得像一个指针可能会很好，这样用户就可以对他们正在处理的内容拥有正确的心理模型。

至于删除，我假设您要删除按值存储在向量中的 MonkeyInternal？如果复制 MonkeyInternal 的成本很高，那么最好的保存方法是在向量​​中存储一些便宜的东西，比如 MonkeyInternal*。

一旦你沿着这条路线走下去，你可能会发现用 std::shared_ptr 之类的东西替换你的 Monkey 类型会更好，然后就完成了。

顺便说一句，只要副本便宜，线性内存访问就非常便宜，因为 CPU 内存预测可以很好地计算出正在发生的事情。如果您必须追逐指针，这将分崩离析，因此您可能会发现 std::vector 比 std::list 快，即使它在技术上是 O(n) 而不是 O(1) 用于插入和删除。

于 2013-02-08T06:16:44.283 回答